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

ในการประยุกต์ใช้กับการแบ่งส่วนภาพ การจัดกลุ่มเชิงสเปกตรัมเรียกว่าการ จำแนกประเภทวัตถุตามการแบ่งส่วน ภาพ

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

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

${\displaystyle L:=DA}$,

เมทริกซ์แนวทแยงอยู่ที่ไหน${\displaystyle D}$

${\displaystyle D_{ii}=\sum _{j}A_{ij},}$

และ A คือ เมทริก ซ์ ประชิด

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

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

เทคนิคการจัดกลุ่มสเปกตรัมแบบนอร์มาไลซ์ที่เป็นที่นิยมคืออัลกอริทึมการตัดแบบนอร์มาไลซ์หรืออัลกอริทึม Shi–Malikที่แนะนำโดย Jianbo Shi และJitendra Malik [ ^{2 ] ซึ่ง}มักใช้สำหรับการแบ่งส่วนภาพโดยจะแบ่งจุดออกเป็นสองชุดตามเวกเตอร์ลักษณะเฉพาะ ที่สอดคล้องกับ ค่าลักษณะเฉพาะที่เล็กที่สุดอันดับสองของLaplacian แบบนอร์มาไลซ์สมมาตรที่กำหนดเป็น ${\displaystyle (B_{1},B_{2})}$${\displaystyle v}$

${\displaystyle L^{\text{norm}}:=ID^{-1/2}AD^{-1/2}.}$

เวกเตอร์นี้ยังเป็นเวกเตอร์ลักษณะเฉพาะ ที่สอดคล้องกับ ค่าลักษณะเฉพาะที่ใหญ่เป็นอันดับสองของ เมทริกซ์ประชิด ที่สมมาตรและปรับให้เป็นมาตรฐานแล้ว${\displaystyle v}$${\displaystyle D^{-1/2}AD^{-1/2}.}$

ลาปลาเซียนแบบนอร์มาไลซ์ (หรือแบบเดินสุ่ม)ถูกกำหนดดังนี้

${\displaystyle L^{\text{rw}}:=D^{-1}L=ID^{-1}A}$

และยังสามารถใช้สำหรับการจัดกลุ่มสเปกตรัมได้อีกด้วย อัลกอริทึมที่เทียบเท่าทางคณิตศาสตร์^{[ 3 ]}จะใช้เวกเตอร์ลักษณะเฉพาะ ที่สอดคล้องกับค่าลักษณะเฉพาะ ที่ใหญ่ที่สุด ของเมทริกซ์ประชิดแบบปกติของการเดินแบบสุ่ม ${\displaystyle u}$${\displaystyle P=D^{-1}A}$

เวกเตอร์ลักษณะเฉพาะของตัวดำเนินการลาปลาเซียนที่สมมาตรและเวกเตอร์ลักษณะเฉพาะของตัวดำเนินการลาปลาเซียนที่ปรับให้เป็นมาตรฐานทางซ้ายมีความสัมพันธ์กันโดยเอกลักษณ์${\displaystyle v}$${\displaystyle u}$${\displaystyle D^{-1/2}v=u.}$

เมื่อทราบเมทริกซ์ขนาด x ของเวกเตอร์ลักษณะเฉพาะที่เลือกแล้ว จะทำการแมป — เรียกว่าการฝังเชิงสเปกตรัม — ของจุดข้อมูลดั้งเดิมไปยังปริภูมิเวกเตอร์มิติโดยใช้แถวของเมทริกซ์นั้นจากนั้น การวิเคราะห์จะลดลงเหลือเพียงการจัดกลุ่มเวกเตอร์ที่มีส่วนประกอบ ซึ่งสามารถทำได้หลายวิธี ${\displaystyle n}$${\displaystyle k}$${\displaystyle V}$${\displaystyle n}$${\displaystyle k}$${\displaystyle V}$${\displaystyle k}$

ในกรณีที่ง่ายที่สุดเวกเตอร์ลักษณะเฉพาะเดี่ยวที่เลือกไว้ซึ่งเรียกว่าเวกเตอร์ Fiedlerนั้น สอดคล้องกับค่าลักษณะเฉพาะที่เล็กที่สุดเป็นอันดับสอง การใช้ส่วนประกอบของเวกเตอร์นี้ ทำให้สามารถจัดวางจุดทั้งหมดที่มีส่วนประกอบเป็นบวกไว้ในเซตและส่วนที่เหลือไว้ในเซต ดังนั้นจึงเป็นการแบ่งกราฟออกเป็นสองส่วน และติดป้ายกำกับจุดข้อมูลด้วยป้ายกำกับสองป้าย วิธีการที่ใช้เครื่องหมายนี้เป็นไปตามคำอธิบายเชิงลึกของการจัดกลุ่มสเปกตรัมผ่านแบบจำลองมวล-สปริง — ในโหมดการสั่นสะเทือนความถี่ต่ำที่เวกเตอร์ Fiedlerแสดงถึง จุดข้อมูลในคลัสเตอร์หนึ่งที่ระบุด้วยมวลที่เชื่อมต่อกันอย่างแน่นหนาจะเคลื่อนที่ไปด้วยกันในทิศทางหนึ่ง ในขณะที่จุดข้อมูลในคลัสเตอร์เสริมที่ระบุด้วยมวลที่เหลือจะเคลื่อนที่ไปด้วยกันในทิศทางตรงกันข้าม อัลกอริทึมนี้สามารถใช้สำหรับการจัดกลุ่มแบบลำดับชั้นโดยการแบ่งส่วนย่อยซ้ำๆ ในลักษณะเดียวกัน ${\displaystyle k=1}$${\displaystyle v}$${\displaystyle v,}$${\displaystyle v}$${\displaystyle B_{+}}$${\displaystyle B_{-}}$${\displaystyle v}$

โดยทั่วไปแล้ว สามารถใช้เทคนิคการ จัด กลุ่มเวกเตอร์แบบใดก็ได้ เช่นDBSCAN${\displaystyle k>1}$

อัลกอริทึมพื้นฐาน

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

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

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

การจัดกลุ่มสเปกตรัมมีความเกี่ยวข้องอย่างใกล้ชิดกับการลดมิติแบบไม่เชิงเส้นและเทคนิคการลดมิติ เช่น การฝังเชิงเส้นเฉพาะที่ สามารถใช้เพื่อลดข้อผิดพลาดจากสัญญาณรบกวนหรือค่าผิดปกติได้^{[ 5 ]}

โดยกำหนดจำนวนจุดข้อมูลด้วยสิ่งสำคัญคือต้องประเมินปริมาณการใช้หน่วยความจำและเวลาในการคำนวณ หรือจำนวนการดำเนินการทางคณิตศาสตร์ (AO) ที่ทำ โดยเป็นฟังก์ชันของไม่ว่าจะเป็นอัลกอริทึมการจัดกลุ่มสเปกตรัมแบบใดก็ตาม สองส่วนที่ใช้ทรัพยากรมากที่สุดคือ การสร้าง Laplacian ของกราฟ และการหาเวกเตอร์ลักษณะเฉพาะสำหรับการฝังสเปกตรัม ขั้นตอนสุดท้าย — การกำหนดป้ายกำกับจากเมทริกซ์เวกเตอร์ลักษณะเฉพาะขนาด x — โดยทั่วไปแล้วจะเป็นขั้นตอนที่ใช้ทรัพยากรน้อยที่สุด โดยต้องการเพียงAO และสร้างเวกเตอร์ป้ายกำกับ ขนาด x ในหน่วยความจำเท่านั้น${\displaystyle n}$${\displaystyle n}$${\displaystyle k}$${\displaystyle n}$${\displaystyle k}$${\displaystyle kn}$${\displaystyle n}$${\displaystyle 1}$

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

เมทริกซ์ลาปลาเซียนของกราฟสามารถสร้างขึ้นได้จากเมทริกซ์ประชิด และโดยทั่วไปจะสร้างขึ้นจากเมทริกซ์ดังกล่าว การสร้างสามารถทำได้โดยไม่ต้องใช้เมทริกซ์ กล่าวคือ โดยไม่ต้องสร้างเมทริกซ์ของเมทริกซ์ลาปลาเซียนของกราฟอย่างชัดเจน และไม่ต้องใช้ AO นอกจากนี้ยังสามารถทำได้แทนที่เมทริกซ์ประชิดโดยไม่เพิ่มการใช้หน่วยความจำ ไม่ว่าจะด้วยวิธีใด ต้นทุนในการสร้างเมทริกซ์ลาปลาเซียนของกราฟนั้นโดยพื้นฐานแล้วจะถูกกำหนดโดยต้นทุนในการสร้างเมทริกซ์ประชิด ขนาด กราฟ${\displaystyle n}$${\displaystyle n}$

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

การสร้าง เมทริกซ์ความประชิดของกราฟแบบง่ายๆเช่น การใช้เคอร์เนล RBF ทำให้เมทริกซ์มีความหนาแน่น จึงต้องใช้หน่วยความจำและAO ในการพิจารณารายการแต่ละรายการของเมทริกซ์ วิธี Nystrom ^{[ 6 ]}สามารถใช้เพื่อประมาณเมทริกซ์ความคล้ายคลึงกันได้ แต่เมทริกซ์โดยประมาณนั้นไม่เป็นบวกทุกองค์ประกอบ^{[ 7 ]}กล่าวคือไม่สามารถตีความได้ว่าเป็นความคล้ายคลึงกันตามระยะทาง ${\displaystyle n^{2}}$${\displaystyle n^{2}}$${\displaystyle n^{2}}$

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

โดยปกติแล้ว ต้นทุนในการคำนวณเมทริกซ์ขนาด-by- (โดยที่) ของเวกเตอร์ลักษณะเฉพาะที่เลือกไว้ของกราฟลาปลาเซียนจะเป็นสัดส่วนกับต้นทุนในการคูณเมท ริกซ์กราฟลาปลาเซียนขนาด -by- ด้วยเวกเตอร์ ซึ่งจะแตกต่างกันอย่างมากไม่ว่าเมทริกซ์กราฟลาปลาเซียนจะเป็นเมทริกซ์หนาแน่นหรือเมทริกซ์เบาบาง สำหรับกรณีหนาแน่น ต้นทุนจึงเป็นต้นทุนที่อ้างถึงกันบ่อยมากในเอกสารทางวิชาการมาจากการเลือกและเห็นได้ชัดว่าทำให้เข้าใจผิด เนื่องจากตัวอย่างเช่น ในการจัดกลุ่มสเปกตรัมแบบลำดับชั้นตามที่กำหนดโดย เวก เตอร์ Fiedler${\displaystyle n}$${\displaystyle k}$${\displaystyle k\ll n}$${\displaystyle n}$${\displaystyle n}$${\displaystyle O(n^{2})}$${\displaystyle O(n^{3})}$${\displaystyle k=n}$${\displaystyle k=1}$

ในกรณีที่เมทริกซ์ Laplacian ของกราฟขนาด-by- มี ค่าไม่เป็นศูนย์ ต้นทุนของการคูณเมทริกซ์กับเวกเตอร์ และด้วยเหตุนี้ ต้นทุนของการคำนวณเมท ริกซ์ ขนาด-by- ของเวกเตอร์ลักษณะเฉพาะที่เลือกไว้ คือโดยที่การใช้หน่วยความจำก็มีเพียง— ซึ่งทั้งสองอย่างนี้เป็นขอบเขตล่างที่เหมาะสมที่สุดของความซับซ้อนของจุดข้อมูลการจัดกลุ่ม ยิ่งไปกว่านั้น ตัวแก้ค่าลักษณะเฉพาะแบบไม่มีเมทริกซ์ เช่นLOBPCGสามารถทำงานแบบขนานได้อย่างมีประสิทธิภาพ เช่น บนGPU หลายตัว ที่มีหน่วยความจำแบบกระจาย ส่งผลให้ไม่เพียงแต่ได้คลัสเตอร์คุณภาพสูง ซึ่งเป็นสิ่งที่การจัดกลุ่มสเปกตรัมมีชื่อเสียง แต่ยังได้ประสิทธิภาพสูงสุดอีกด้วย^{[ 8 ]}${\displaystyle n}$${\displaystyle n}$${\displaystyle O(n)}$${\displaystyle n}$${\displaystyle k}$${\displaystyle k\ll n}$${\displaystyle O(n)}$${\displaystyle O(n)}$${\displaystyle n}$

ซอฟต์แวร์ฟรีที่ใช้การจัดกลุ่มสเปกตรัมมีให้บริการในโครงการโอเพนซอร์สขนาดใหญ่ เช่นscikit-learn ^{[ 9 ]}โดยใช้LOBPCG ^{[ 10 ]}พร้อมการปรับสภาพล่วงหน้าแบบมัลติกริด^{[ 11 ] [ 12 ]}หรือARPACK , MLlib สำหรับการ ^จัดกลุ่มเวกเตอร์เสมือนโดยใช้วิธีการวนซ้ำกำลัง^{[ 13 ]}และR [ ^{14 ]}

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

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

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

ในทางคณิตศาสตร์ ฟังก์ชันวัตถุประสงค์ที่ลดค่าลงโดยการจัดกลุ่มสเปกตรัมสามารถแสดงให้เห็นว่าเทียบเท่ากับฟังก์ชันวัตถุประสงค์ของ k-means เคอร์เนลแบบถ่วงน้ำหนักในพื้นที่ที่แปลงแล้วนี้ ซึ่งได้รับการพิสูจน์อย่างเป็นทางการในงานต่างๆ เช่น^{[ 16 ]}โดยแสดงให้เห็นว่าการตัดแบบนอร์มาไลซ์เทียบเท่ากับ k-means เคอร์เนลแบบถ่วงน้ำหนักที่ใช้กับแถวของเมทริกซ์เวกเตอร์ลักษณะเฉพาะของ Laplacian แบบนอร์มาไลซ์

เนื่องจากความเท่าเทียมกันนี้การจัดกลุ่มแบบสเปกตรัมจึงสามารถมองได้ว่าเป็นการดำเนินการ k-means แบบเคอร์เนลในปริภูมิไอเกนที่กำหนดโดยลาปลาเซียนของกราฟความเข้าใจเชิงทฤษฎีนี้มีนัยสำคัญในทางปฏิบัติ: ขั้นตอนการจัดกลุ่มขั้นสุดท้ายในการจัดกลุ่มแบบสเปกตรัมโดยทั่วไปเกี่ยวข้องกับการเรียกใช้ขั้นตอนวิธี k-means มาตรฐานบนแถวของเมทริกซ์ที่สร้างขึ้นจากเวกเตอร์ไอเกน k ตัวแรกของลาปลาเซียน แถวเหล่านี้สามารถคิดได้ว่าเป็นการฝังจุดข้อมูลหรือโหนดแต่ละจุดลงในพื้นที่มิติที่ต่ำกว่า ซึ่งกลุ่มต่างๆ จะแยกออกจากกันได้ดีกว่า และด้วยเหตุนี้จึงง่ายต่อการตรวจจับโดย k-means

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

การจัดกลุ่มสเปกตรัมยังมีความสัมพันธ์เชิงแนวคิดกับDBSCAN (การจัดกลุ่มเชิงพื้นที่ตามความหนาแน่นของแอปพลิเคชันที่มีสัญญาณรบกวน) โดยเฉพาะอย่างยิ่งในกรณีพิเศษที่ใช้วิธีสเปกตรัมเพื่อระบุส่วนประกอบกราฟที่เชื่อมต่อกัน ของกราฟ ในกรณีที่เรียบง่ายนี้—ซึ่งเป้าหมายคือการระบุกลุ่มย่อยของโหนดที่ไม่มีขอบเชื่อมต่อระหว่างกัน—วิธีสเปกตรัมจะลดลงเหลือเพียงวิธีการจัดกลุ่มตามการเชื่อมต่อ ซึ่งคล้ายกับ DBSCAN ^{[ 18 ]}

DBSCAN ทำงานโดยการระบุบริเวณที่มีการเชื่อมต่อกันด้วยความหนาแน่นในพื้นที่อินพุต: จุดที่สามารถเข้าถึงกันได้ผ่านลำดับของจุดข้างเคียงภายในรัศมีที่กำหนด (ε) และมีจำนวนจุดขั้นต่ำ (minPts) อยู่ภายใน อัลกอริทึมนี้มีความโดดเด่นในการค้นหาคลัสเตอร์ที่มีรูปร่างใดๆ ก็ได้ และแยกสัญญาณรบกวนโดยไม่จำเป็นต้องระบุจำนวนคลัสเตอร์ล่วงหน้า

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

ความเชื่อมโยงนี้เห็นได้ชัดเจนที่สุดเมื่อใช้การจัดกลุ่มแบบสเปกตรัม ไม่ใช่เพื่อปรับพาร์ติชันแบบอ่อนให้เหมาะสมที่สุด (เช่น การลดค่าการตัดแบบนอร์มาไลซ์ให้เหลือน้อยที่สุด) แต่เพื่อระบุส่วนประกอบที่เชื่อมต่อกันอย่างแม่นยำซึ่งสอดคล้องกับรูปแบบที่รุนแรงที่สุดของการจัดกลุ่มแบบ "อิงความหนาแน่น" โดยที่เฉพาะโหนดที่เชื่อมต่อกันโดยตรงหรือโดยอ้อมเท่านั้นที่จะถูกจัดกลุ่มเข้าด้วยกัน ดังนั้น การจัดกลุ่มแบบสเปกตรัมในระบอบนี้จึงมีพฤติกรรมคล้ายกับDBSCAN เวอร์ชันสเปกตรัมโดยเฉพาะอย่างยิ่งในกราฟแบบเบาบางหรือเมื่อสร้างกราฟ ε-neighborhood

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

Ravi Kannan, Santosh Vempala และ Adrian Vetta ^{[ 19 ]}เสนอการวัดแบบสองเกณฑ์เพื่อกำหนดคุณภาพของการจัดกลุ่มที่กำหนด พวกเขากล่าวว่าการจัดกลุ่มเป็นการจัดกลุ่มแบบ (α, ε) หากค่าการนำไฟฟ้าของแต่ละกลุ่ม (ในการจัดกลุ่ม) มีค่าอย่างน้อย α และน้ำหนักของขอบระหว่างกลุ่มมีค่าไม่เกิน ε เศษส่วนของน้ำหนักรวมของขอบทั้งหมดในกราฟ พวกเขายังพิจารณาอัลกอริทึมการประมาณค่าสองแบบในเอกสารเดียวกันด้วย

การจัดกลุ่มสเปกตรัมมีประวัติยาวนาน^{[ 20 ] [ 21 ] [ 22 ] [ 23 ] [ 24 ] [ 2 ] [ 25 ]}การจัดกลุ่มสเปกตรัมในฐานะ วิธี การเรียนรู้ของเครื่องได้รับความนิยมจาก Shi & Malik ^{[ 2 ]}และ Ng, Jordan, & Weiss ^{[ 25 ]}

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

• การแพร่กระจายความสัมพันธ์
• การวิเคราะห์ส่วนประกอบหลักของเคอร์เนล
• การวิเคราะห์คลัสเตอร์
• ทฤษฎีกราฟสเปกตรัม