機器學習十大經典算法之K-Means聚類算法

聚類介紹

聚類在機器學習，數據挖掘，模式識別，圖像分析以及生物信息等領域有廣泛的應用。聚類是把相似的對象通過靜態分類的方法分成不同的組別或者更多的子集（subset），這樣讓在同一個子集中的成員對象都有相似的一些屬性，常見的包括在坐標系中更加短的空間距離（一般是歐式距離）等。

聚類的應用

在商務上，聚類能幫助市場分析人員從客戶基本庫中發現不同的客戶群，并且用購買模式來刻畫不同的客戶群的特征。在生物學上，聚類能用于推導植物和動物的分類，對基因進行分類，獲得對種群中固有結構的認識。聚類在地球觀測數據庫中相似地區的確定，汽車保險單持有者的分組，及根據房子的類型、價值和地理位置對一個城市中房屋的分組上也可以發揮作用。聚類也能用于對Web上的文檔進行分類，以發現信息。諸如此類，聚類有著廣泛的實際應用。

K-Means聚類算法簡介

K-Means是發現給定數據集的 K 個簇的聚類算法, 之所以稱之為 K-均值是因為它可以發現 K 個不同的簇, 且每個簇的中心采用簇中所含值的均值計算而成。簇個數 K 是用戶指定的, 每一個簇通過其質心（centroid）, 即簇中所有點的中心來描述。聚類與分類算法的最大區別在于, 分類的目標類別已知, 而聚類的目標類別是未知的。

K-Means聚類算法步驟

K-Means聚類步驟是一個循環迭代的算法，具體·步驟如下：

1、先隨機選取K個對象作為初始的聚類中心，隨機選擇K個初始中心點；

2、計算每個對象與各個種子聚類中心之間的距離，按照距離初始中心點最小的原則，把每個對象分配給距離它最近的聚類中心。聚類中心以及分配給它們的對象就代表一個聚類。

3、一旦全部對象都被分配了，每個聚類的聚類中心會根據聚類中現有的對象被重新計算。這個過程將不斷重復直到滿足某個終止條件。終止條件可以是以下任何一個：

1）沒有（或最小數目）對象被重新分配給不同的聚類。

2）沒有（或最小數目）聚類中心再發生變化。

3）誤差平方和局部最小。

因此得到相互分離的球狀聚類，在這些聚類中，均值點趨向收斂于聚類中心。 一般會希望得到的聚類大小大致相當，這樣把每個觀測都分配到離它最近的聚類中心（即均值點）就是比較正確的分配方案。

K-Means的數學描述

聚類是把相似的物體聚在一起，這個相似度（或稱距離）是用歐氏距離來衡量的。

給定兩個樣本 X = ( x 1 , x 2 , . . . , x n ) X=(x_{1},x_{2},...,x_{n}) X=(x1 ,x2 ,...,xn ) 與 Y = ( y 1 , y 2 , . . . , y n ) Y=(y_{1},y_{2},...,y_{n}) Y=(y1 ,y2 ,...,yn ) ，其中n表示特征數 ，X和Y兩個向量間的歐氏距離(Euclidean Distance)表示為：

d i s t e d ( X , Y ) = ∣ ∣ X ? Y ∣ ∣ 2 = ( x 1 ? y 1 ) 2 + . . . + ( x n ? y n ) 2 2 dist_{ed}(X,Y)=||X-Y||{2}=\sqrt[2]{(x_{1}-y_{1})^{2}+...+(x_{n}-y_{n})^{2}} disted (X,Y)=∣∣X?Y∣∣2=2(x1 ?y1 )2+...+(xn ?yn )2

k-means算法是把數據給分成不同的簇，目標是同一個簇中的差異小，不同簇之間的差異大，這個目標怎么用數學語言描述呢？我們一般用誤差平方和作為目標函數（想想線性回歸中說過的殘差平方和、損失函數，是不是很相似），公式如下:

S S E = ∑ i = 1 K ∑ x ∈ C i ( C i ? x ) 2 SSE=\sum_{i=1}^{K} \sum_{x \in C_{i}}\left(C_{i}-x\right)^{2} SSE=i=1∑K x∈Ci ∑ (Ci ?x)2

其中C表示聚類中心，如果x屬于 C i C_{i} Ci 這個簇，則計算兩者的歐式距離，將所有樣本點到其中心點距離算出來，并加總，就是k-means的目標函數。實現同一個簇中的樣本差異小，就是最小化SSE。

可以通過求導來求函數的極值，我們對SSE求偏導看看能得到什么結果：

? ? C k S S E = ? ? C k ∑ i = 1 K ∑ x ∈ C i ( C i ? x ) 2 = ∑ i = 1 K ∑ x ∈ C i ? ? C k ( C i ? x ) 2 = ∑ x ∈ C i 2 ( C i ? x ) = 0

??CkSSE=??Ck∑i=1K∑x∈Ci(Ci?x)2=∑i=1K∑x∈Ci??Ck(Ci?x)2=∑x∈Ci2(Ci?x)=0

?

?

C

k

S

S

E

=

?

?

C

k

∑

i

=

1

K

∑

x

∈

C

i

(

C

i

?

x

)

2

=

∑

i

=

1

K

∑

x

∈

C

i

?

?

C

k

(

C

i

?

x

)

2

=

∑

x

∈

C

i

2

(

C

i

?

x

)

=

0

∑ x ∈ C i 2 ( C i ? x ) = 0 ? m i C i = ∑ x ∈ C i x ? C i = 1 m i ∑ x ∈ C i x \sum_{x \in C_{i}} 2\left(C_{i}-x\right)=0 \Rightarrow m_{i} C_{i}=\sum_{x \in C_{i}} x \Rightarrow C_{i}=\frac{1}{m_{i}} \sum_{x \in C_{i}} x x∈Ci ∑ 2(Ci ?x)=0?mi Ci =x∈Ci ∑ x?Ci =mi 1 x∈Ci ∑ x

式中m是簇中點的數量，發現了沒有，這個C的解，就是X的均值點。多點的均值點應該很好理解吧，給定一組點 X 1 , . . . , X m X_{1},...,X_{m} X1 ,...,Xm ，其中 X i = ( x i 1 , x i 2 , . . . , x i n ) X_{i}=(x_{i1},x_{i2},...,x_{in}) Xi =(xi1 ,xi2 ,...,xin ) ，這組點的均值向量表示為：

C = ( x 11 + . . . + x 1 n m , . . . , x m 1 + . . . + x m n m ) C=(\frac{x_{11}+...+x_{1n}}{m},...,\frac{x_{m1}+...+x_{mn}}{m}) C=(mx11 +...+x1n ,...,mxm1 +...+xmn )

K-Means偽代碼

function K-Means(輸入數據，中心點個數K) 獲取輸入數據的維度Dim和個數N 隨機生成K個Dim維的點 while(算法未收斂) 對N個點：計算每個點屬于哪一類。 對于K個中心點： 1，找出所有屬于自己這一類的所有數據點 2，把自己的坐標修改為這些數據點的中心點坐標 end 輸出結果： end

1

2

3

4

5

6

7

8

9

10

11

K-Means優缺點

優點:

屬于無監督學習，無須準備訓練集

原理簡單，實現起來較為容易

結果可解釋性較好

缺點:

聚類數目k是一個輸入參數。選擇不恰當的k值可能會導致糟糕的聚類結果。這也是為什么要進行特征檢查來決定數據集的聚類數目了。

可能收斂到局部最小值, 在大規模數據集上收斂較慢

對于異常點、離群點敏感

K-Means算法實現

from collections import defaultdict from random import uniform from math import sqrt def point_avg(points): """ Accepts a list of points, each with the same number of dimensions. NB. points can have more dimensions than 2 Returns a new point which is the center of all the points. """ dimensions = len(points[0]) new_center = [] for dimension in xrange(dimensions): dim_sum = 0 # dimension sum for p in points: dim_sum += p[dimension] # average of each dimension new_center.append(dim_sum / float(len(points))) return new_center def update_centers(data_set, assignments): """ Accepts a dataset and a list of assignments; the indexes of both lists correspond to each other. Compute the center for each of the assigned groups. Return `k` centers where `k` is the number of unique assignments. """ new_means = defaultdict(list) centers = [] for assignment, point in zip(assignments, data_set): new_means[assignment].append(point) for points in new_means.itervalues(): centers.append(point_avg(points)) return centers def assign_points(data_points, centers): """ Given a data set and a list of points betweeen other points, assign each point to an index that corresponds to the index of the center point on it's proximity to that point. Return a an array of indexes of centers that correspond to an index in the data set; that is, if there are N points in `data_set` the list we return will have N elements. Also If there are Y points in `centers` there will be Y unique possible values within the returned list. """ assignments = [] for point in data_points: shortest = () # positive infinity shortest_index = 0 for i in xrange(len(centers)): val = distance(point, centers[i]) if val < shortest: shortest = val shortest_index = i assignments.append(shortest_index) return assignments def distance(a, b): """ """ dimensions = len(a) _sum = 0 for dimension in xrange(dimensions): difference_sq = (a[dimension] - b[dimension]) ** 2 _sum += difference_sq return sqrt(_sum) def generate_k(data_set, k): """ Given `data_set`, which is an array of arrays, find the minimum and maximum for each coordinate, a range. Generate `k` random points between the ranges. Return an array of the random points within the ranges. """ centers = [] dimensions = len(data_set[0]) min_max = defaultdict(int) for point in data_set: for i in xrange(dimensions): val = point[i] min_key = 'min_%d' % i max_key = 'max_%d' % i if min_key not in min_max or val < min_max[min_key]: min_max[min_key] = val if max_key not in min_max or val > min_max[max_key]: min_max[max_key] = val for _k in xrange(k): rand_point = [] for i in xrange(dimensions): min_val = min_max['min_%d' % i] max_val = min_max['max_%d' % i] rand_point.append(uniform(min_val, max_val)) centers.append(rand_point) return centers def k_means(dataset, k): k_points = generate_k(dataset, k) assignments = assign_points(dataset, k_points) old_assignments = None while assignments != old_assignments: new_centers = update_centers(dataset, assignments) old_assignments = assignments assignments = assign_points(dataset, new_centers) return zip(assignments, dataset) # points = [ # [1, 2], # [2, 1], # [3, 1], # [5, 4], # [5, 5], # [6, 5], # [10, 8], # [7, 9], # [11, 5], # [14, 9], # [14, 14], # ] # print k_means(points, 3)

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

參考文獻

https://zhuanlan.zhihu.com/p/75477709

機器學習

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。