K-Means Clustering - Example - USC Upstate Facultyk-均值聚类样本学院USC北部.docVIP

K-Means Clustering – Example We recall from the previous lecture, that clustering allows for unsupervised learning. That is, the machine / software will learn on its own, using the data (learning set), and will classify the objects into a particular class – for example, if our class (decision) attribute is tumorType and its values are: malignant, benign, etc. - these will be the classes. They will be represented by cluster1, cluster2, etc. However, the class information is never provided to the algorithm. The class information can be used later on, to evaluate how accurately the algorithm classified the objects. Curvature Texture Blood Consump Tumor Type x1 0.8 1.2 A Benign x2 0.75 1.4 B Benign x3 0.23 0.4 D Malignant x4 . . 0.23 0.5 D Malignant Curvature Texture Blood Consump Tumor Type x1 0.8 1.2 A Benign x2 0.75 1.4 B Benign x3 0.23 0.4 D Malignant x4 . . 0.23 0.5 D Malignant (learning set) With the K-Means algorithm, we recall it works as follows: Example Problem: Cluster the following eight points (with (x, y) representing locations) into three clusters A1(2, 10) A2(2, 5) A3(8, 4) A4(5, 8) A5(7, 5) A6(6, 4) A7(1, 2) A8(4, 9). Initial cluster centers are: A1(2, 10), A4(5, 8) and A7(1, 2). The distance function between two points a=(x1, y1) and b=(x2, y2) is defined as: ρ(a, b) = |x2 – x1| + |y2 – y1| . Use k-means algorithm to find the three cluster centers after the second iteration. Solution: Iteration 1 (2, 10) (5, 8) (1, 2) Point Dist Mean 1 Dist Mean 2 Dist Mean 3 Cluster A1 (2, 10) A2 (2, 5) A3 (8, 4) A4 (5, 8) A5 (7, 5) A6 (6, 4) A7 (1, 2) A8 (4, 9) First we list all points in the first column of the table above. The initial cluster centers – means, are (2, 10), (5, 8) and (1, 2) - chosen randomly. Next, we will calculate the distance from the first point (2, 10) to each of the three means, by using the distance function: point mean1