Skip to content
กลับไปยังผลการค้นหา

Spectral Clustering

ผู้เสนอ
Ng, A. Y.; Jordan, M. I.; Weiss, Y.
ปี
2002
ประเภท
Graph-based clustering (spectral method)

ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ

ขนาดตัวอักษร

ใช้ทำอะไร?

Spectral Clustering เป็นอัลกอริทึมการเรียนรู้แบบไม่มีผู้สอน (unsupervised learning) ที่อิงตามกราฟ ซึ่งถูกพัฒนาอย่างเป็นระบบโดย Ng, Jordan, และ Weiss ในปี 2002 โดยทำการแปลงข้อมูลให้อยู่ในปริภูมิไอเกน (eigenspace) มิติ ต่ำ ที่ได้มาจาก Laplacian ของกราฟความคล้ายคลึง (similarity graph) ก่อนที่จะนำไปใช้กับ k-means การฝังตัวแบบสเปกตรัม (spectral embedding) นี้ทำให้สามารถค้นพบกลุ่มข้อมูลที่มีรูปร่างซับซ้อนได้ เช่น วงแหวน, รูปพระจันทร์เสี้ยว, หรือเกลียวที่พันกัน ซึ่งวิธีการที่ใช้ระยะทางแบบยุคลิด (Euclidean distance) มักจะล้มเหลวในการแยกแยะ

แนวคิดเบื้องหลังวิธีการ

k-means แบบมาตรฐานจะแบ่งปริภูมิโดยใช้ระยะทางที่เป็นเส้นตรง ดังนั้นจึงสามารถค้นพบได้เฉพาะกลุ่มข้อมูลที่มีลักษณะนูน (convex) และมีรูปร่างคล้ายทรงกลมเท่านั้น Spectral Clustering จะข้ามข้อจำกัดนี้ไปโดยการพิจารณาข้อมูลเสมือนเป็นเครือข่าย: แต่ละจุดคือโหนด (node) และเส้นเชื่อมระหว่างโหนดจะมีการถ่วงน้ำหนักที่สะท้อนถึงความคล้ายคลึงกันของทั้งสองจุด กลุ่มข้อมูลจะสอดคล้องกับบริเวณในเครือข่ายที่มีการเชื่อมต่อกันอย่างหนาแน่นภายใน แต่มีการเชื่อมต่อกันอย่างหลวมๆ กับส่วนอื่นๆ เมทริกซ์กราฟ Laplacian (graph Laplacian matrix) จะเข้ารหัสโครงสร้างการเชื่อมต่อนี้ และเวกเตอร์ไอเกน (eigenvectors) ที่มีค่าน้อยที่สุดของมันจะทำหน้าที่เหมือนระบบพิกัดที่ราบรื่น ซึ่งจะยืดข้อมูลออกไปเพื่อให้กลุ่มข้อมูลที่แยกจากกันได้ดีอยู่ห่างกัน แม้ว่าเดิมทีจะพันกันอยู่ก็ตาม จากนั้น การใช้ k-means อย่างง่ายในระบบพิกัดใหม่นี้จะสามารถแยกกลุ่มข้อมูลได้อย่างชัดเจน

ประวัติศาสตร์

รากฐานทางทฤษฎีของ spectral clustering สืบย้อนไปถึงงานของ Fiedler ในปี 1973 เกี่ยวกับการเชื่อมต่อของกราฟและค่าไอเกนของการเชื่อมต่อเชิงพีชคณิต (algebraic connectivity) Shi และ Malik (2000) ได้นำแนวทางนี้มาสู่การประมวลผลภาพผ่านเกณฑ์ normalized-cuts สำหรับการแบ่งส่วนภาพ Ng, Jordan, และ Weiss (2002) ได้นำเสนอขั้นตอนวิธีที่ชัดเจนและใช้งานได้ทั่วไปในงาน NIPS ซึ่งเป็นวิธีที่มักถูกอ้างอิงมากที่สุดในปัจจุบัน พร้อมกับการวิเคราะห์ทฤษฎีการรบกวน (perturbation-theoretic analysis) ที่อธิบายว่าทำไมและเมื่อใดที่วิธีการนี้จึงได้ผล บทความทบทวนของ Von Luxburg ในปี 2007 ในวารสาร Statistics and Computing ได้รวบรวมสูตรที่แข่งขันกัน ชี้แจงบทบาทของการทำให้ Laplacian เป็นมาตรฐาน และกลายเป็นเอกสารอ้างอิงมาตรฐานสำหรับผู้ปฏิบัติงาน Spectral clustering ปัจจุบันมีบทบาทสำคัญในหลักสูตรการเรียนรู้ของเครื่อง (machine learning) และยังคงเป็นหัวข้อวิจัยที่เคลื่อนไหว โดยมีการทำงานอย่างต่อเนื่องเกี่ยวกับวิธีการประมาณที่ปรับขนาดได้ เคอร์เนลที่ทนทาน และการขยายไปยังกราฟและแมนิโฟลด์

ควรใช้เมื่อใด

Spectral Clustering เหมาะอย่างยิ่งเมื่อกลุ่มข้อมูลมีรูปร่างที่ไม่ใช่แบบนูน (non-convex) ไม่สามารถแยกเชิงเส้นได้ (non-linearly separable) หรือเชื่อมต่อกันด้วยสะพานบางๆ ที่วิธีการแบ่งแบบยุคลิดไม่สามารถตรวจจับได้ — ตัวอย่างทั่วไป ได้แก่ กลุ่มข้อมูลรูปวงแหวน, เกลียวที่พันกัน, และส่วนของภาพ มันเหมาะสมเมื่อสามารถคำนวณความคล้ายคลึงแบบคู่ (pairwise similarity) ระหว่างจุดได้อย่างมีความหมาย (ไม่ว่าจะจากเคอร์เนลบนคุณลักษณะดิบ หรือจากเมทริกซ์ความสัมพันธ์ที่ให้มาก่อน) และเมื่อจำนวนกลุ่มข้อมูล k เป็นที่ทราบ หรือสามารถประมาณได้จากหลักการ eigengap heuristic วิธีการนี้ไม่ต้องการสมมติฐานเกี่ยวกับการแจกแจงของรูปร่างกลุ่มข้อมูล ข้อจำกัดในการใช้งานจริง ได้แก่ หน่วยความจำที่เป็นกำลังสองของจำนวนจุด (สำหรับเมทริกซ์ความสัมพันธ์เต็ม) และเวลาที่เป็นกำลังสามสำหรับการหาค่าไอเกน (eigendecomposition) ทำให้สูตรมาตรฐานมีค่าใช้จ่ายสูงเกินกว่าประมาณ 10,000 จุด วิธีการประมาณ (Nystrom, sparse graphs, randomized SVD) จะช่วยขยายขอบเขตการใช้งานไปยังชุดข้อมูลที่ใหญ่ขึ้น

ข้อจำกัดและข้อควรพิจารณา

  • การสร้างเมทริกซ์ความสัมพันธ์ n x n เต็มรูปแบบต้องใช้หน่วยความจำ O(n^2) และเวลา O(n^3) สำหรับการหาค่าไอเกน ทำให้ขั้นตอนวิธีแบบตรงไปตรงมาไม่สามารถใช้งานได้สำหรับชุดข้อมูลขนาดใหญ่
  • ผลลัพธ์มีความอ่อนไหวต่อการเลือกแบนด์วิดท์เคอร์เนล sigma และกลยุทธ์การสร้างกราฟ การเลือกที่ไม่ดีอาจทำให้กลุ่มข้อมูลรวมกันหรือแยกออกจากกัน
  • การเริ่มต้น k-means ใน spectral embedding มีการสุ่ม ดังนั้นการรันหลายครั้งอาจให้ผลการแบ่งกลุ่มที่แตกต่างกัน
  • ไม่สามารถปรับขนาดได้อย่างเหมาะสมกับปริภูมิคุณลักษณะที่มีมิติสูงมาก หากไม่มีการเลือกเคอร์เนลอย่างระมัดระวัง
  • ให้เฉพาะป้ายกลุ่มเท่านั้น ไม่ได้ให้แบบจำลองเชิงกำเนิด (generative model) และไม่มีการขยายไปยังจุดข้อมูลใหม่ตามธรรมชาติ (out-of-sample extension)

เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้

จุดแข็ง

  • ตรวจจับกลุ่มข้อมูลที่มีรูปร่างตามอำเภอใจ รวมถึงการกำหนดค่าที่ไม่ใช่แบบนูนและไม่สามารถแยกเชิงเส้นได้ ซึ่งทำให้ k-means และ Gaussian mixture models ล้มเหลว
  • สามารถทำงานกับเมทริกซ์ความคล้ายคลึงแบบคู่ใดก็ได้ ไม่ใช่แค่ระยะทางยุคลิด ทำให้สามารถนำไปใช้กับกราฟ สตริง และข้อมูลที่มีโครงสร้างอื่นๆ ได้
  • หลักการ eigengap heuristic ให้แนวทางที่มีหลักการและขับเคลื่อนด้วยข้อมูลสำหรับการเลือกจำนวนกลุ่มข้อมูล k
  • มีรากฐานมาจากทฤษฎีกราฟสเปกตรัม (spectral graph theory) ที่สมบูรณ์ ทำให้สามารถวิเคราะห์การลู่เข้า (convergence) และคุณภาพของกลุ่มข้อมูลได้อย่างเป็นทางการ
  • มีความเข้าใจง่ายและสามารถนำไปใช้งานได้ง่ายโดยใช้ไลบรารีพีชคณิตเชิงเส้นมาตรฐาน

การประยุกต์ใช้

  • การแบ่งส่วนภาพ (Image segmentation): การแบ่งพิกเซลหรือ superpixels ออกเป็นบริเวณที่สอดคล้องกันตามการรับรู้ โดยใช้ความคล้ายคลึงของคุณลักษณะระดับพิกเซล
  • การตรวจจับชุมชน (Community detection) ในเครือข่ายสังคมและชีวภาพ ซึ่งการเชื่อมต่อแบบคู่มีความสำคัญมากกว่าเวกเตอร์คุณลักษณะในการกำหนดโครงสร้าง
  • ชีวสารสนเทศศาสตร์ (Bioinformatics): การจัดกลุ่มยีนหรือโปรตีนตามความคล้ายคลึงของโปรไฟล์การแสดงออก (expression profile similarity) ซึ่งกลุ่มการแสดงออกมักจะไม่ใช่แบบนูนในปริภูมิยีน
  • การประมวลผลภาษาธรรมชาติ (Natural language processing): การจัดกลุ่มเอกสารหรือประโยคโดยใช้เคอร์เนลความคล้ายคลึงเชิงความหมาย (semantic similarity kernels)
  • คอมพิวเตอร์วิทัศน์ (Computer vision): การแบ่งส่วนการเคลื่อนไหว (motion segmentation) และการแบ่งกลุ่มจุดเมฆ (point-cloud partitioning) ซึ่งขอบเขตของกลุ่มข้อมูลมีความไม่สม่ำเสมอ
  • การวิเคราะห์ข้อมูลเชิงสำรวจ (Exploratory data analysis): การเปิดเผยโครงสร้างกลุ่มข้อมูลที่ซ่อนอยู่ก่อนที่จะใช้วิธีการยืนยัน

วิธีการทำงาน

วิธีการทำงาน

1

จะมีการสร้างเมทริกซ์ความคล้ายคลึง (affinity matrix) แบบคู่ (pairwise similarity) W จากข้อมูล ตัวเลือกที่ใช้กันมากที่สุดคือ Gaussian (RBF) kernel ซึ่งจะกำหนดน้ำหนักสูงให้กับคู่ที่อยู่ใกล้กัน และน้ำหนักใกล้ศูนย์ให้กับคู่ที่อยู่ห่างกัน พารามิเตอร์แบนด์วิดท์ (bandwidth parameter) sigma จะควบคุมอัตราการลดลงของความคล้ายคลึงตามระยะทาง การเลือกค่านี้อย่างเหมาะสมเป็นสิ่งสำคัญยิ่ง นอกจากนี้ ยังสามารถใช้กราฟ k-nearest-neighbour (k-NN) เพื่อการแสดงผลที่เบาบางขึ้นสำหรับชุดข้อมูลขนาดใหญ่

สูตร
W_{ij} = \exp\!\left(-\frac{\|x_i - x_j\|^2}{2\sigma^2}\right)
2

เมทริกซ์ดีกรี (degree matrix) D คือเมทริกซ์ทแยงมุมที่สมาชิกในแนวทแยงมุมที่ i คือผลรวมของแถวที่ i ของ W จาก W และ D จะมีการสร้าง normalized (symmetric) graph Laplacian L_sym เมทริกซ์นี้จะเก็บโครงสร้างการเชื่อมต่อทั้งหมดของกราฟความคล้ายคลึง สเปกตรัมของค่าไอเกน (eigenvalue spectrum) ของมันจะเปิดเผยจำนวนกลุ่มข้อมูลตามธรรมชาติที่มีอยู่ และระดับการแยกออกจากกันอย่างชัดเจน

สูตร
L_{\mathrm{sym}} = D^{-1/2}(D - W)D^{-1/2} = I - D^{-1/2}W D^{-1/2}
3

จะมีการคำนวณเวกเตอร์ไอเกน k ตัวที่สอดคล้องกับค่าไอเกน k ค่าที่น้อยที่สุดของ L_sym เวกเตอร์ไอเกนเหล่านี้จะประกอบกันเป็นคอลัมน์ของเมทริกซ์การฝังตัว U ซึ่งมีหนึ่งแถวต่อหนึ่งจุดข้อมูล ในปริภูมิสเปกตรัมมิติ k นี้ จุดข้อมูลที่อยู่ในกลุ่มเดียวกันจะถูกดึงเข้าหากัน แม้ว่าเดิมทีจะมีการสลับกันอยู่ในปริภูมิคุณลักษณะเดิมก็ตาม

สูตร
L_{\mathrm{sym}}\, u = \lambda u \quad \Rightarrow \quad U = [u_1,\, u_2,\, \ldots,\, u_k]
4

แต่ละแถวของ U จะถูกหารด้วยนอร์มยุคลิด (Euclidean norm) ของมัน เพื่อฉายจุดที่ถูกฝังตัวลงบนไฮเปอร์สเฟียร์หนึ่งหน่วย (unit hypersphere) การทำให้เป็นมาตรฐาน (normalization) นี้ ซึ่งนำเสนอโดย Ng, Jordan, และ Weiss จะกำจัดความแตกต่างของสเกลที่ไม่แท้จริงระหว่างเวกเตอร์ไอเกน และทำให้แน่ใจว่าขั้นตอน k-means ที่ตามมาจะมุ่งเน้นไปที่โครงสร้างเชิงมุม (angular structure) ของการฝังตัว แทนที่จะเป็นขนาด (magnitude)

สูตร
T_{ij} = U_{ij} \Big/ \left(\sum_{j'} U_{ij'}^2\right)^{1/2}
5

จะมีการใช้ k-means clustering แบบมาตรฐานกับแถวของเมทริกซ์การฝังตัวที่ทำให้เป็นมาตรฐานแล้ว T เนื่องจาก spectral embedding ได้ทำการคลายโครงสร้างทางเรขาคณิตของกลุ่มข้อมูลแล้ว k-means จึงสามารถค้นหาการแบ่งกลุ่มที่มีความหมายได้ แม้สำหรับรูปร่างกลุ่มข้อมูลที่ไม่ใช่แบบนูน (non-convex) จากนั้นป้ายกลุ่ม (cluster labels) จะถูกแมปกลับไปยังจุดข้อมูลดั้งเดิม

ข้อผิดพลาดที่พบบ่อย

  • การเลือก sigma โดยไม่มีการตรวจสอบไขว้ (cross-validation) หรือการปรับแต่งด้วยตนเองตามหลักการ แบนด์วิดท์ที่เล็กเกินไปจะสร้างกราฟที่ขาดการเชื่อมต่อ ในขณะที่แบนด์วิดท์ที่ใหญ่เกินไปจะรวมกลุ่มที่แตกต่างกัน
  • การละเลยการทำให้แถวของเมทริกซ์ความสัมพันธ์เป็นมาตรฐานก่อนใช้ k-means (ขั้นตอนการทำให้แถวเป็นมาตรฐานของ Ng et al. มีความสำคัญต่อเสถียรภาพ)
  • การละเลย eigengap: การใช้ k ที่กำหนดไว้โดยไม่ได้ตรวจสอบสเปกตรัมของค่าไอเกน มักจะนำไปสู่การแบ่งกลุ่มที่น้อยเกินไปหรือมากเกินไป
  • การใช้ขั้นตอนวิธีเต็มรูปแบบกับชุดข้อมูลที่มีจุดข้อมูลหลายหมื่นจุดโดยไม่ได้เปลี่ยนไปใช้วิธีการประมาณหรือวิธีแบบเบาบาง
  • การสับสนระหว่าง Laplacian ที่ไม่ได้ทำให้เป็นมาตรฐาน (L = D - W) และที่ทำให้เป็นมาตรฐานแล้ว (L_sym, L_rw) ซึ่งอาจเปลี่ยนแปลงการกำหนดกลุ่มข้อมูลได้อย่างมาก

คำถามที่พบบ่อย

ฉันจะเลือกจำนวนกลุ่มข้อมูล k ได้อย่างไร?

หลักการ eigengap heuristic คือแนวทางมาตรฐาน: คำนวณค่าไอเกนของ normalized Laplacian ตามลำดับจากน้อยไปมาก และมองหาช่องว่างที่ใหญ่ที่สุดระหว่างค่าไอเกนที่อยู่ติดกัน ดัชนีที่ช่องว่างนี้เกิดขึ้นจะบ่งชี้ถึงจำนวนกลุ่มข้อมูลตามธรรมชาติ เมื่อ eigengap ไม่ชัดเจน วิธีการที่อิงตามเสถียรภาพ (stability-based approaches) — การรันอัลกอริทึมสำหรับค่า k หลายค่าและเปรียบเทียบการกำหนดกลุ่มข้อมูลภายใต้การรบกวนต่างๆ — สามารถช่วยได้

ฉันควรตั้งค่าแบนด์วิดท์เคอร์เนล Gaussian sigma อย่างไร?

หลักการทั่วไปที่ใช้กันคือค่ามัธยฐานของระยะทางแบบคู่ในชุดข้อมูล หรือรูปแบบการปรับแต่งตนเองแบบเพื่อนบ้านใกล้สุด (nearest-neighbour self-tuning scheme) (Zelnik-Manor & Perona, 2004) ซึ่งกำหนดแบนด์วิดท์เฉพาะที่ให้กับแต่ละจุด ในทางปฏิบัติ ควรตรวจสอบ sigma โดยการตรวจสอบการเชื่อมต่อของกราฟความสัมพันธ์ที่ได้: แต่ละจุดควรมีเพื่อนบ้านที่มีน้ำหนักสูงอย่างน้อยสองสามจุด และกราฟไม่ควรแตกออกเป็นส่วนประกอบที่แยกจากกัน

เหตุใดขั้นตอนการทำให้แถวเป็นมาตรฐานจึงจำเป็น?

เวกเตอร์ไอเกนของ Laplacian อาจมีความแตกต่างกันอย่างมากในเรื่องสเกล หากไม่มีการทำให้แต่ละแถวของเมทริกซ์การฝังตัวมีขนาดเป็นหนึ่งหน่วย ขั้นตอน k-means อาจถูกครอบงำโดยเวกเตอร์ไอเกนที่มีขนาดใหญ่ และละเลยส่วนประกอบที่มีข้อมูลแต่มีขนาดเล็กกว่า การทำให้แถวเป็นมาตรฐานที่นำเสนอโดย Ng, Jordan, และ Weiss จะแมปจุดทั้งหมดไปยังทรงกลมหนึ่งหน่วย เพื่อให้ k-means ตอบสนองต่อเรขาคณิตเชิงมุมของการฝังตัว

Spectral clustering สามารถจัดการกับชุดข้อมูลขนาดใหญ่มากได้หรือไม่?

ในรูปแบบตรงไปตรงมาไม่ได้ เนื่องจากต้องใช้หน่วยความจำ O(n^2) และเวลา O(n^3) สำหรับการหาค่าไอเกน สำหรับ n ที่มีค่ามาก วิธีแก้ไขมาตรฐาน ได้แก่: การสร้างกราฟ k-nearest-neighbour แบบเบาบางแทนเมทริกซ์ความสัมพันธ์เต็ม; การใช้การประมาณค่า Nystrom เพื่อประมาณเวกเตอร์ไอเกนจากกลุ่มตัวอย่างย่อย; หรือการใช้ randomized SVD วิธีการประมาณเหล่านี้จะให้ความแม่นยำเกือบทั้งหมดโดยใช้ต้นทุนเพียงเศษเสี้ยว

วิธีการที่เกี่ยวข้อง

แหล่งอ้างอิง

  1. Ng, A. Y., Jordan, M. I., & Weiss, Y. (2002). On Spectral Clustering: Analysis and an Algorithm. Advances in Neural Information Processing Systems, 14, 849–856.

    เปิดเอกสารอ้างอิงสิ่งพิมพ์
    คัดลอกแล้ว
  2. von Luxburg, U. (2007). A Tutorial on Spectral Clustering. Statistics and Computing, 17, 395–416.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว
  3. Shi, J., & Malik, J. (2000). Normalized Cuts and Image Segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8), 888–905.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว