所謂聚類問題，就是給定一個(gè)元素集合D，其中每個(gè)元素具有n個(gè)可觀察屬性，使用某種算法將D劃分成k個(gè)子集，要求每個(gè)子集內(nèi)部的元素之間相異度盡可能低，而不同子集的元素相異度盡可能高。其中每個(gè)子集叫做一個(gè)簇。

與分類不同，分類是示例式學(xué)習(xí)，要求分類前明確各個(gè)類別，并斷言每個(gè)元素映射到一個(gè)類別，而聚類是觀察式學(xué)習(xí)，在聚類前可以不知道類別甚至不給定類別數(shù)量，是無監(jiān)督學(xué)習(xí)的一種。目前聚類廣泛應(yīng)用于統(tǒng)計(jì)學(xué)、生物學(xué)、數(shù)據(jù)庫技術(shù)和市場營銷等領(lǐng)域，相應(yīng)的算法也非常的多。

K-Means算法實(shí)例

例：以下是一組用戶的年齡數(shù)據(jù)，將K值定義為2對(duì)用戶進(jìn)行聚類。并隨機(jī)選擇16和22作為兩個(gè)類別的初始質(zhì)心。

Data_Age = ［15，15， 16， 19， 19， 20， 20， 21， 22， 28， 35， 40， 41， 42， 43， 44， 60， 61， 65］;

CenterId1 =16， CenterId2 = 22

（1）、計(jì)算距離并劃分?jǐn)?shù)據(jù)

通過計(jì)算所有用戶的年齡值與初始質(zhì)心的距離對(duì)用戶進(jìn)行第一次分類。計(jì)算距離的方法是使用歐式距離。距離值越小表示兩個(gè)用戶間年齡的相似度越高。

第一次迭代：

Data_Age = ［15，15， 16， 19， 19， 20， 20， 21， 22， 28， 35， 40， 41， 42， 43， 44， 60， 61， 65］;

Distance（16）= ［1， 1， 0， 3， 3， 4， 4， 5， 6， 12， 19， 24， 25， 26， 27， 28，44， 45， 49］;

Distance（22）= ［7， 7，6， 3， 3， 2， 2， 1， 0， 6， 13， 18， 19， 20， 21， 22， 38， 39，43］;

Group1_（16）= ［15，15， 16］; Mean =15.33

Group2_（22）= ［19，19， 20， 20， 21， 22， 28， 35， 40， 41， 42， 43， 44， 60， 61， 65］; Mean = 36.25

（2）、使用均值作為新的質(zhì)心

將兩個(gè)分組中數(shù)據(jù)的均值作為新的質(zhì)心，并重復(fù)之前的方法，迭代計(jì)算每個(gè)數(shù)據(jù)點(diǎn)到新質(zhì)心的距離，將數(shù)據(jù)點(diǎn)劃分到與之距離較小的類別中。

第二次迭代：

Data_Age = ［15，15， 15.33， 16， 19， 19， 20， 20， 21， 22， 28，35， 36.25， 40， 41， 42， 43， 44， 60， 61， 65］;

Distance（15.33）=［0.33， 0.33， 0.67，3.67， 3.67， 4.67， 4.67， 5.67， 6.67， 12.67， 19.67， 24.67， 25.67， 26.67，27.67， 28.67， 44.67， 45.67， 49.67］;

Distance（36.25）=［21.25， 21.25， 20.25， 17.25， 17.25， 16.25，16.25， 15.25， 14.25， 8.25， 1.25， 3.75， 4.75， 5.75，6.75， 7.75， 23.75， 24.75， 28.75］;

Group1_（15.33）=［ 15， 15， 16， 19， 19， 20， 20， 21， 22］; Mean = 18.56

Group2_（36.25）=［ 28， 35， 40， 41， 42， 43， 44， 60， 61，65］; Mean = 45.90

第三次迭代：

Data_Age = ［15，15， 16， 18.56， 19， 19， 20， 20， 21， 22， 28，35， 40， 41， 42， 43， 44， 45.90， 60， 61， 65］;

Distance（18.56）=［3.56， 3.56， 2.56，0.44， 0.44， 1.44， 1.44， 2.44， 3.44， 9.44， 16.44， 21.44， 22.44， 23.44，24.44， 25.44， 41.44， 42.44， 46.44］;

Distance（45.90）=［30.90， 30.90， 29.90， 26.90， 26.90， 25.90，25.90， 24.90， 23.90， 17.90， 10.90， 5.90， 4.90， 3.90，2.90， 1.90， 14.10， 15.10， 19.10］;

Group1_（18.56）=［ 15， 15， 16， 19， 19， 20， 20， 21， 22， 28］; Mean = 19.50

Group2_（45.90）=［ 35， 40， 41， 42， 43， 44， 60， 61， 65］; Mean = 47.89

第四次迭代：

Data_Age = ［15，15， 16， 19， 19， 19.50， 20， 20， 21， 22， 28，35， 40， 41， 42， 43， 44， 47.89， 60， 61， 65］;

Distance（19.50）=［4.5， 4.5， 3.5，0.5， 0.5， 0.5， 0.5， 1.5， 2.5， 8.5， 15.5， 20.5， 21.5， 22.5， 23.5， 24.5，40.5， 41.5， 45.5］;

Distance（47.89）=［32.89， 32.89， 31.89， 28.89， 28.89， 27.89，27.89， 26.89， 25.89， 19.89， 12.89， 7.89， 6.89， 5.89，4.89， 3.89， 12.11， 13.11， 17.11］;

Group1_（19.50）=［ 15， 15， 16， 19， 19， 20， 20， 21， 22，28］; Mean = 19.50

Group2_（47.89）=［ 35， 40， 41， 42， 43， 44， 60， 61， 65］; Mean = 47.89

（3）、算法停止條件

迭代計(jì)算每個(gè)數(shù)據(jù)到新質(zhì)心的距離，直到新的質(zhì)心和原質(zhì)心相等，算法結(jié)束。

MATLAB中的kmeans函數(shù)

MATLAB中的kmeans函數(shù)采用的是將N*P的矩陣X劃分為K個(gè)類，使得類內(nèi)對(duì)象之間的距離最大，而類之間的距離最小。

使用方法：

Idx = Kmeans（X，K）

［Idx， C］ = Kmeans（X，K）

［Idc， C， sumD］ = Kmeans（X，K）

［Idx， C， sumD， D］ = Kmeans（X，K）

各輸入輸出參數(shù)介紹：

X---N*P的數(shù)據(jù)矩陣

K---表示將X劃分為幾類，為整數(shù)

Idx---N*1的向量，存儲(chǔ)的是每個(gè)點(diǎn)的聚類標(biāo)號(hào)

C---K*P的矩陣，存儲(chǔ)的是K個(gè)聚類質(zhì)心位置

sumD---1*K的和向量，存儲(chǔ)的是類間所有點(diǎn)與該類質(zhì)心點(diǎn)距離之和

D---N*K的矩陣，存儲(chǔ)的是每個(gè)點(diǎn)與所有質(zhì)心的距離

［┈］ = Kmeans（┈，’Param1’，’Val1’，’Param2’，’Val2’，┈）

其中參數(shù)Param1、Param2等，主要可以設(shè)置為如下：

1、’Distance’---距離測度

‘sqEuclidean’---歐氏距離

‘cityblock’---絕對(duì)誤差和，又稱L1

‘cosine’---針對(duì)向量

‘correlation’---針對(duì)有時(shí)序關(guān)系的值

‘Hamming’---只針對(duì)二進(jìn)制數(shù)據(jù)

2、’Start’---初始質(zhì)心位置選擇方法

‘sample’---從X中隨機(jī)選取K個(gè)質(zhì)心點(diǎn)

‘uniform’---根據(jù)X的分布范圍均勻的隨機(jī)生成K個(gè)質(zhì)心

‘cluster’---初始聚類階段隨機(jī)選取10%的X的子樣本（此方法初始使用’sample’方法）

Matrix提供一K*P的矩陣，作為初始質(zhì)心位置集合

3、’Replicates’---聚類重復(fù)次數(shù)，為整數(shù)

MATLAB代碼：

% KMeans算法的基本思想是初始隨機(jī)給定K個(gè)簇中心，按照最鄰近原則把待分類樣本點(diǎn)分到各個(gè)簇。

% 然后按平均法重新計(jì)算各個(gè)簇的質(zhì)心，從而確定新的簇心。一直迭代，直到簇心的移動(dòng)距離小于某個(gè)給定的值。

% 隨機(jī)獲取200個(gè)點(diǎn)

X = ［randn（50，2）+［-ones（50，1）， +ones（50，1）］; randn（50，2）+［ones（50，1）， ones（50，1）］; 。。。

randn（50，2）+［ones（50，1）， -ones（50，1）］; randn（50，2）+［-ones（50，1），-ones（50，1）］］;

%{

MATLAB中的kmeans函數(shù)采用的是將N*P的矩陣X劃分為K個(gè)類，使得類內(nèi)對(duì)象之間的距離最大，而類之間的距離最小。

使用方法：

Idx = Kmeans（X，K）

［Idx，C］ = Kmeans（X，K）

［Idc，C，sumD］ = Kmeans（X，K）

［Idx，C，sumD，D］ = Kmeans（X，K）

各輸入輸出參數(shù)介紹：

X---N*P的數(shù)據(jù)矩陣

K---表示將X劃分為幾類，為整數(shù)

Idx---N*1的向量，存儲(chǔ)的是每個(gè)點(diǎn)的聚類標(biāo)號(hào)

Ctrs---K*P的矩陣，存儲(chǔ)的是K個(gè)聚類質(zhì)心位置

sumD---1*K的和向量，存儲(chǔ)的是類間所有點(diǎn)與該類質(zhì)心點(diǎn)距離之和

D---N*K的矩陣，存儲(chǔ)的是每個(gè)點(diǎn)與所有質(zhì)心的距離

%}

opts = statset（‘Display’，‘final’）;

［Idx，Ctrs，SumD，D］ = kmeans（X，4，‘Replicates’，4，‘Options’，opts）;

% 畫出聚類為1的點(diǎn)。

% X（Idx==1，1），為第一類的樣本的第一個(gè)坐標(biāo)；X（Idx==1，2）為第一類的樣本的第二個(gè)坐標(biāo)

plot（X（Idx==1，1）， X（Idx==1，2）， ‘r.’， ‘MarkerSize’， 14）;

hold on;

plot（X（Idx==2，1）， X（Idx==2，2）， ‘b.’， ‘MarkerSize’， 14）;

hold on;

plot（X（Idx==3，1）， X（Idx==3，2）， ‘g.’， ‘MarkerSize’， 14）;

hold on;

plot（X（Idx==4，1）， X（Idx==4，2）， ‘y.’， ‘MarkerSize’， 14）;

hold on;

% 繪出聚類中心點(diǎn)，kx表示是交叉符

plot（Ctrs（：，1）， Ctrs（：，2）， ‘kx’， ‘MarkerSize’， 14， ‘LineWidth’， 4）;

legend（‘Cluster 1’， ‘Cluster 2’， ‘Cluster 3’， ‘Cluster 4’， ‘Centroids’， ‘Location’， ‘NW’）;

grid on;

%{

［┈］ = Kmeans（┈，’Param1’，’Val1’，’Param2’，’Val2’，┈）

其中參數(shù)Param1、Param2等，主要可以設(shè)置為如下：

1、‘Distance’---距離測度

‘sqEuclidean’---歐氏距離

‘cityblock’---絕對(duì)誤差和，又稱L1

‘cosine’---針對(duì)向量

‘correlation’---針對(duì)有時(shí)序關(guān)系的值

‘Hamming’---只針對(duì)二進(jìn)制數(shù)據(jù)

2、‘Start’---初始質(zhì)心位置選擇方法

‘sample’---從X中隨機(jī)選取K個(gè)質(zhì)心點(diǎn)

‘uniform’---根據(jù)X的分布范圍均勻的隨機(jī)生成K個(gè)質(zhì)心

‘cluster’---初始聚類階段隨機(jī)選取10%的X的子樣本（此方法初始使用’sample’方法）

Matrix提供一K*P的矩陣，作為初始質(zhì)心位置集合

3、‘Replicates’---聚類重復(fù)次數(shù)，為整數(shù)

%}