機器學習之深入理解K-means、與KNN算法區別及其代碼實現
K-means方法是一種 非監督學習 的算法，它解決的是 聚類問題。
1、 算法簡介 ：K-means方法是聚類中的經典算法，數據挖掘十大經典算法之一；算法接受參數k,然后將事先輸入的n個數據對象劃分為k個聚類以便使得所獲得的聚類滿足聚類中的對象相似度較高，而不同聚類中的對象相似度較小。
2、 算法思想： 以空間中k個點為中心進行聚類，對最靠近他們的對象歸類，通過迭代的方法，逐次更新各聚類中心的值，直到得到最好的聚類結果。
3、 算法描述：
（1）適當選擇c個類的初始中心；
（2）在第k次迭代中，對任意一個樣本，求其到c各中心的距離，將該樣本歸到距離最短的那個中心所在的類；
（3）利用均值等方法更新該類的中心值；
（4）對于所有的C個聚類中心，如果利用（2）（3）的迭代法更新后，值保持不變，則迭代結束；否則繼續迭代。
4、 算法舉例：
我們假設藥物A、B、C、D有兩個特征值，分別是藥物重量以及PH值。
| 藥物名稱 | 藥物重量 | 藥物PH值 |
|---|---|---|
| A | 1 | 1 |
| B | 2 | 1 |
| C | 4 | 3 |
| D | 5 | 4 |
現在我們要對這四個藥物進行聚類，已知我們要分成兩類，那么我們該怎么做呢？
首先我們把上面的數據畫到二位坐標系當中 A ( 1 , 1 ) , B ( 2 , 1 ) , ( 4 , 3 ) , D ( 5 , 4 )
初始時，我們先假設藥物A為聚類1的中心點，B為聚類2的中心點，那么初始時的中心坐標分別為 c 1 = ( 1 , 1 ) , c 2 = ( 2 , 1 )
，矩陣D的第一行代表各個點到中心點 c 1 的距離，第二行代表各個點到中心點 c 2 的距離；那么初始矩陣 D 0 表示成如下：
D 0 = [ 0 1 1 0 3.61 2.83 5 4.24 ]
矩陣 G
代表樣本應該歸屬于哪個聚類，第一行代表各個點是否屬于中心 c 1 所在的類（0代表不在，1代表在），第二行代表各個點是否屬于中心 c 2 所在的類（0代表不在，1代表在）；那么此時 G 0 表示成如下：
G 0 = [ 1 0 0 1 0 1 0 1 ]
由矩陣 G 0 可知A藥物屬于一個類，B、C、D屬于一類；
然后，利用均值等方法更新該類的中心值。
c 1 = （ 1 , 1 ）
c 2 = （ 2 + 4 + 5 3 , 1 + 3 + 4 3 ） = ( 13 3 , 8 3 )
上圖是更新后的坐標圖，對應的中心點也發生了變化。
因為中心點跟上次不一樣了，所以我們又可以對樣本點進行重新劃分。劃分的方法還是跟以前一模一樣，我們先計算出矩陣 D 1
表示成如下：
D 1 = [ 0 3.14 1 2.36 3.61 0.47 5 1.89 ]
此時 G 1
表示成如下：
G 1 = [ 1 0 1 0 0 1 0 1 ]
由矩陣 G 1 可知A、B藥物屬于一個類，C、D屬于一類；
然后，利用均值等方法再次更新該類的中心值。
c 1 = （ 1 + 2 2 , 1 + 1 2 ） = ( 1.5 , 1 )
c 2 = （ 4 + 5 2 , 3 + 4 2 ） = ( 4.5 , 3.5 )
上圖是更新后的坐標圖，對應的中心點也發生了變化。
因為中心點跟上次不一樣了，所以我們又可以對樣本點進行重新劃分。劃分的方法還是跟以前一模一樣，我們先計算出矩陣 D 2
表示成如下：
D 2 = [ 0.5 4.30 0.5 3.54 3.20 0.71 4.61 0.71 ]
此時 G 2
表示成如下：
G 2 = [ 1 0 1 0 0 1 0 1 ]
由矩陣 G 2 可知A、B藥物屬于一個類，C、D屬于一類；
然后，利用均值等方法再次更新該類的中心值。
c 1 = （ 1 + 2 2 , 1 + 1 2 ） = ( 1.5 , 1 )
c 2 = （ 4 + 5 2 , 3 + 4 2 ） = ( 4.5 , 3.5 )
因為對應的中心點并沒有發生變化，所以迭代停止，計算完畢。
本算法的時間復雜度：O(tkmn)，其中，t為迭代次數，k為簇的數目，m為記錄數，n為維數；
空間復雜度：O((m+k)n)，其中，k為簇的數目，m為記錄數，n為維數。
適用范圍：
K-menas算法試圖找到使平凡誤差準則函數最小的簇。當潛在的簇形狀是凸面的，簇與簇之間區別較明顯，且簇大小相近時，其聚類結果較理想。前面提到，該算法時間復雜度為O(tkmn)，與樣本數量線性相關，所以，對于處理大數據集合，該算法非常高效，且伸縮性較好。但該算法除了要事先確定簇數K和對初始聚類中心敏感外，經常以局部最優結束，同時對“噪聲”和孤立點敏感，并且該方法不適于發現非凸面形狀的簇或大小差別很大的簇。
缺點：
1、聚類中心的個數K 需要事先給定，但在實際中這個 K 值的選定是非常難以估計的，很多時候，事先并不知道給定的數據集應該分成多少個類別才最合適；
2、Kmeans需要人為地確定初始聚類中心，不同的初始聚類中心可能導致完全不同的聚類結果。（可以使用K-means++算法來解決）
算法代碼實現：
main.m
clear all;
close all;
clc;
%第一類數據
mu1=[0 0 0]; %均值
S1=[0.3 0 0;0 0.35 0;0 0 0.3]; %協方差
data1=mvnrnd(mu1,S1,100); %產生高斯分布數據
%%第二類數據
mu2=[1.25 1.25 1.25];
S2=[0.3 0 0;0 0.35 0;0 0 0.3];
data2=mvnrnd(mu2,S2,100);
%第三個類數據
mu3=[-1.25 1.25 -1.25];
S3=[0.3 0 0;0 0.35 0;0 0 0.3];
data3=mvnrnd(mu3,S3,100);
%顯示數據
plot3(data1(:,1),data1(:,2),data1(:,3),'+');
hold on;
plot3(data2(:,1),data2(:,2),data2(:,3),'r+');
plot3(data3(:,1),data3(:,2),data3(:,3),'g+');
grid on;
%三類數據合成一個不帶標號的數據類
data=[data1;data2;data3]; %這里的data是不帶標號的
%k-means聚類
[u re]=KMeans(data,3); %最后產生帶標號的數據，標號在所有數據的最后，意思就是數據再加一維度
[m n]=size(re);
%最后顯示聚類后的數據
figure;
hold on;
for i=1:m
if re(i,4)==1
plot3(re(i,1),re(i,2),re(i,3),'ro');
elseif re(i,4)==2
plot3(re(i,1),re(i,2),re(i,3),'go');
else
plot3(re(i,1),re(i,2),re(i,3),'bo');
end
end
grid on;
K-Means.m
%N是數據一共分多少類
%data是輸入的不帶分類標號的數據
%u是每一類的中心
%re是返回的帶分類標號的數據
function [u re]=KMeans(data,N)
[m n]=size(data); %m是數據個數，n是數據維數
ma=zeros(n); %每一維最大的數
mi=zeros(n); %每一維最小的數
u=zeros(N,n); %隨機初始化，最終迭代到每一類的中心位置
for i=1:n
ma(i)=max(data(:,i)); %每一維最大的數
mi(i)=min(data(:,i)); %每一維最小的數
for j=1:N
u(j,i)=ma(i)+(mi(i)-ma(i))*rand(); %隨機初始化，不過還是在每一維[min max]中初始化好些
end
end
while 1
pre_u=u; %上一次求得的中心位置
for i=1:N
tmp{i}=[]; % 公式一中的x(i)-uj,為公式一實現做準備
for j=1:m
tmp{i}=[tmp{i};data(j,:)-u(i,:)];
end
end
quan=zeros(m,N);
for i=1:m %公式一的實現
c=[];
for j=1:N
c=[c norm(tmp{j}(i,:))];
end
[junk index]=min(c);
quan(i,index)=norm(tmp{index}(i,:));
end
for i=1:N %公式二的實現
for j=1:n
u(i,j)=sum(quan(:,i).*data(:,j))/sum(quan(:,i));
end
end
if norm(pre_u-u)<0.1 %不斷迭代直到位置不再變化
break;
end
end
re=[];
for i=1:m
tmp=[];
for j=1:N
tmp=[tmp norm(data(i,:)-u(j,:))];
end
[junk index]=min(tmp);
re=[re;data(i,:) index];
end
end
K-means、和KNN算法比較
KNN(K-Nearest Neighbor)介紹
算法思路：如果一個樣本在特征空間中的k個最相似(即特征空間中最鄰近)的樣本中的大多數屬于某一個類別，則該樣本也屬于這個類別。該方法在定類決策上只依據最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。
看下面這幅圖：
KNN的算法過程是是這樣的：
從上圖中我們可以看到，圖中的數據集是良好的數據，即都打好了label，一類是藍色的正方形，一類是紅色的三角形，那個綠色的圓形是我們待分類的數據。
如果K=3，那么離綠色點最近的有2個紅色三角形和1個藍色的正方形，這3個點投票，于是綠色的這個待分類點屬于紅色的三角形
如果K=5，那么離綠色點最近的有2個紅色三角形和3個藍色的正方形，這5個點投票，于是綠色的這個待分類點屬于藍色的正方形
我們可以看到，KNN本質是基于一種數據統計的方法！其實很多機器學習算法也是基于數據統計的。
KNN是一種memory-based learning，也叫instance-based learning，屬于lazy learning。即它沒有明顯的前期訓練過程，而是程序開始運行時，把數據集加載到內存后，不需要進行訓練，就可以開始分類了。
具體是每次來一個未知的樣本點，就在附近找K個最近的點進行投票。
KNN和K-Means的區別
參考：
來自：http://blog.csdn.net/sinat_35512245/article/details/55051306