【資料挖掘】K-Means 二維資料聚類分析 ( K-Means 疊代總結 | K-Means 初始中心點選擇方案 | K-Means 算法優缺點 | K-Means 算法變種 )

文章目錄

• • • • K-Means 二維資料 聚類分析 資料樣本及聚類要求
      • 二維資料曼哈頓距離計算
      • K-Means 算法 步驟
      • 第一次疊代 : 步驟 ( 1 ) 中心點初始化
      • 第一次疊代 : 步驟 ( 2 ) 計算距離
      • 第一次疊代 : 步驟 ( 3 ) 聚類分組
      • 第二次疊代 : 步驟 ( 1 ) 中心點初始化
      • 第二次疊代 : 步驟 ( 2 ) 計算距離
      • 第二次疊代 : 步驟 ( 3 ) 聚類分組
      • K-Means 疊代總結
      • K-Means 初始中心點選擇方案
      • K-Means 算法優缺點
      • K-Means 算法變種

K-Means 二維資料 聚類分析 資料樣本及聚類要求

資料樣本及聚類要求 :

① 資料樣本 : 資料集樣本為

6

6

6 個點 ,

A

1

(

2

,

4

)

A_1 ( 2 , 4 )

A1​(2,4) ,

A

2

(

3

,

7

)

A_2 ( 3 , 7 )

A2​(3,7) ,

B

1

(

5

,

8

)

B_1 ( 5 , 8 )

B1​(5,8) ,

B

2

(

9

,

5

)

B_2 ( 9 , 5 )

B2​(9,5) ,

C

1

(

6

,

2

)

C_1 ( 6 , 2 )

C1​(6,2) ,

C

2

(

4

,

9

)

C_2 ( 4 , 9 )

C2​(4,9) ;

② 聚類個數 : 分為

3

3

3 個聚類 ;

③ 距離計算方式 : 使用 曼哈頓距離 , 計算樣本之間的相似度 ; 曼哈頓距離的計算方式是 兩個次元的資料差 的 絕對值 相加 ;

④ 中心點初始值 : 選取

A

1

,

B

1

,

C

1

A_1 , B_1 , C_1

A1​,B1​,C1​ 三個樣本為聚類的初始值 , 這是實點 ; 如果選取非樣本的點作為初始值 , 就是虛點 ;

⑤ 要求 : 使用 K-Means 算法疊代

2

2

2 次 ;

⑥ 中心值精度 : 計算過程中中心值小數向下取整 ;

二維資料曼哈頓距離計算

1 . 曼哈頓距離 公式如下 :

d

(

i

,

j

)

=

∣

x

i

1

−

x

j

1

∣

+

∣

x

i

2

−

x

j

2

∣

+

⋯

+

∣

x

i

p

−

x

j

p

∣

d(i, j) = | x_{i1} - x_{j1} | + | x_{i2} - x_{j2} | + \cdots + | x_{ip} - x_{jp} |

d(i,j)=∣xi1​−xj1​∣+∣xi2​−xj2​∣+⋯+∣xip​−xjp​∣

d

(

i

,

j

)

d(i, j)

d(i,j) 表示兩個樣本之間的距離 , 曼哈頓距離 ;

p

p

p 表示屬性的個數 , 每個樣本有

p

p

p 個屬性 ;

i

i

i 和

j

j

j 表示兩個 樣本的索引值 , 取值範圍是

{

1

,

2

,

⋯

 

,

q

}

\{1 , 2, \cdots , q\}

{1,2,⋯,q} ;

x

i

p

−

x

j

p

x_{ip} - x_{jp}

xip​−xjp​ 表示兩個樣本 第

p

p

p 個屬性值 的內插補點 ,

x

i

1

−

x

j

1

x_{i1} - x_{j1}

xi1​−xj1​ 表示兩個樣本 第

1

1

1 個屬性值 的內插補點 ,

x

i

2

−

x

j

2

x_{i2} - x_{j2}

xi2​−xj2​ 表示兩個樣本 第

2

2

2 個屬性值 的內插補點 ;

2 . 曼哈頓距離圖示 : 曼哈頓的街道都是橫平豎直的 , 從

A

A

A 點到

B

B

B 點 , 一般就是其

x

x

x 軸坐标差 加上其

y

y

y 軸坐标差 , 即

x

+

y

x + y

x+y ;

3 . 本題目中的樣本距離計算示例 : 兩個樣本的曼哈頓距離是

x

x

x 屬性差的絕對值 , 加上

y

y

y 屬性差的絕對值 , 之和 ;

計算

A

1

(

2

,

4

)

A_1 ( 2 , 4 )

A1​(2,4) ,

A

2

(

3

,

7

)

A_2 ( 3 , 7 )

A2​(3,7) 的距離 :

d

(

A

1

,

A

2

)

=

∣

2

−

3

∣

+

∣

4

−

7

∣

=

4

d(A_1 , A_2) = | 2 - 3 | + |4 - 7| = 4

d(A1​,A2​)=∣2−3∣+∣4−7∣=4

A

1

A_1

A1​ 樣本與

A

2

A_2

A2​ 樣本之間的距離是

4

4

4 ;

K-Means 算法 步驟

K-Means 算法 步驟 : 給定資料集

X

X

X , 該資料集有

n

n

n 個樣本 , 将其分成

K

K

K 個聚類 ;

① 中心點初始化 : 為

K

K

K 個聚類分組選擇初始的中心點 , 這些中心點稱為 Means ; 可以依據經驗 , 也可以随意選擇 ;

② 計算距離 : 計算

n

n

n 個對象與

K

K

K 個中心點 的距離 ; ( 共計算

n

×

K

n \times K

n×K 次 )

③ 聚類分組 : 每個對象與

K

K

K 個中心點的值已計算出 , 将每個對象配置設定給距離其最近的中心點對應的聚類 ;

④ 計算中心點 : 根據聚類分組中的樣本 , 計算每個聚類的中心點 ;

⑤ 疊代直至收斂 : 疊代執行 ② ③ ④ 步驟 , 直到 聚類算法收斂 , 即 中心點 和 分組 經過多少次疊代都不再改變 , 也就是本次計算的中心點與上一次的中心點一樣 ;

第一次疊代 : 步驟 ( 1 ) 中心點初始化

初始化中心點 :

3

3

3 個聚類的中心點 , 在題目中已經給出 ;

① 聚類

1

1

1 中心點 :

A

1

(

2

,

4

)

A_1 ( 2 , 4 )

A1​(2,4) ;

② 聚類

2

2

2 中心點 :

B

1

(

5

,

8

)

B_1 ( 5 , 8 )

B1​(5,8) ;

③ 聚類

3

3

3 中心點 :

C

1

(

6

,

2

)

C_1 ( 6 , 2 )

C1​(6,2) ;

第一次疊代 : 步驟 ( 2 ) 計算距離

距離計算次數 : 這裡需要計算所有的樣本 , 與所有的中心點的距離 , 每個樣本都需要計算與

3

3

3 個中心點的距離 , 共需要計算

6

×

3

=

18

6 \times 3 = 18

6×3=18 次 ;

資料樣本 :

A

1

(

2

,

4

)

A_1 ( 2 , 4 )

A1​(2,4) ,

A

2

(

3

,

7

)

A_2 ( 3 , 7 )

A2​(3,7) ,

B

1

(

5

,

8

)

B_1 ( 5 , 8 )

B1​(5,8) ,

B

2

(

9

,

5

)

B_2 ( 9 , 5 )

B2​(9,5) ,

C

1

(

6

,

2

)

C_1 ( 6 , 2 )

C1​(6,2) ,

C

2

(

4

,

9

)

C_2 ( 4 , 9 )

C2​(4,9)

1 . 計算

A

1

(

2

,

4

)

A_1 ( 2 , 4 )

A1​(2,4) 與 三個中心點

{

A

1

,

B

1

,

C

1

}

\{ A_1 , B_1 , C_1 \}

{A1​,B1​,C1​} 之間的距離 :

①

A

1

(

2

,

4

)

A_1 ( 2 , 4 )

A1​(2,4) 與

A

1

(

2

,

4

)

A_1 ( 2 , 4 )

A1​(2,4) 的距離 : ( 最小 )

d

(

A

1

,

A

1

)

=

∣

2

−

2

∣

+

∣

4

−

4

∣

=

d(A_1 , A_1) = | 2-2 | + | 4-4 | = 0

d(A1​,A1​)=∣2−2∣+∣4−4∣=0

②

A

1

(

2

,

4

)

A_1 ( 2 , 4 )

A1​(2,4) 與

B

1

(

5

,

8

)

B_1 ( 5 , 8 )

B1​(5,8) 的距離 :

d

(

A

1

,

B

1

)

=

∣

2

−

5

∣

+

∣

4

−

8

∣

=

7

d(A_1 , B_1) = | 2-5 | + | 4-8 | = 7

d(A1​,B1​)=∣2−5∣+∣4−8∣=7

③

A

1

(

2

,

4

)

A_1 ( 2 , 4 )

A1​(2,4) 與

C

1

(

6

,

2

)

C_1 ( 6 , 2 )

C1​(6,2) 的距離 :

d

(

A

1

,

C

1

)

=

∣

2

−

6

∣

+

∣

4

−

2

∣

=

6

d(A_1 , C_1) = | 2-6 | + | 4-2 | = 6

d(A1​,C1​)=∣2−6∣+∣4−2∣=6

A

1

(

2

,

4

)

A_1 ( 2 , 4 )

A1​(2,4) 與

A

1

(

2

,

4

)

A_1 ( 2 , 4 )

A1​(2,4) 的距離最小 ;

2 . 計算

A

2

(

3

,

7

)

A_2 ( 3 , 7 )

A2​(3,7) 與 三個中心點

{

A

1

,

B

1

,

C

1

}

\{ A_1 , B_1 , C_1 \}

{A1​,B1​,C1​} 之間的距離 :

①

A

2

(

3

,

7

)

A_2 ( 3 , 7 )

A2​(3,7) 與

A

1

(

2

,

4

)

A_1 ( 2 , 4 )

A1​(2,4) 的距離 :

d

(

A

2

,

A

1

)

=

∣

3

−

2

∣

+

∣

7

−

4

∣

=

4

d(A_2 , A_1) = | 3-2 | + | 7-4 | = 4

d(A2​,A1​)=∣3−2∣+∣7−4∣=4

②

A

2

(

3

,

7

)

A_2 ( 3 , 7 )

A2​(3,7) 與

B

1

(

5

,

8

)

B_1 ( 5 , 8 )

B1​(5,8) 的距離 : ( 最小 )

d

(

A

2

,

B

1

)

=

∣

3

−

5

∣

+

∣

7

−

8

∣

=

3

d(A_2 , B_1) = | 3-5 | + | 7-8 | = 3

d(A2​,B1​)=∣3−5∣+∣7−8∣=3

③

A

2

(

3

,

7

)

A_2 ( 3 , 7 )

A2​(3,7) 與

C

1

(

6

,

2

)

C_1 ( 6 , 2 )

C1​(6,2) 的距離 :

d

(

A

2

,

C

1

)

=

∣

3

−

6

∣

+

∣

7

−

2

∣

=

8

d(A_2 , C_1) = | 3-6 | + | 7-2 | = 8

d(A2​,C1​)=∣3−6∣+∣7−2∣=8

A

2

(

3

,

7

)

A_2 ( 3 , 7 )

A2​(3,7) 與

B

1

(

5

,

8

)

B_1 ( 5 , 8 )

B1​(5,8) 的距離最小 ;

3 . 計算

B

1

(

5

,

8

)

B_1 ( 5 , 8 )

B1​(5,8) 與 三個中心點

{

A

1

,

B

1

,

C

1

}

\{ A_1 , B_1 , C_1 \}

{A1​,B1​,C1​} 之間的距離 :

①

B

1

(

5

,

8

)

B_1 ( 5 , 8 )

B1​(5,8) 與

A

1

(

2

,

4

)

A_1 ( 2 , 4 )

A1​(2,4) 的距離 :

d

(

B

1

,

A

1

)

=

∣

5

−

2

∣

+

∣

8

−

4

∣

=

7

d(B_1 , A_1) = | 5 -2 | + | 8 -4 | = 7

d(B1​,A1​)=∣5−2∣+∣8−4∣=7

②

B

1

(

5

,

8

)

B_1 ( 5 , 8 )

B1​(5,8) 與

B

1

(

5

,

8

)

B_1 ( 5 , 8 )

B1​(5,8) 的距離 : ( 最小 )

d

(

B

1

,

B

1

)

=

∣

5

−

5

∣

+

∣

8

−

8

∣

=

d(B_1 , B_1) = | 5 -5 | + | 8 -8 | = 0

d(B1​,B1​)=∣5−5∣+∣8−8∣=0

③

B

1

(

5

,

8

)

B_1 ( 5 , 8 )

B1​(5,8) 與

C

1

(

6

,

2

)

C_1 ( 6 , 2 )

C1​(6,2) 的距離 :

d

(

B

1

,

C

1

)

=

∣

5

−

6

∣

+

∣

8

−

2

∣

=

7

d(B_1 , C_1) = | 5 -6 | + | 8 -2 | = 7

d(B1​,C1​)=∣5−6∣+∣8−2∣=7

B

1

(

5

,

8

)

B_1 ( 5 , 8 )

B1​(5,8) 與

B

1

(

5

,

8

)

B_1 ( 5 , 8 )

B1​(5,8) 的距離最小 ;

4 . 計算

B

2

(

9

,

5

)

B_2 ( 9 , 5 )

B2​(9,5) 與 三個中心點

{

A

1

,

B

1

,

C

1

}

\{ A_1 , B_1 , C_1 \}

{A1​,B1​,C1​} 之間的距離 :

①

B

2

(

9

,

5

)

B_2 ( 9 , 5 )

B2​(9,5) 與

A

1

(

2

,

4

)

A_1 ( 2 , 4 )

A1​(2,4) 的距離 :

d

(

B

2

,

A

1

)

=

∣

9

−

2

∣

+

∣

5

−

4

∣

=

8

d(B_2 , A_1) = | 9 -2 | + | 5 -4 | = 8

d(B2​,A1​)=∣9−2∣+∣5−4∣=8

②

B

2

(

9

,

5

)

B_2 ( 9 , 5 )

B2​(9,5) 與

B

1

(

5

,

8

)

B_1 ( 5 , 8 )

B1​(5,8) 的距離 :

d

(

B

2

,

B

1

)

=

∣

9

−

5

∣

+

∣

5

−

8

∣

=

7

d(B_2 , B_1) = | 9 -5 | + | 5 -8 | = 7

d(B2​,B1​)=∣9−5∣+∣5−8∣=7

③

B

2

(

9

,

5

)

B_2 ( 9 , 5 )

B2​(9,5) 與

C

1

(

6

,

2

)

C_1 ( 6 , 2 )

C1​(6,2) 的距離 : ( 最小 )

d

(

B

2

,

C

1

)

=

∣

9

−

6

∣

+

∣

5

−

2

∣

=

6

d(B_2 , C_1) = | 9 -6 | + | 5 -2 | = 6

d(B2​,C1​)=∣9−6∣+∣5−2∣=6

B

2

(

9

,

5

)

B_2 ( 9 , 5 )

B2​(9,5) 與

C

1

(

6

,

2

)

C_1 ( 6 , 2 )

C1​(6,2) 的距離最小 ;

5 . 計算

C

1

(

6

,

2

)

C_1 ( 6 , 2 )

C1​(6,2) 與 三個中心點

{

A

1

,

B

1

,

C

1

}

\{ A_1 , B_1 , C_1 \}

{A1​,B1​,C1​} 之間的距離 :

①

C

1

(

6

,

2

)

C_1 ( 6 , 2 )

C1​(6,2) 與

A

1

(

2

,

4

)

A_1 ( 2 , 4 )

A1​(2,4) 的距離 :

d

(

C

1

,

A

1

)

=

∣

6

−

2

∣

+

∣

2

−

4

∣

=

6

d(C_1 , A_1) = | 6 -2 | + | 2 -4 | = 6

d(C1​,A1​)=∣6−2∣+∣2−4∣=6

②

C

1

(

6

,

2

)

C_1 ( 6 , 2 )

C1​(6,2) 與

B

1

(

5

,

8

)

B_1 ( 5 , 8 )

B1​(5,8) 的距離 :

d

(

C

1

,

B

1

)

=

∣

6

−

5

∣

+

∣

2

−

8

∣

=

7

d(C_1 , B_1) = | 6 -5 | + | 2 -8 | = 7

d(C1​,B1​)=∣6−5∣+∣2−8∣=7

③

C

1

(

6

,

2

)

C_1 ( 6 , 2 )

C1​(6,2) 與

C

1

(

6

,

2

)

C_1 ( 6 , 2 )

C1​(6,2) 的距離 : ( 最小 )

d

(

C

1

,

C

1

)

=

∣

6

−

6

∣

+

∣

2

−

2

∣

=

d(C_1 , C_1) = | 6 -6 | + | 2 -2 | = 0

d(C1​,C1​)=∣6−6∣+∣2−2∣=0

C

1

(

6

,

2

)

C_1 ( 6 , 2 )

C1​(6,2) 與

C

1

(

6

,

2

)

C_1 ( 6 , 2 )

C1​(6,2) 的距離最小 ;

6 . 計算

C

2

(

4

,

9

)

C_2 ( 4 , 9 )

C2​(4,9) 與 三個中心點

{

A

1

,

B

1

,

C

1

}

\{ A_1 , B_1 , C_1 \}

{A1​,B1​,C1​} 之間的距離 :

①

C

2

(

4

,

9

)

C_2 ( 4 , 9 )

C2​(4,9) 與

A

1

(

2

,

4

)

A_1 ( 2 , 4 )

A1​(2,4) 的距離 :

d

(

C

2

,

A

1

)

=

∣

4

−

2

∣

+

∣

9

−

4

∣

=

7

d(C_2 , A_1) = | 4 -2 | + | 9 -4 | = 7

d(C2​,A1​)=∣4−2∣+∣9−4∣=7

②

C

2

(

4

,

9

)

C_2 ( 4 , 9 )

C2​(4,9) 與

B

1

(

5

,

8

)

B_1 ( 5 , 8 )

B1​(5,8) 的距離 : ( 最小 )

d

(

C

2

,

B

1

)

=

∣

4

−

5

∣

+

∣

9

−

8

∣

=

2

d(C_2 , B_1) = | 4 -5 | + | 9 -8 | = 2

d(C2​,B1​)=∣4−5∣+∣9−8∣=2

③

C

2

(

4

,

9

)

C_2 ( 4 , 9 )

C2​(4,9) 與

C

1

(

6

,

2

)

C_1 ( 6 , 2 )

C1​(6,2) 的距離 :

d

(

C

2

,

C

1

)

=

∣

4

−

6

∣

+

∣

9

−

2

∣

=

9

d(C_2 , C_1) = | 4 -6 | + | 9 -2 | = 9

d(C2​,C1​)=∣4−6∣+∣9−2∣=9

C

2

(

4

,

9

)

C_2 ( 4 , 9 )

C2​(4,9) 與

B

1

(

5

,

8

)

B_1 ( 5 , 8 )

B1​(5,8) 的距離最小 ;

8 . 生成距離表格 : 将上面計算的内容總結到如下表格中 ;

A 1 ( 2 , 4 ) A_1 ( 2 , 4 ) A1​(2,4)	A 2 ( 3 , 7 ) A_2 ( 3 , 7 ) A2​(3,7)	B 1 ( 5 , 8 ) B_1 ( 5 , 8 ) B1​(5,8)	B 2 ( 9 , 5 ) B_2 ( 9 , 5 ) B2​(9,5)	C 1 ( 6 , 2 ) C_1 ( 6 , 2 ) C1​(6,2)	C 2 ( 4 , 9 ) C_2 ( 4 , 9 ) C2​(4,9)
A 1 ( 2 , 4 ) A_1 ( 2 , 4 ) A1​(2,4)		4 4 4	7 7 7	8 8 8	6 6 6	7 7 7
B 1 ( 5 , 8 ) B_1 ( 5 , 8 ) B1​(5,8)	7 7 7	3 3 3		7 7 7	7 7 7	2 2 2
C 1 ( 6 , 2 ) C_1 ( 6 , 2 ) C1​(6,2)	6 6 6	8 8 8	7 7 7	6 6 6		9 9 9

第一次疊代 : 步驟 ( 3 ) 聚類分組

1 . 聚類分組 : 根據計算出的 , 每個樣本與

3

3

3 個中心點的距離 , 将樣本劃分到 距離該樣本最近的中心點 對應的分組中 ;

A 1 ( 2 , 4 ) A_1 ( 2 , 4 ) A1​(2,4)	A 2 ( 3 , 7 ) A_2 ( 3 , 7 ) A2​(3,7)	B 1 ( 5 , 8 ) B_1 ( 5 , 8 ) B1​(5,8)	B 2 ( 9 , 5 ) B_2 ( 9 , 5 ) B2​(9,5)	C 1 ( 6 , 2 ) C_1 ( 6 , 2 ) C1​(6,2)	C 2 ( 4 , 9 ) C_2 ( 4 , 9 ) C2​(4,9)
A 1 ( 2 , 4 ) A_1 ( 2 , 4 ) A1​(2,4)		4 4 4	7 7 7	8 8 8	6 6 6	7 7 7
B 1 ( 5 , 8 ) B_1 ( 5 , 8 ) B1​(5,8)	7 7 7	3 3 3		7 7 7	7 7 7	2 2 2
C 1 ( 6 , 2 ) C_1 ( 6 , 2 ) C1​(6,2)	6 6 6	8 8 8	7 7 7	6 6 6		9 9 9

2 . 根據表格中的距離 , 為每個樣本分組 :

①

A

1

(

2

,

4

)

A_1 ( 2 , 4 )

A1​(2,4) 距離

A

1

(

2

,

4

)

A_1 ( 2 , 4 )

A1​(2,4) 中心點最近 , 劃分到 聚類

1

1

1 中 ;

②

A

2

(

3

,

7

)

A_2 ( 3 , 7 )

A2​(3,7) 距離

B

1

(

5

,

8

)

B_1 ( 5 , 8 )

B1​(5,8) 中心點最近 , 劃分到 聚類

2

2

2 中 ;

③

B

1

(

5

,

8

)

B_1 ( 5 , 8 )

B1​(5,8) 距離

B

1

(

5

,

8

)

B_1 ( 5 , 8 )

B1​(5,8) 中心點最近 , 劃分到 聚類

2

2

2 中 ;

④

B

2

(

9

,

5

)

B_2 ( 9 , 5 )

B2​(9,5) 距離

C

1

(

6

,

2

)

C_1 ( 6 , 2 )

C1​(6,2) 中心點最近 , 劃分到 聚類

3

3

3 中 ;

⑤

C

1

(

6

,

2

)

C_1 ( 6 , 2 )

C1​(6,2) 距離

C

1

(

6

,

2

)

C_1 ( 6 , 2 )

C1​(6,2) 中心點最近 , 劃分到 聚類

3

3

3 中 ;

⑥

C

2

(

4

,

9

)

C_2 ( 4 , 9 )

C2​(4,9) 距離

B

1

(

5

,

8

)

B_1 ( 5 , 8 )

B1​(5,8) 中心點最近 , 劃分到 聚類

2

2

2 中 ;

3 . 最終的聚類分組為 :

① 聚類

1

1

1 :

{

A

1

}

\{ A_1 \}

{A1​}

② 聚類

2

2

2 :

{

A

2

,

B

1

,

C

2

}

\{ A_2 , B_1 , C_2 \}

{A2​,B1​,C2​}

③ 聚類

3

3

3 :

{

B

2

,

C

1

}

\{ B_2 , C_1 \}

{B2​,C1​}

第二次疊代 : 步驟 ( 1 ) 中心點初始化

A

1

(

2

,

4

)

A_1 ( 2 , 4 )

A1​(2,4) ,

A

2

(

3

,

7

)

A_2 ( 3 , 7 )

A2​(3,7) ,

B

1

(

5

,

8

)

B_1 ( 5 , 8 )

B1​(5,8) ,

B

2

(

9

,

5

)

B_2 ( 9 , 5 )

B2​(9,5) ,

C

1

(

6

,

2

)

C_1 ( 6 , 2 )

C1​(6,2) ,

C

2

(

4

,

9

)

C_2 ( 4 , 9 )

C2​(4,9)

1 . 聚類

1

1

1 中心點計算 : 計算

{

A

1

(

2

,

4

)

}

\{ A_1 ( 2 , 4 ) \}

{A1​(2,4)} 中心點

聚

類

1

中

心

點

=

(

2

,

4

)

聚類 1 中心點 = ( 2 , 4 )

聚類1中心點=(2,4)

2 . 聚類

2

2

2 中心點計算 : 計算

{

A

2

(

3

,

7

)

,

B

1

(

5

,

8

)

,

C

2

(

4

,

9

)

}

\{ A_2 ( 3 , 7 ) , B_1 ( 5 , 8 ) , C_2( 4 , 9 ) \}

{A2​(3,7),B1​(5,8),C2​(4,9)} 中心點

聚

類

2

中

心

點

=

(

3

+

5

+

4

3

,

7

+

8

+

9

3

)

=

(

4

,

8

)

聚類 2 中心點 = ( \frac{3 + 5 + 4}{3} , \frac{7 + 8 + 9}{3}) = ( 4 , 8 )

聚類2中心點=(33+5+4​,37+8+9​)=(4,8)

3 . 聚類

3

3

3 中心點計算 : 計算

{

B

2

(

9

,

5

)

,

C

1

(

6

,

2

)

}

\{ B_2( 9 , 5 ) , C_1 ( 6 , 2 ) \}

{B2​(9,5),C1​(6,2)} 中心點

聚

類

3

中

心

點

=

(

9

+

6

2

,

5

+

2

2

)

=

(

7

,

3

)

聚類 3 中心點 = ( \frac{9 + 6 }{2} , \frac{5 + 2}{2}) = ( 7 , 3 )

聚類3中心點=(29+6​,25+2​)=(7,3)

第二次疊代 : 步驟 ( 2 ) 計算距離

計算

6

6

6 個點 , 到

3

3

3 個中心點的距離 ,

3

3

3 個中心點分别是

{

(

2

,

4

)

,

(

4

,

8

)

,

(

7

,

3

)

}

\{ ( 2 , 4 ) , ( 4 , 8 ) , ( 7 , 3 ) \}

{(2,4),(4,8),(7,3)} , 直接将兩個點的曼哈頓距離填在對應的表格中 ;

如 : 第

1

1

1 行 , 第

2

2

2 列 :

A

1

(

2

,

4

)

A_1 ( 2 , 4 )

A1​(2,4) 樣本 與

(

4

,

8

)

( 4 , 8 )

(4,8) 聚類

2

2

2 中心點的 曼哈頓距離 是

6

6

6 , 計算過程如下 :

A

1

(

2

,

4

)

與

(

4

,

8

)

兩

點

曼

哈

頓

距

離

=

∣

2

−

4

∣

+

∣

4

−

8

∣

=

6

A_1 ( 2 , 4 ) 與 ( 4 , 8 ) 兩點曼哈頓距離 = | 2 - 4 | + | 4 - 8 | = 6

A1​(2,4)與(4,8)兩點曼哈頓距離=∣2−4∣+∣4−8∣=6

A 1 ( 2 , 4 ) A_1 ( 2 , 4 ) A1​(2,4)	A 2 ( 3 , 7 ) A_2 ( 3 , 7 ) A2​(3,7)	B 1 ( 5 , 8 ) B_1 ( 5 , 8 ) B1​(5,8)	B 2 ( 9 , 5 ) B_2 ( 9 , 5 ) B2​(9,5)	C 1 ( 6 , 2 ) C_1 ( 6 , 2 ) C1​(6,2)	C 2 ( 4 , 9 ) C_2 ( 4 , 9 ) C2​(4,9)
( 2 , 4 ) ( 2 , 4 ) (2,4)		4 4 4	7 7 7	8 8 8	6 6 6	7 7 7
( 4 , 8 ) ( 4 , 8 ) (4,8)	6 6 6	2 2 2	1 1 1	8 8 8	8 8 8	1 1 1
( 7 , 3 ) ( 7 , 3 ) (7,3)	6 6 6	8 8 8	7 7 7	4 4 4	2 2 2	9 9 9

第二次疊代 : 步驟 ( 3 ) 聚類分組

1 . 聚類分組 : 根據計算出的 , 每個樣本與

3

3

3 個中心點的距離 , 将樣本劃分到 距離該樣本最近的中心點 對應的分組中 ;

A 1 ( 2 , 4 ) A_1 ( 2 , 4 ) A1​(2,4)	A 2 ( 3 , 7 ) A_2 ( 3 , 7 ) A2​(3,7)	B 1 ( 5 , 8 ) B_1 ( 5 , 8 ) B1​(5,8)	B 2 ( 9 , 5 ) B_2 ( 9 , 5 ) B2​(9,5)	C 1 ( 6 , 2 ) C_1 ( 6 , 2 ) C1​(6,2)	C 2 ( 4 , 9 ) C_2 ( 4 , 9 ) C2​(4,9)
( 2 , 4 ) ( 2 , 4 ) (2,4)		4 4 4	7 7 7	8 8 8	6 6 6	7 7 7
( 4 , 8 ) ( 4 , 8 ) (4,8)	6 6 6	2 2 2	1 1 1	8 8 8	8 8 8	1 1 1
( 7 , 3 ) ( 7 , 3 ) (7,3)	6 6 6	8 8 8	7 7 7	4 4 4	2 2 2	9 9 9

2 . 根據表格中的距離 , 為每個樣本分組 :

①

A

1

(

2

,

4

)

A_1 ( 2 , 4 )

A1​(2,4) 距離

(

2

,

4

)

( 2 , 4 )

(2,4) 中心點最近 , 劃分到 聚類

1

1

1 中 ;

②

A

2

(

3

,

7

)

A_2 ( 3 , 7 )

A2​(3,7) 距離

(

4

,

8

)

( 4 , 8 )

(4,8) 中心點最近 , 劃分到 聚類

2

2

2 中 ;

③

B

1

(

5

,

8

)

B_1 ( 5 , 8 )

B1​(5,8) 距離

(

4

,

8

)

( 4 , 8 )

(4,8) 中心點最近 , 劃分到 聚類

2

2

2 中 ;

④

B

2

(

9

,

5

)

B_2 ( 9 , 5 )

B2​(9,5) 距離

(

7

,

3

)

( 7 , 3 )

(7,3) 中心點最近 , 劃分到 聚類

3

3

3 中 ;

⑤

C

1

(

6

,

2

)

C_1 ( 6 , 2 )

C1​(6,2) 距離

(

7

,

3

)

( 7 , 3 )

(7,3) 中心點最近 , 劃分到 聚類

3

3

3 中 ;

⑥

C

2

(

4

,

9

)

C_2 ( 4 , 9 )

C2​(4,9) 距離

(

4

,

8

)

( 4 , 8 )

(4,8) 中心點最近 , 劃分到 聚類

2

2

2 中 ;

3 . 最終的聚類分組為 :

① 聚類

1

1

1 :

{

A

1

}

\{ A_1 \}

{A1​}

② 聚類

2

2

2 :

{

A

2

,

B

1

,

C

2

}

\{ A_2 , B_1 , C_2 \}

{A2​,B1​,C2​}

③ 聚類

3

3

3 :

{

B

2

,

C

1

}

\{ B_2 , C_1 \}

{B2​,C1​}

第二次疊代的聚類分組 , 與第一次疊代的聚類分組 , 沒有改變 , 說明聚類算法分析結果已經收斂 , 該聚類結果就是最終的結果 ;

K-Means 疊代總結

1 . 第一次疊代 :

① 設定中心點 : 設定了

3

3

3 個初始中心點 ,

A

1

(

2

,

4

)

A_1 ( 2 , 4 )

A1​(2,4) 對應聚類

1

1

1 中心點 ,

B

1

(

5

,

8

)

B_1 ( 5 , 8 )

B1​(5,8) 對應聚類

2

2

2 中心點 ,

C

1

(

6

,

2

)

C_1 ( 6 , 2 )

C1​(6,2) 對應聚類

3

3

3 中心點 ;

② 計算中心點距離 : 然後就算

6

6

6 個樣本距離這

3

3

3 個中心點的距離 ;

③ 根據距離聚類分組 : 每個樣本取距離最近的

1

1

1 個中心點 , 将該樣本分類成該中心點對應的聚類分組 , 聚類分組結果是 , 聚類

1

1

1 :

{

A

1

}

\{ A_1 \}

{A1​} , 聚類

2

2

2 :

{

A

2

,

B

1

,

C

2

}

\{ A_2 , B_1 , C_2 \}

{A2​,B1​,C2​} , 聚類

3

3

3 :

{

B

2

,

C

1

}

\{ B_2 , C_1 \}

{B2​,C1​} ;

2 . 第二次疊代 :

① 計算中心點 : 根據第一次疊代的聚類分組結果計算

3

3

3 個中心點 ,

(

2

,

4

)

( 2 , 4 )

(2,4) 對應聚類

1

1

1 中心點 , $( 4 , 8 ) $ 對應聚類

2

2

2 中心點 ,

(

7

,

3

)

( 7 , 3 )

(7,3) 對應聚類

3

3

3 中心點 ;

② 計算中心點距離 : 然後就算

6

6

6 個樣本距離這

3

3

3 個中心點的距離 ;

③ 根據距離聚類分組 : 每個樣本取距離最近的

1

1

1 個中心點 , 将該樣本分類成該中心點對應的聚類分組 , 聚類分組結果是 , 聚類

1

1

1 :

{

A

1

}

\{ A_1 \}

{A1​} , 聚類

2

2

2 :

{

A

2

,

B

1

,

C

2

}

\{ A_2 , B_1 , C_2 \}

{A2​,B1​,C2​} , 聚類

3

3

3 :

{

B

2

,

C

1

}

\{ B_2 , C_1 \}

{B2​,C1​} ;

3 . 最終結果 : 經過

2

2

2 次疊代 , 發現 , 根據最初選擇中心點 , 進行聚類分組的結果 , 就是最終的結果 , 疊代

2

2

2 次的分組結果相同 , 說明聚類算法已經收斂 , 此時的聚類結果就是最終結果 , 聚類算法終止 ;

K-Means 初始中心點選擇方案

1 . 初始中心點選擇 :

① 初始種子 : 初始的中心點 , 又稱為種子 , 如果種子選擇的好 , 疊代的次數就會非常少 , 疊代的最少次數為

2

2

2 , 如上面的示例 ;

② 種子選擇影響 : 初始種子選擇的好壞 , 即影響算法收斂的速度 , 又影響聚類結果的品質 ; 選擇的好 , 疊代

2

2

2 次 , 算法收斂 , 得到最終結果 , 并且聚類效果很好 ; 選擇的不好 , 疊代很多次才收斂 , 并且聚類效果很差 ;

2 . 初始中心點選擇方案 :

① 随機選擇 ;

② 使用已知聚類算法的結果 ;

③ 爬山算法 : K-Means 采用的是爬山算法 , 隻找局部最優的中心點 ;

K-Means 算法優缺點

1 . K-Means 算法優點 :

① 算法可擴充性高 : 算法複雜度随資料量增加 , 而線性增加 ;

② 算法的複雜度 : K-Means 的算法複雜度是

O

(

t

k

n

)

O(tkn)

O(tkn) ,

n

n

n 是資料樣本個數 ,

k

k

k 是聚類分組的個數 ,

t

t

t 是疊代次數 ,

t

t

t 一般不超過

n

n

n ;

2 . K-Means 算法缺點 :

③ 事先必須設定聚類個數 : K-Means 的聚類分組的個數, 必須事先确定 , 有些應用場景中 , 事先是不知道聚類個數的 ;

④ 有些中心點難以确定 : 有些資料類型的中心點不好确定 , 如字元型的資料 , 離散型資料 , 布爾值資料 等 ;

⑤ 魯棒性差 : 對于資料樣本中的噪音資料 , 異常資料 , 不能有效的排除這些資料的幹擾 ;

⑥ 局限性 : 隻能處理凸狀 , 或 球狀分布的樣本資料 , 對于 凹形分布 的樣本資料 , 無法有效的進行聚類分析 ;

K-Means 算法變種

1 . K-Means 方法有很多變種 :

① K_Modes : 處理離散型的屬性值 , 如字元型資料等 ;

② K-Prototypes : 處理 離散型 或 連續型 的屬性 ;

③ K-Medoids : 其計算中心點不是使用算術平均值 , 其使用的是中間值 ;

2 . K-Means 變種算法 與 k-Means 算法的差別與聯系 :

① 原理相同 : 這些變種算法 與 K-Means 算法原理基本相同 ;