Kmeans算法，又叫做K均值聚類算法，可以說是無監(jiān)督聚類算法中最具代表性，最經(jīng)典的聚類算法了，這一算法的主要作用是將相似的樣本自動(dòng)歸到一個(gè)類別中。小編特意整理了這一經(jīng)典聚類算法的基本原理供大家參考，希望對大家有所幫助。

一、首先來看一下Kmeans算法的效果

#通過簡單的例子來直接查看K均值聚類的效果
from sklearn.cluster import KMeans
import matplotlib.pyplot as plt
import numpy as np
%matplotlib inline

#聚類前
X = np.random.rand(100,2)
plt.scatter(X[:,0],X[:,1], marker='o')

#聚類后
kmeans = KMeans(n_clusters=4).fit(X)
label_pred = kmeans.labels_
plt.scatter(X[:,0],X[:,1],c=label_pred)
plt.show()

二、Kmeans算法基本原理

假定給定數(shù)據(jù)樣本X，包含了n個(gè)對象

其中每個(gè)對象都具有m個(gè)維度的屬性。Kmeans算法的目標(biāo)是將n個(gè)對象依據(jù)對象間的相似性聚集到指定的k個(gè)類簇中，每個(gè)對象屬于且僅屬于一個(gè)其到類簇中心距離最小的類簇中。對于Kmeans，首先需要初始化k個(gè)聚類中心{C1.C2.C3....,Ck},1<k≤n,然后通過計(jì)算每一個(gè)對象到每一個(gè)聚類中心的歐式距離，如下式所示

依次比較每一個(gè)對象到每一個(gè)聚類中心的距離，將對象分配到距離最近的聚類中心的類簇中，得到k個(gè)類簇{S1.S2.S3....,Sk}

Kmeans算法用中心定義了類簇的原型，類簇中心就是類簇內(nèi)所有對象在各個(gè)維度的均值，其計(jì)算公式如下

代碼實(shí)現(xiàn)

Kmeans算法
% 輸入：
% data 輸入的不帶分類標(biāo)號(hào)的數(shù)據(jù)
% K 數(shù)據(jù)一共分多少類
% iniCentriods 自行指定初始聚類中心
% iterations 迭代次數(shù)

% 輸出：
% Idx 返回的分類標(biāo)號(hào)
% centroids 每一類的中心
% Distance 類內(nèi)總距離

 
function [Idx,centroids,Distance]=KMeans(data,K,iniCentriods,iterations)
[numOfData,numOfAttr]=size(data); % numOfData是數(shù)據(jù)個(gè)數(shù)，numOfAttr是數(shù)據(jù)維數(shù)
centroids=iniCentriods;
%% 迭代
for iter=1:iterations
    pre_centroids=centroids;% 上一次求得的中心位置
    
    tags=zeros(numOfData,K);
    %% 尋找最近中心，更新中心
    for i=1:numOfData
        D=zeros(1,K);% 每個(gè)數(shù)據(jù)點(diǎn)與每個(gè)聚類中心的標(biāo)準(zhǔn)差
        Dist=D;
        
        % 計(jì)算每個(gè)點(diǎn)到每個(gè)中心點(diǎn)的標(biāo)準(zhǔn)差
        for j=1:K
            Dist(j)=norm(data(i,:)-centroids(j,:),2);
        end
        
        [minDistance,index]=min(Dist);% 尋找距離最小的類別索引
        tags(i,index)=1;% 標(biāo)記最小距離所處的位置（類別）
    end
    
    
    %% 取均值更新聚類中心點(diǎn)
    for i=1:K
        if sum(tags(:,i))~=0
            % 未出現(xiàn)空類，計(jì)算均值作為下一聚類中心
            for j=1:numOfAttr
                centroids(i,j)=sum(tags(:,i).*data(:,j))/sum(tags(:,i));
            end
        else % 如果出現(xiàn)空類，從數(shù)據(jù)集中隨機(jī)選中一個(gè)點(diǎn)作為中心
            randidx = randperm(size(data, 1));
            centroids(i,:) = data(randidx(1),:);
            tags(randidx,:)=0;
            tags(randidx,i)=1;
        end
    end
    
   
    if sum(norm(pre_centroids-centroids,2))<0.001  % 不斷迭代直到位置不再變化
        break;
    end
    
    
end

%% 計(jì)算輸出結(jié)果
Distance=zeros(numOfData,1);
Idx=zeros(numOfData,1);
for i=1:numOfData
    D=zeros(1,K);% 每個(gè)數(shù)據(jù)點(diǎn)與每個(gè)聚類中心的標(biāo)準(zhǔn)差
    Dist=D;
    % 計(jì)算每個(gè)點(diǎn)到每個(gè)中心點(diǎn)的標(biāo)準(zhǔn)差
    for j=1:K
        Dist(j)=norm(data(i,:)-centroids(j,:),2);
    end
    
    [distance,idx]=min(Dist);% 尋找距離最小的類別索引
    distance=Dist(idx);
    
    Distance(i)=distance;
    Idx(i)=idx;
end
Distance=sum(Distance,1);% 計(jì)算類內(nèi)總距離
end

二、Kmeans的優(yōu)化算法

1.二分K-means算法

二分KMeans特點(diǎn)：解決K-Means算法對初始簇心比較敏感的問題，二分K-Means算法是一種弱化初 始質(zhì)心的一種算法

二分Kmeans 具體思路步驟：

(1) 將所有樣本數(shù)據(jù)放回到一個(gè)蔟隊(duì)列中

(2) 隊(duì)列中的一個(gè)蔟進(jìn)行 k = 2 的KMeans算法聚類形成兩個(gè)子蔟，將他們放回到蔟隊(duì)列中

(3)重復(fù)這個(gè)步驟，直到中止條件達(dá)到(主要是聚簇?cái)?shù)量)

選取隊(duì)列蔟二劃分的條件：

(1)選取蔟距離平方和SSE 最大的蔟進(jìn)行二劃分(優(yōu)先)。

(2)選取樣本較多的蔟進(jìn)行二劃分。

2.Kmeans++算法

K-Means++算法就是對K-Means隨機(jī)初始化質(zhì)心的方法的優(yōu)化。K-Means++的對于初始化質(zhì)心的優(yōu)化策略也很簡單，如下：

(1)從輸入的數(shù)據(jù)點(diǎn)集合中隨機(jī)選擇一個(gè)點(diǎn)作為第一個(gè)聚類中心μ1

(2)

(3)選擇一個(gè)新的數(shù)據(jù)點(diǎn)作為新的聚類中心，選擇的原則是：D(x)較大的點(diǎn)，被選取作為聚類中心的概率較大

(4)重復(fù)2和3直到選擇出k個(gè)聚類質(zhì)心

(5)利用這k個(gè)質(zhì)心來作為初始化質(zhì)心去運(yùn)行標(biāo)準(zhǔn)的K-Means算法

簡單的來說， Kmeans++ 就是選擇離已選中心點(diǎn)最遠(yuǎn)的點(diǎn)。