ในทฤษฎีเครือข่ายการจำแนกประเภทแบบรวมกลุ่มคือการทำนายป้ายกำกับสำหรับวัตถุหลายชิ้นพร้อมกัน โดยแต่ละป้ายกำกับจะถูกทำนายโดยใช้ข้อมูลเกี่ยวกับคุณลักษณะ ที่สังเกตได้ของวัตถุ คุณลักษณะที่สังเกตได้และป้ายกำกับของเพื่อนบ้าน และป้ายกำกับที่ไม่ได้รับการสังเกตของเพื่อนบ้าน^{[ 1 ]}ปัญหาการจำแนกประเภทแบบรวมกลุ่มถูกกำหนดในแง่ของเครือข่ายของตัวแปรสุ่ม โดยโครงสร้างเครือข่ายจะกำหนดความสัมพันธ์ระหว่างตัวแปรสุ่มการอนุมานจะดำเนินการกับตัวแปรสุ่มหลายตัวพร้อมกัน โดยทั่วไปโดยการเผยแพร่ข้อมูลระหว่างโหนดในเครือข่ายเพื่อทำการอนุมานโดยประมาณแนวทางที่ใช้การจำแนกประเภทแบบรวมกลุ่มสามารถใช้ข้อมูลเชิงสัมพันธ์เมื่อทำการอนุมาน ตัวอย่างของการจำแนกประเภทแบบรวมกลุ่ม ได้แก่ การทำนายคุณลักษณะ (เช่น เพศ อายุ สังกัดทางการเมือง) ของบุคคลในเครือข่ายสังคมการจำแนกเว็บเพจในเวิลด์ไวด์เว็บและการอนุมานพื้นที่วิจัยของบทความในชุดข้อมูลสิ่งพิมพ์ทางวิทยาศาสตร์

โดยทั่วไปแล้ว การเรียนรู้ของเครื่องมุ่งเน้นไปที่การแก้ ปัญหา การจำแนกประเภท เป็นหลัก (ตัวอย่างเช่น เมื่อมีอีเมลชุดหนึ่ง เราต้องการระบุว่าอีเมลใดเป็นสแปมและอีเมลใดไม่ใช่) โมเดลการเรียนรู้ของเครื่องจำนวนมากสำหรับการทำงานนี้จะพยายามจัดหมวดหมู่แต่ละรายการอย่างอิสระและมุ่งเน้นไปที่การทำนายป้ายกำกับคลาสแยกกัน อย่างไรก็ตาม ความแม่นยำในการทำนายป้ายกำกับซึ่งค่าจะต้องถูกอนุมานนั้นสามารถปรับปรุงได้ด้วยความรู้เกี่ยวกับป้ายกำกับคลาสที่ถูกต้องสำหรับรายการที่เกี่ยวข้อง ตัวอย่างเช่น การทำนายหัวข้อของเว็บเพจจะง่ายขึ้นหากเรารู้หัวข้อของเว็บเพจที่เชื่อมโยงไปยังเว็บเพจนั้น ในทำนองเดียวกัน โอกาสที่คำใดคำหนึ่งจะเป็นคำกริยาจะเพิ่มขึ้นหากเรารู้ว่าคำก่อนหน้าในประโยคเป็นคำนาม การรู้ตัวอักษรสองสามตัวแรกในคำสามารถทำให้การระบุตัวอักษรที่เหลือทำได้ง่ายขึ้นมาก นักวิจัยหลายคนได้เสนอเทคนิคที่พยายามจำแนกตัวอย่างในลักษณะร่วมกันหรือแบบรวมกลุ่ม แทนที่จะจัดการแต่ละตัวอย่างแยกกัน เทคนิคเหล่านี้ทำให้ความแม่นยำในการจำแนกประเภทเพิ่มขึ้นอย่างมาก^{[ 1 ] [ 2 ]}

ลองพิจารณาภารกิจในการอนุมานความเชื่อทางการเมืองของผู้ใช้ในเครือข่ายสังคมออนไลน์ ซึ่งความเชื่อทางการเมืองบางส่วนสามารถสังเกตได้ และส่วนที่เหลือไม่สามารถสังเกตได้ ผู้ใช้แต่ละคนมีคุณลักษณะเฉพาะตัว เช่น ข้อมูลโปรไฟล์ และมีการเชื่อมโยงระหว่างผู้ใช้ที่เป็นเพื่อนกันในเครือข่ายสังคมนี้ วิธีการที่ไม่จัดกลุ่มผู้ใช้โดยรวมจะพิจารณาผู้ใช้แต่ละคนในเครือข่ายอย่างอิสระ และใช้คุณลักษณะเฉพาะตัวของพวกเขาเพื่ออนุมานความเชื่อทางการเมือง ในขณะที่วิธีการที่ทำการจัดกลุ่มโดยรวมอาจสมมติว่าผู้ใช้ที่เป็นเพื่อนกันมักมีมุมมองทางการเมืองที่คล้ายคลึงกัน จากนั้นจึงสามารถอนุมานความเชื่อทางการเมืองที่ไม่สามารถสังเกตได้ทั้งหมดโดยใช้ประโยชน์จากโครงสร้างความสัมพันธ์ที่ซับซ้อนของเครือข่ายสังคม

พิจารณา ปัญหา การเรียนรู้แบบกึ่งกำกับดูแล (semi-supervised learning)ในการกำหนดป้ายกำกับให้กับโหนดในเครือข่ายโดยใช้ความรู้เกี่ยวกับป้ายกำกับย่อยของโหนดเหล่านั้น โดยเฉพาะอย่างยิ่ง เราได้รับเครือข่ายที่แสดงด้วยกราฟ ซึ่งประกอบด้วยเซตของโหนดและเซตของขอบที่แสดงความสัมพันธ์ระหว่างโหนด แต่ละโหนดจะถูกอธิบายด้วยคุณลักษณะของมัน ได้แก่ เวกเตอร์คุณลักษณะและป้ายกำกับ (หรือคลาส) ของมัน ${\displaystyle G}$${\displaystyle V}$${\displaystyle E}$${\displaystyle v_{i}\in V}$${\displaystyle x_{i}\in X}$${\displaystyle y_{i}\in Y}$

${\displaystyle V}$สามารถแบ่งออกเป็นสองกลุ่มย่อยได้อีก คือกลุ่มโหนดที่เราทราบค่าป้ายกำกับที่ถูกต้อง (ตัวแปรที่สังเกตได้) และกลุ่มโหนดที่ต้องอนุมานป้ายกำกับ งานจำแนกประเภทโดยรวมคือการติดป้ายกำกับให้กับโหนดในกลุ่มด้วยป้ายกำกับจากชุดป้ายกำกับ ${\displaystyle L}$${\displaystyle U}$${\displaystyle U}$${\displaystyle L=\{L_{1},\cdots L_{q}\}}$

ในสถานการณ์เช่นนี้ อัลกอริทึมการจำแนกประเภทแบบดั้งเดิมจะถือว่าข้อมูลถูกสุ่มมาอย่างอิสระและเหมือนกันจากบางการแจกแจง (iid) ซึ่งหมายความว่าป้ายกำกับที่อนุมานสำหรับโหนดที่ยังไม่ทราบป้ายกำกับนั้นจะเป็นอิสระต่อกัน แต่เราจะไม่ใช้สมมติฐานนี้เมื่อทำการจำแนกประเภทแบบรวมกลุ่ม แทนที่จะเป็นเช่นนั้น จะมีการใช้ความสัมพันธ์สามประเภทที่แตกต่างกันเพื่อกำหนดการจำแนกประเภทหรือป้ายกำกับของข้อมูล: ${\displaystyle v}$

1. ความสัมพันธ์ระหว่างป้ายกำกับและคุณลักษณะที่สังเกตได้ของตัวจำแนกแบบอิสระและมีการกระจายเหมือนกันแบบดั้งเดิมซึ่งใช้เวกเตอร์คุณลักษณะเป็นตัวอย่างของวิธีการที่ใช้ความสัมพันธ์นี้${\displaystyle v}$${\displaystyle v}$
2. ความสัมพันธ์ระหว่างป้ายกำกับของและคุณลักษณะที่สังเกตได้ (รวมถึงป้ายกำกับที่สังเกตได้) ของโหนดในบริเวณใกล้เคียงของ${\displaystyle v}$${\displaystyle v}$
3. ความสัมพันธ์ระหว่างป้ายกำกับของวัตถุกับป้ายกำกับที่มองไม่เห็นของวัตถุในบริเวณใกล้เคียง${\displaystyle v}$${\displaystyle v}$

การจัดกลุ่มแบบรวม หมายถึงการจัดกลุ่มวัตถุที่เชื่อมโยงกันเป็นกลุ่ม โดยใช้ข้อมูลทั้งสามประเภทข้างต้น

มีแนวทางการจัดกลุ่มแบบรวมอยู่หลายวิธี วิธีหลักสองวิธีคือวิธีแบบวนซ้ำและวิธีที่อิงตามแบบจำลองกราฟิกเชิงความน่าจะเป็น^{[ 3 ]}

แนวคิดทั่วไปของวิธีการวนซ้ำคือการรวมและปรับปรุงการคาดการณ์ของแต่ละโหนดอย่างต่อเนื่องจนกว่าจะถึงจุดสมดุล เมื่อการอัปเดตการคาดการณ์สำหรับแต่ละโหนดเป็นกระบวนการที่รวดเร็ว ความซับซ้อนของวิธีการวนซ้ำเหล่านี้จะขึ้นอยู่กับจำนวนรอบที่จำเป็นสำหรับการบรรจบกัน แม้ว่าการบรรจบกันและความเหมาะสมที่สุดจะไม่ได้รับการรับประกันทางคณิตศาสตร์เสมอไป แต่ในทางปฏิบัติ วิธีการเหล่านี้มักจะบรรจบกันอย่างรวดเร็วไปยังโซลูชันที่ดี ขึ้นอยู่กับโครงสร้างของกราฟและความซับซ้อนของปัญหา วิธีการที่นำเสนอในส่วนนี้เป็นตัวอย่างของวิธีการวนซ้ำนี้

ข้อสันนิษฐานตามธรรมชาติในการจำแนกเครือข่ายคือโหนดที่อยู่ติดกันมีแนวโน้มที่จะมีป้ายกำกับเดียวกัน (เช่น การแพร่กระจายหรือความเหมือนกัน ) ตัวทำนายสำหรับโหนดโดยใช้วิธีการแพร่กระจายป้ายกำกับคือค่าเฉลี่ยถ่วงน้ำหนักของป้ายกำกับเพื่อนบ้าน^{[ 4 ]}${\displaystyle V_{i}}$${\displaystyle Y_{N_{i}}}$

แม้ว่าการแพร่กระจายป้ายกำกับจะมีประสิทธิภาพอย่างน่าประหลาดใจ แต่บางครั้งอาจไม่สามารถจับพลวัตเชิงสัมพันธ์ที่ซับซ้อนได้ วิธีการที่ซับซ้อนกว่าสามารถใช้ตัวทำนายที่สมบูรณ์ยิ่งขึ้น สมมติว่าเรามีตัวจำแนกประเภทที่ได้รับการฝึกฝนให้จำแนกโหนดโดยพิจารณาจากคุณลักษณะของ โหนดนั้น และคุณลักษณะและป้ายกำกับของเพื่อนบ้านการจำแนกประเภทแบบวนซ้ำจะใช้ตัวจำแนกประเภทเฉพาะที่สำหรับแต่ละโหนด ซึ่งใช้ข้อมูลเกี่ยวกับการทำนายในปัจจุบันและ ข้อมูล ความจริงเกี่ยวกับเพื่อนบ้านของโหนด และวนซ้ำจนกว่าการทำนายเฉพาะที่จะมาบรรจบกันที่โซลูชันโดยรวม การจำแนกประเภทแบบวนซ้ำเป็น “กรอบงานเชิงอัลกอริทึม” ในแง่ที่ว่ามันไม่ขึ้นกับตัวเลือกของตัวทำนาย ทำให้เป็นเครื่องมืออเนกประสงค์มากสำหรับการจำแนกประเภทแบบรวมกลุ่ม ^{[ 5 ] [ 6 ] [ 7 ]}${\displaystyle h}$${\displaystyle v_{i}}$${\displaystyle X_{i}}$${\displaystyle X_{N_{i}}}$${\displaystyle Y_{N_{i}}}$${\displaystyle N_{i}}$

อีกแนวทางหนึ่งสำหรับการจำแนกประเภทแบบรวมกลุ่มคือการแสดงปัญหาด้วยแบบจำลองกราฟิกและใช้เทคนิคการเรียนรู้และการอนุมานสำหรับวิธีการสร้างแบบจำลองกราฟิกเพื่อให้ได้การจำแนกประเภทที่ถูกต้อง แบบจำลองกราฟิกเป็นเครื่องมือสำหรับการอนุมานเชิงความน่าจะเป็นร่วมกัน ทำให้เหมาะสำหรับการจำแนกประเภทแบบรวมกลุ่ม ลักษณะเฉพาะของแบบจำลองกราฟิกคือการแสดงการกระจายความน่าจะเป็นใน รูปแบบกราฟิก โดยที่ตัวแปรสุ่มเป็นโหนดในกราฟแบบจำลองกราฟิกสามารถแบ่งออกได้เป็นหมวดหมู่กว้างๆ ว่ากราฟพื้นฐานเป็นแบบมีทิศทาง (เช่นเครือข่ายเบย์เซียนหรือชุดของตัวจำแนกประเภทเฉพาะที่) หรือไม่มีทิศทาง (เช่นฟิลด์สุ่มมาร์คอฟ (MRF)) ${\displaystyle P}$${\displaystyle G}$

การสุ่มตัวอย่างแบบ Gibbsเป็นกรอบการทำงานทั่วไปสำหรับการประมาณค่าการแจกแจง เป็น อัลกอริทึม Markov chain Monte Carloที่ทำการสุ่มตัวอย่างซ้ำๆ จากการประมาณค่าการแจกแจงในปัจจุบัน สร้างห่วงโซ่ Markov ที่ลู่เข้าสู่การแจกแจงเป้าหมาย (คงที่) แนวคิดพื้นฐานของการสุ่มตัวอย่างแบบ Gibbs คือการสุ่มตัวอย่างเพื่อหาค่าประมาณป้ายกำกับที่ดีที่สุดสำหรับค่าทั้งหมดของโหนดโดยใช้ตัวจำแนกประเภทท้องถิ่นเป็นจำนวนรอบคงที่ หลังจากนั้น เราจะสุ่มป้ายกำกับสำหรับแต่ละโหนดและเก็บสถิติการนับจำนวนครั้งที่เราสุ่มป้ายกำกับสำหรับโหนดนั้นหลังจากรวบรวมตัวอย่างตามจำนวนที่กำหนดไว้ล่วงหน้าแล้ว เราจะส่งออกการกำหนดป้ายกำกับที่ดีที่สุดสำหรับโหนดโดยเลือกป้ายกำกับที่ถูกกำหนดให้กับโหนดนั้นมากที่สุดในขณะที่รวบรวมตัวอย่าง^{[ 8 ] [ 9 ]}${\displaystyle y_{i}}$${\displaystyle N_{i}}$${\displaystyle f}$${\displaystyle y_{i}\in Y}$${\displaystyle l}$${\displaystyle y_{i}}$${\displaystyle y_{i}}$${\displaystyle y_{i}}$

สำหรับแบบจำลองกราฟิกที่ไม่กำหนดทิศทางบางแบบ เป็นไปได้ที่จะทำการอนุมานที่แม่นยำอย่างมีประสิทธิภาพผ่านการส่งข้อความหรือ อัลกอริธึ มการแพร่กระจายความเชื่อ^{[ 10 ]}อัลกอริธึมเหล่านี้ปฏิบัติตามรูปแบบการวนซ้ำที่เรียบง่าย: ตัวแปรแต่ละตัวส่ง "ความเชื่อ" เกี่ยวกับการแจกแจงแบบมาร์จินัลของเพื่อนบ้าน จากนั้นใช้ข้อความที่เข้ามาเกี่ยวกับค่าของตนเองเพื่ออัปเดตความเชื่อ การบรรจบกันไปยังมาร์จินัลที่แท้จริงรับประกันได้สำหรับ MRF ที่มีโครงสร้างแบบต้นไม้ แต่ไม่รับประกันสำหรับ MRF ที่มีวงจร

การเรียนรู้เชิงสัมพันธ์ทางสถิติมักใช้เพื่อแก้ไขปัญหาการจำแนกประเภทแบบรวมกลุ่ม วิธีการ SRL ที่หลากหลายได้ถูกนำมาใช้กับการตั้งค่าการจำแนกประเภทแบบรวมกลุ่ม วิธีการบางอย่างรวมถึงวิธีการโดยตรง เช่น แบบจำลองเชิงสัมพันธ์ความน่าจะเป็น (PRM) ^{[ 11 ]}แบบจำลองเงื่อนไขแบบเชื่อมโยง เช่น การจำแนกประเภทตามลิงก์^{[ 12 ]} และวิธีการทางอ้อม เช่นเครือข่ายตรรกะมาร์คอฟ (MLN) ^{[ 13 ]}และตรรกะอ่อนเชิงความน่าจะเป็น (PSL) ^{[ 14 ]}

การจัดกลุ่มแบบรวมถูกนำไปใช้ในหลายสาขาที่มีโครงสร้างเชิงสัมพันธ์ เช่น:

• การวิเคราะห์เครือข่ายสังคมซึ่งวิธีการแบบรวมกลุ่มสำหรับงานจำแนกประเภทโหนด เช่น การตรวจจับผู้ใช้ที่เป็นอันตราย สามารถใช้ข้อมูลเกี่ยวกับความสัมพันธ์ระหว่างโหนดได้^{[ 15 ] [ 16 ]}
• การแก้ไขเอนทิตีซึ่งสามารถใช้ความสัมพันธ์ร่วมเขียนเพื่อระบุผู้เขียนบทความได้^{[ 17 ]}
• การระบุเอนทิตีที่มีชื่อ ซึ่งบางแนวทางถือว่านี่เป็นปัญหา การติดป้ายลำดับข้อความและอนุมานป้ายกำกับของทุกคำในประโยคร่วมกัน โดยทั่วไปจะใช้ฟิลด์สุ่มแบบมีเงื่อนไขซึ่งจำลองห่วงโซ่เชิงเส้นของการพึ่งพาระหว่างป้ายกำกับของคำที่อยู่ติดกันในประโยค^{[ 18 ]}
• การจำแนกประเภทเอกสารโดยที่ความคล้ายคลึงทางความหมายระหว่างเอกสารสามารถนำมาใช้ร่วมกันเป็นสัญญาณว่าเอกสารบางฉบับอยู่ในกลุ่มเดียวกัน^{[ 19 ]}
• ชีววิทยาเชิงคำนวณซึ่ง ใช้ แบบจำลองกราฟิกเช่นฟิลด์สุ่มมาร์คอฟเพื่ออนุมานความสัมพันธ์ร่วมกันระหว่างเอนทิตีทางชีววิทยา เช่น ยีน^{[ 20 ]}
• วิชั่นคอมพิวเตอร์ซึ่งตัวอย่างเช่น การจำแนกประเภทแบบรวมกลุ่มสามารถนำไปใช้ในการจดจำวัตถุหลายชิ้นพร้อมกันได้^{[ 21 ]}

• การเรียนรู้ของเครื่อง
• การจำแนกประเภท
• ความคล้ายคลึง (วิทยาศาสตร์เครือข่าย)
• กราฟ (คณิตศาสตร์เชิงดิสครีต)
• การเรียนรู้เชิงสัมพันธ์ทางสถิติ
• เครือข่ายเบย์เซียน
• ฟิลด์สุ่มมาร์คอฟ