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): การเปิดเผยโครงสร้างกลุ่มข้อมูลที่ซ่อนอยู่ก่อนที่จะใช้วิธีการยืนยัน
วิธีการทำงาน
วิธีการทำงาน
จะมีการสร้างเมทริกซ์ความคล้ายคลึง (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)เมทริกซ์ดีกรี (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}จะมีการคำนวณเวกเตอร์ไอเกน k ตัวที่สอดคล้องกับค่าไอเกน k ค่าที่น้อยที่สุดของ L_sym เวกเตอร์ไอเกนเหล่านี้จะประกอบกันเป็นคอลัมน์ของเมทริกซ์การฝังตัว U ซึ่งมีหนึ่งแถวต่อหนึ่งจุดข้อมูล ในปริภูมิสเปกตรัมมิติ k นี้ จุดข้อมูลที่อยู่ในกลุ่มเดียวกันจะถูกดึงเข้าหากัน แม้ว่าเดิมทีจะมีการสลับกันอยู่ในปริภูมิคุณลักษณะเดิมก็ตาม
สูตร
L_{\mathrm{sym}}\, u = \lambda u \quad \Rightarrow \quad U = [u_1,\, u_2,\, \ldots,\, u_k]แต่ละแถวของ 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}จะมีการใช้ 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 วิธีการประมาณเหล่านี้จะให้ความแม่นยำเกือบทั้งหมดโดยใช้ต้นทุนเพียงเศษเสี้ยว
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
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.
เปิดเอกสารอ้างอิงสิ่งพิมพ์คัดลอกแล้วvon Luxburg, U. (2007). A Tutorial on Spectral Clustering. Statistics and Computing, 17, 395–416.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้วShi, J., & Malik, J. (2000). Normalized Cuts and Image Segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8), 888–905.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้ว