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

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

เป้าหมายคือการค้นหาการจัดกลุ่ม (นั่นคือการแบ่งกลุ่มของข้อมูล) ที่ทำให้จำนวนความสอดคล้อง สูงสุด —ผลรวมของขอบบวกที่มีจุดปลายอยู่ในกลุ่มเดียวกัน และขอบลบที่มีจุดปลายอยู่ในกลุ่มที่แตกต่างกัน—หรือทำให้จำนวนความไม่สอดคล้อง น้อยที่สุด —ผลรวมของขอบบวกที่มีจุดปลายแยกจากกัน และขอบลบที่มีจุดปลายอยู่ในกลุ่มเดียวกัน แตกต่างจากวิธีการจัดกลุ่มอื่นๆ เช่นk-meansการจัดกลุ่มแบบสหสัมพันธ์ไม่จำเป็นต้องเลือกจำนวนกลุ่มล่วงหน้า ${\displaystyle V}$${\displaystyle k}$

การหาคลัสเตอร์ที่มีความขัดแย้งเป็นศูนย์นั้นไม่ใช่เรื่องที่เป็นไปได้เสมอไป ตัวอย่างเช่น ลองพิจารณากราฟรูปสามเหลี่ยมที่มีขอบบวกสองขอบและขอบลบหนึ่งขอบ ในกรณีนี้ คลัสเตอร์ทุกคลัสเตอร์จะเกิดความขัดแย้งอย่างน้อยหนึ่งรายการ การกำหนดค่าดังกล่าวในเอกสารทางวิชาการเรียกว่าสามเหลี่ยมที่ไม่ดี^{[ 2 ]}

จากมุมมองการคำนวณ การเพิ่มประสิทธิภาพเป้าหมายการจัดกลุ่มความสัมพันธ์เป็นเรื่องท้าทาย ปัญหา (เวอร์ชันการตัดสินใจของ) เป็นปัญหาNP-complete [ ^{3 ] งาน} วิจัยจำนวนมากในภายหลังได้พัฒนาอัลกอริทึมการประมาณค่าสำหรับการจัดกลุ่มความสัมพันธ์ภายใต้สมมติฐานต่างๆ รวมถึงกราฟที่สมบูรณ์หรือทั่วไป และกราฟที่ไม่มีน้ำหนักหรือมีน้ำหนัก สำหรับทั้งเป้าหมายการลดค่าและการเพิ่มค่า ปัญหานี้ถือเป็นหนึ่งใน ปัญหา การเพิ่มประสิทธิภาพเชิงการจัดเรียง พื้นฐาน และมีการพัฒนาเทคนิคอัลกอริทึมมากมายเพื่อแก้ไขปัญหานี้

ปัญหาดังกล่าวได้รับการศึกษาอย่างกว้างขวางในหลายสาขาวิชา Wahid และ Hassini ได้รวบรวมบทวิจารณ์วรรณกรรมที่ครอบคลุมเกี่ยวกับการวิจัยการจัดกลุ่มความสัมพันธ์ในช่วงแรก^{[ 4 ]}

ให้G เป็นกราฟที่มีโหนดและขอบการจัดกลุ่มของ G คือการแบ่งเซตของโหนดด้วยและสำหรับการจัดกลุ่มที่กำหนดให้แทนเซตย่อยของขอบของ G ที่มีจุดปลายอยู่ในเซตย่อยที่แตกต่างกันของการจัดกลุ่มทีนี้ ให้เป็นฟังก์ชันที่กำหนดค่าน้ำหนักที่ไม่เป็นลบให้กับแต่ละขอบของกราฟ และให้เป็นการแบ่งขอบออกเป็นขอบดึงดูด ( ) และขอบผลักดัน ( ) กล่าวคือ ขอบมี เครื่องหมาย${\displaystyle G=(V,E)}$${\displaystyle V}$${\displaystyle E}$${\displaystyle G}$${\displaystyle \Pi =\{\pi _{1},\dots ,\pi _{k}\}}$${\displaystyle V=\pi _{1}\cup \dots \cup \pi _{k}}$${\displaystyle \pi _{i}\cap \pi _{j}=\emptyset }$${\displaystyle i\neq j}$${\displaystyle \Pi }$${\displaystyle \delta (\Pi )=\{\{u,v\}\in E\mid \{u,v\}\not \subseteq \pi \;\forall \pi \in \Pi \}}$${\displaystyle G}$${\displaystyle \Pi }$${\displaystyle w\colon E\to \mathbb {R} _{\geq 0}}$${\displaystyle E=E^{+}\cup E^{-}}$${\displaystyle E^{+}}$${\displaystyle E^{-}}$

ปัญหาการจัดกลุ่มความสัมพันธ์ที่ไม่สอดคล้องกันน้อยที่สุดคือปัญหาการหาค่าเหมาะสม ที่สุดดังต่อไปนี้ : ในที่นี้ เซตประกอบด้วยขอบที่ดึงดูดกันซึ่งจุดปลายอยู่ในส่วนประกอบที่แตกต่างกันเมื่อเทียบกับการจัดกลุ่มและเซตประกอบด้วยขอบที่ผลักดันกันซึ่งจุดปลายอยู่ในส่วนประกอบเดียวกันเมื่อเทียบกับการจัดกลุ่มเซตทั้งสองนี้รวมกันประกอบด้วยขอบทั้งหมดที่ไม่สอดคล้องกับการจัดกลุ่ม $${\displaystyle {\begin{aligned}&{\underset {\Pi }{\operatorname {minimize} }}&&\sum _{e\in E^{+}\cap \delta (\Pi )}w_{e}+\sum _{e\in E^{-}\setminus \delta (\Pi )}w_{e}\;.\end{aligned}}}$$${\displaystyle E^{+}\cap \delta (\Pi )}$${\displaystyle \Pi }$${\displaystyle E^{-}\setminus \delta (\Pi )}$${\displaystyle \Pi }$${\displaystyle \Pi }$

เช่นเดียวกับปัญหาการจัดกลุ่มความสัมพันธ์ที่ไม่เห็นด้วยน้อยที่สุด ปัญหาการจัดกลุ่มความสัมพันธ์ที่เห็นด้วยมากที่สุดถูกกำหนดไว้ดังนี้ โดย ที่เซตประกอบด้วยขอบที่ดึงดูดกันซึ่งจุดปลายอยู่ในส่วนประกอบเดียวกันเมื่อพิจารณาการจัดกลุ่มและเซตประกอบด้วยขอบที่ผลักดันกันซึ่งจุดปลายอยู่ในส่วนประกอบที่แตกต่างกันเมื่อพิจารณาการจัดกลุ่มเซตทั้งสองนี้รวมกันประกอบด้วยขอบทั้งหมดที่สอดคล้องกับการจัดกลุ่ม $${\displaystyle {\begin{aligned}&{\underset {\Pi }{\operatorname {maximize} }}&&\sum _{e\in E^{+}\setminus \delta (\Pi )}w_{e}+\sum _{e\in E^{-}\cap \delta (\Pi )}w_{e}\;.\end{aligned}}}$$${\displaystyle E^{+}\setminus \delta (\Pi )}$${\displaystyle \Pi }$${\displaystyle E^{-}\cap \delta (\Pi )}$${\displaystyle \Pi }$${\displaystyle \Pi }$

แทนที่จะกำหนดปัญหาการจัดกลุ่มความสัมพันธ์ในแง่ของน้ำหนักขอบที่ไม่เป็นลบและการแบ่งขอบออกเป็นขอบดึงดูดและขอบผลักดัน ปัญหานี้ยังถูกกำหนดในแง่ของต้นทุนขอบที่เป็นบวกและลบโดยไม่ต้องแบ่งเซตของขอบอย่างชัดเจน สำหรับน้ำหนักที่กำหนดและการแบ่งขอบออกเป็นขอบดึงดูดและขอบผลักดันที่กำหนด ต้นทุนขอบสามารถกำหนดได้โดย สำหรับทุกค่า ${\displaystyle w\colon E\to \mathbb {R} _{\geq 0}}$${\displaystyle E=E^{+}\cup E^{-}}$$${\displaystyle {\begin{aligned}c_{e}={\begin{cases}\;\;w_{e}&{\text{if }}e\in E^{+}\\-w_{e}&{\text{if }}e\in E^{-}\end{cases}}\end{aligned}}}$$${\displaystyle e\in E}$

ขอบที่มีจุดปลายอยู่ในคลัสเตอร์ที่แตกต่างกันเรียกว่าขอบที่ถูกตัด เซตของ ขอบทั้งหมดที่ถูกตัดมักเรียกว่ามัลติคัท^{[ 5 ]}ของ${\displaystyle \delta (\Pi )}$${\displaystyle G}$

ปัญหาการตัดหลายเส้นที่มีต้นทุนต่ำสุด คือ ปัญหาการหาการจัดกลุ่มที่ทำให้ผลรวมของต้นทุนของเส้นเชื่อมที่มีจุดปลายอยู่ในกลุ่มที่แตกต่างกันมีค่าน้อยที่สุด: ${\displaystyle \Pi }$${\displaystyle G}$$${\displaystyle {\begin{aligned}&{\underset {\Pi }{\operatorname {minimize} }}&&\sum _{e\in \delta (\Pi )}c_{e}\;.\end{aligned}}}$$

เช่นเดียวกับปัญหาการตัดหลายส่วนที่มีต้นทุนขั้นต่ำ การสร้างโครงสร้างพันธมิตรในเกมกราฟถ่วงน้ำหนัก^{[ 6 ]}เป็นปัญหาของการค้นหาการจัดกลุ่มที่ทำให้ผลรวมของต้นทุนของขอบที่ไม่ถูกตัดมีค่าสูงสุด: การกำหนดสูตรนี้ยังเป็นที่รู้จักในชื่อปัญหาการแบ่งกลุ่มคลิก^{[ 7 ]}$${\displaystyle {\begin{aligned}&{\underset {\Pi }{\operatorname {maximize} }}&&\sum _{e\in E\setminus \delta (\Pi )}c_{e}\;.\end{aligned}}}$$

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

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

Bansal et al. ^{[ 9 ]}อภิปรายการพิสูจน์ความสมบูรณ์ของ NP และยังนำเสนออัลกอริทึมการประมาณค่าปัจจัยคงที่และแผนการประมาณค่าในเวลาพหุนามเพื่อค้นหาคลัสเตอร์ในการตั้งค่านี้ Ailon et al. ^{[ 10 ]} เสนอ อัลกอริทึมการประมาณค่า 3 แบบสุ่มสำหรับปัญหาเดียวกัน

CC-Pivot (G=(V,E + ,E − )) เลือกจุดหมุนแบบสุ่ม i ∈ V กำหนดให้V'=Ø สำหรับทุก j ∈ V, j ≠ i; ถ้า (i,j) ∈ E + แล้ว${\displaystyle C=\{i\}}$ เพิ่ม j ลงใน C มิฉะนั้น (ถ้า (i,j) ∈ E − ) เพิ่ม j ลงใน V' ให้ G' เป็นกราฟย่อยที่เกิดจาก V' ส่งคืนการจัดกลุ่ม C,CC-Pivot(G') 

ผู้เขียนแสดงให้เห็นว่าอัลกอริทึมข้างต้นเป็นอัลกอริทึมการประมาณค่า 3 เท่าสำหรับการจัดกลุ่มความสัมพันธ์ อัลกอริทึมการประมาณค่าแบบพหุนามที่ดีที่สุดที่ทราบในขณะนี้สำหรับปัญหานี้บรรลุการประมาณค่าประมาณ ~2.06 โดยการ ^{ปัดเศษ}โปรแกรมเชิงเส้น ดังที่แสดงโดยChawla , Makarychev, Schramm และYaroslavtsev ^[ 11 ^]

Karpinski และ Schudy ^{[ 12 ]}พิสูจน์การมีอยู่ของ แผนการประมาณค่าแบบ พหุนามเวลา (PTAS) สำหรับปัญหาดังกล่าวบนกราฟสมบูรณ์และจำนวนคลัสเตอร์คงที่

^{ในปี 2011 Bagon และ Galun [ 13 ]}ได้แสดงให้เห็น ว่าการปรับฟังก์ชันการจัดกลุ่มความสัมพันธ์ให้เหมาะสมนั้นมีความเกี่ยวข้องอย่างใกล้ชิดกับ วิธี การปรับให้เหมาะสมแบบไม่ต่อเนื่องที่เป็น ที่รู้จักกันดี ในงานของพวกเขา พวกเขาได้เสนอการวิเคราะห์เชิงความน่าจะเป็นของแบบจำลองโดยนัยพื้นฐานที่ช่วยให้ฟังก์ชันการจัดกลุ่มความสัมพันธ์สามารถประมาณจำนวนคลัสเตอร์พื้นฐานได้ การวิเคราะห์นี้ชี้ให้เห็นว่าฟังก์ชันดังกล่าวถือว่ามีความน่าจะเป็นล่วงหน้าแบบสม่ำเสมอเหนือพาร์ติชันที่เป็นไปได้ทั้งหมดโดยไม่คำนึงถึงจำนวนคลัสเตอร์ ดังนั้นจึงเกิดความน่าจะเป็นล่วงหน้าที่ไม่สม่ำเสมอเหนือจำนวนคลัสเตอร์ขึ้น

งานวิจัยนี้ได้เสนออัลกอริธึมการปรับให้เหมาะสมแบบไม่ต่อเนื่องหลายแบบ ซึ่งสามารถปรับขนาดได้อย่างเหมาะสมกับจำนวนองค์ประกอบ (การทดลองแสดงผลลัพธ์ที่มีตัวแปรมากกว่า 100,000 ตัว) นอกจากนี้ งานวิจัยของ Bagon และ Galun ยังได้ประเมินประสิทธิภาพของการกู้คืนจำนวนคลัสเตอร์พื้นฐานในแอปพลิเคชันต่างๆ อีกด้วย

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

ความสัมพันธ์ระหว่างชุดย่อยของคุณลักษณะส่งผลให้เกิดรูปร่างเชิงพื้นที่ที่แตกต่างกันของกลุ่ม ดังนั้น ความคล้ายคลึงกันระหว่างวัตถุในกลุ่มจึงถูกกำหนดโดยคำนึงถึงรูปแบบความสัมพันธ์ในท้องถิ่น ด้วยแนวคิดนี้ คำดังกล่าวได้รับการแนะนำใน^{[ 14 ]}พร้อมกับแนวคิดที่กล่าวถึงข้างต้น วิธีการต่างๆ สำหรับการจัดกลุ่มความสัมพันธ์ประเภทนี้มีการกล่าวถึงใน^{[ 15 ]}และความสัมพันธ์กับการจัดกลุ่มประเภทต่างๆ ได้รับการกล่าวถึงใน^{[ 16 ]}ดูเพิ่มเติมที่ การจัดกลุ่ม ข้อมูล มิติสูง

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

• การนำไปใช้งานในภาษา Python