Sparsification (การทำให้ Proximity Matrix เบาบาง)
Proximity matrix ขนาด m×m สำหรับ m จุดข้อมูล สามารถมองเป็น dense graph ที่ทุกโหนดเชื่อมต่อกันทุกคู่ และน้ำหนัก edge ระหว่างคู่โหนดสะท้อน pairwise proximity ของพวกเขา แม้ทุกวัตถุจะมีความคล้ายคลึงกับทุกวัตถุ แต่สำหรับชุดข้อมูลส่วนใหญ่ วัตถุคล้ายกับจำนวนน้อยของวัตถุ และคล้อยน้อยกับส่วนใหญ่
ลักษณะนี้ใช้ทำให้ proximity graph (matrix) เบาบาง (sparsify) โดยตั้งค่า low-similarity (high-dissimilarity) เป็น 0 ก่อนเริ่ม clustering จริง Sparsification ทำได้โดย: ตัด links ที่มี similarity (dissimilarity) ต่ำกว่า (สูงกว่า) threshold ที่กำหนด หรือเก็บเฉพาะ links ไปยัง k nearest neighbors ของจุด สร้าง k-nearest neighbor graph
ประโยชน์ของ Sparsification
1. Data size is reduced (ลดขนาดข้อมูล)
ปริมาณข้อมูลที่ต้องประมวลผลเพื่อจัดกลุ่มลดลงมาก Sparsification กำจัด entries ใน proximity matrix ได้มากกว่า 99% ทำให้จัดการปัญหาขนาดใหญ่ได้
2. Clustering may work better (จัดกลุ่มได้ดีขึ้น)
Sparsification เก็บ link ไปยัง nearest neighbors ของวัตถุ ขณะตัด connection ไปยังวัตถุที่แตกต่างมาก สอดคล้องกับ nearest neighbor principle ว่า nearest neighbors ของวัตถุมักอยู่ใน class (cluster) เดียวกับวัตถุ ลดผลกระทบของ noise และ outliers และชัดเจนขอบเขตระหว่าง clusters
3. Graph partitioning algorithms can be used (ใช้ graph partitioning algorithms ได้)
มีงานมากเกี่ยวกับ heuristic algorithms หา min-cut partitionings ของ sparse graphs โดยเฉพาะใน parallel computing และ IC design Sparsification ทำให้ proximity graph ใช้ graph partitioning algorithms ได้ เช่น Opossum และ Chameleon
Sparsification ควรมองเป็นขั้นตอนก่อนการใช้ clustering algorithms จริง Sparsification ที่ดีอาจทำให้ proximity matrix แยกเป็น connected components ตรงกับ clusters ที่ต้องการ แต่ในทางปฏิบัติอาจไม่ค่อยเกิดขึ้นง่าย
มันง่ายที่ edge เดียวจะเชื่อมสองกลุ่ม หรือ cluster เดียวจะแยกเป็นหลาย disconnected subclusters จริงๆ เมื่อ Jarvis-Patrick และ SNN ใช้ density-based clustering sparse proximity graph จะถูกเปลี่ยนให้ได้ proximity graph ใหม่ ซึ่งอาจ sparsified อีก clustering algorithms ทำงานกับ proximity graph ที่เป็นผลลัพธ์ของ preprocessing ทั้งหมด
