• 在 “無(wú)監(jiān)督學(xué)習(xí)” 中，樣本的標(biāo)記信息是未知的，目的是通過(guò)對(duì)無(wú)標(biāo)記訓(xùn)練樣本的學(xué)習(xí)揭示數(shù)據(jù)的內(nèi)在性質(zhì)及規(guī)律，為進(jìn)一步的數(shù)據(jù)分析提供基礎(chǔ)。
• 聚類試圖將數(shù)據(jù)集中的樣本劃分為若干個(gè)不相交的子集，每個(gè)子集稱為一個(gè) “簇”，子集的中心點(diǎn)稱為 “簇心”。聚類過(guò)程僅自動(dòng)形成若干個(gè)簇，簇所對(duì)應(yīng)的意義由使用者來(lái)把握。
• 例如，聚類算法可根據(jù)西瓜的密度與含糖率劃分為三個(gè)簇，使用者則可將這三個(gè)簇命名為 “甜西瓜”、“有點(diǎn)甜瓜”、“不甜瓜”。

k-means聚類

一、概括x

算法對(duì)原型進(jìn)行初始化，然后對(duì)原型迭代更新求解。

二、補(bǔ)充

• 距離計(jì)算
  歐氏距離: d= \sqrt [] { \sum_{k = 1}^{n} {(x_1^k - x_2^k)^2}}
• 性能度量：
  平方誤差：min E = \sum_{i=1}^k\sum_{x∈C_i}{||x-μ_i||_2^2}
• k的取值：
  1.橫坐標(biāo)為簇心數(shù)，縱坐標(biāo)為損失函數(shù)（例如：平方誤差的值）。若隨著k值的增大，出現(xiàn)了明顯的拐點(diǎn)，則取出現(xiàn)拐點(diǎn)時(shí)的k值，但未出現(xiàn)明顯的拐點(diǎn)，則方法失效。
  
  Andrew Ng
  2.簇心數(shù)的取值是為了使用者接下來(lái)的用途服務(wù)的。
  例如：若T恤生產(chǎn)商需要生產(chǎn)S、M、L三種類型的T恤，則需要將購(gòu)買者的數(shù)據(jù)劃分為三類，取簇心作為生產(chǎn)模板，簇心k取3；若T恤生產(chǎn)商需要生產(chǎn)XS、S、M、L、XL五類型的T恤，則需要將購(gòu)買者的數(shù)據(jù)劃分為五類，取簇心作為生產(chǎn)模板，簇心k取5。

Andrew Ng

三、具體過(guò)程

輸入：樣本集D = {x₁,x₂,x₃,...,x_m}，聚類簇?cái)?shù)k

過(guò)程：

從D中隨機(jī)選擇k個(gè)樣本作為初始均值向量，即簇心向量{μ₁, μ₂,...,μ_k}
repeat:
令C{_i} = ?（1<= i <= k）
??for x in 樣本D:
????計(jì)算樣本與各簇心{μ₁, μ₂,...,μ_k}的距離
????x離哪個(gè)簇心近則將其劃分到哪個(gè)簇（{C₁, C₂, ...,C_k }）
??計(jì)算新的均值向量（簇心向量）
??更新簇新{μ₁, μ₂,...,μ_k}
直到簇心向量未更新，或已最小化平方誤差

輸出：簇劃分（簇標(biāo)簽與簇成員）

四、舉個(gè)例子

輸入：

聚類數(shù)k = 3，西瓜樣本D如下圖：

編號(hào)	西瓜密度	西瓜含糖率
1	0.697	0.460
2	0.774	0.376
3	0.634	0.264
..	...	...
30	0.446	0.459

過(guò)程:

1. 從D中隨機(jī)選擇3個(gè)樣本作為初始均值向量{μ₁, μ₂, μ₃ }
   假設(shè)隨機(jī)選取的樣本為前三個(gè)樣本，則μ_1 =(0.697, 0.460), μ_2 = (0.774, 0.376), μ_3= (0.634, 0.264)
2. 計(jì)算樣本與各簇心{μ₁, μ₂,...,μ_k}的距離
   例如：第30個(gè)樣本據(jù)簇心的歐式距離分別為：d_{(30,1)} = \sqrt [] { (0.446 - 0.697)^2 + (0.459 - 0.460)^2}=0.251、d_{(30,2)}~ =\sqrt [] { (0.446 - 0.774)^2 + (0.459 - 0.376)^2}=0.338、d_{(30,3)}~ =\sqrt [] { (0.446 - 0.634)^2 + (0.459 - 0.264)^2}=0.271
3. x離哪個(gè)簇心近則將其劃分到哪個(gè)簇（{C₁, C₂, ...,C_k }）
   例如：d_(30,2)最大，故將第30個(gè)樣本劃分到C₂簇。
   ???簇劃分的結(jié)果為：C_1={\{x_3, x_5, x_6, x_7, x_8, x_9, x_{10}, x_{13}, x_{14}, x_{17}, x_{18}, x_{19}, x_{20}, x_{23}}\} C_2={\{ x_{11}, x_{12}, x_{16}, x_{20} }\} C_3={\{x_1, x_2, x_4, x_{15}, x_{21}x_{22}, x_{24}, x_{25}, x_{26}, x_{27}, x_{28}, x_{29}}\}
4. 將樣本都劃分到3個(gè)簇后，計(jì)算新的均值向量，更新簇新{μ₁, μ₂,...,μ_k}
   例如：μ_{1new} =(0.493, 0.208), μ_{2new }= (0.396, 0.076), μ_{3new}= (0.602, 0.395)
5. 重復(fù)2-3步，直到簇心向量未更新，或已最小化平方誤差：min E = \sum_{i=1}^k\sum_{x∈C_i}{||x-μ_i||_2^2}

參考資料：
《機(jī)器學(xué)習(xí)》 周志華
《machine learning》 Andrew Ng