Agglomerative Clustering Algorithm
Agglomerative clustering เป็น bottom-up clustering method ที่ clusters มี subclusters ซึ่งต่อไปมี sub-clusters เริ่มต้นโดยวางแต่ละ object ใน cluster ของตัวเอง แล้วผสม atomic clusters เหล่านี้เป็น larger และ larger clusters จนกว่า all objects จะอยู่ใน single cluster หรือถึง termination condition ที่กำหนด บาง hierarchical clustering methods ใช้ประเภทนี้ แตกต่างกันแค่ definition of between-cluster similarity
ตัวอย่าง: AGNES (Agglomerative Nesting)
ใช้ single-link techniques ทำงาน: สมมติมีกลุ่ม objects วางใน rectangle เริ่มต้นทุก object อยู่ใน cluster ของตัวเอง แล้ว clusters ถูกรวมทีละขั้นตอน ตาม principle เช่น รวม clusters ที่มี minimum Euclidean distance ระหว่าง nearest objects ใน cluster
เปรียบเทียบกับ K-means
K-means เริ่มต้นด้วย fixed number of clusters และ allocate all data into exactly that many clusters อีก class ของ approaches ทำงานด้วย agglomeration เริ่มต้นทุก data point เป็น cluster ของตัวเอง และ gradually combine เข้า larger clusters จนกว่า all points จะรวมเป็น one large cluster
ขั้นตอนการทำงาน
- สร้าง similarity matrix: ตาราง pairwise distances หรือ degrees of similarity ระหว่าง clusters เริ่มต้น similarity matrix มี pairwise distances ระหว่าง single pairs of records
- มี measures of similarity หลายอย่าง: Euclidean distance, angle between vectors, ratio of connecting to non-connecting categorical fields
- กับ N original clusters สำหรับ N data points ต้องการ N² distance computations สำหรับ distance table ถ้า similarity measure เป็น true distance metric ต้องการแค่ครึ่งเพราะ Distance(X,Y) = Distance(Y,X) ในคณิตศาสตร์ matrix เป็น lower triangular
- หาค่าน้อยที่สุดใน similarity matrix: ระบุ two clusters ที่ most similar รวมเป็น cluster ใหม่ และ update similarity matrix โดยแทนที่ two rows ที่ represent parent clusters ด้วย new row ที่ represent distance ระหว่าง merged cluster และ remaining clusters
- ตอนนี้มี N-1 clusters และ N-1 rows ใน similarity matrix Iterate merge step N-1 ครั้ง จน all data 属于 same large cluster แต่ละ iteration ระบุว่า clusters ไหนถูกรวม และ distance ระหว่างพวกเขา ข้อมูลนี้決定 clustering method ที่ใช้
