K-Means聚類算法-模式識別

K-Means聚類算法算法原理k-means是劃分方法中較經(jīng)典的聚類算法之一。由于該算法的效率高，所以在對大規(guī)模數(shù)據(jù)進行聚類時被廣泛應(yīng)用。目前，許多算法均圍繞著該算法進行擴展和改進。k-means算法以k為參數(shù)，把n個對象分成k個簇，使簇內(nèi)具有較高的相似度，而簇間的相似度較低。k-means算法的處理過程如下：首先，隨機地選擇k個對象，每個對象初始地代表了一個簇的平均值或中心；對剩余的每個對象，根據(jù)其與各簇中心的距離，將它賦給最近的簇 ；然后重新計算每個簇的平均值。這個過程不斷重復，直到準則函數(shù)收斂。通常，采用平方誤差準則，其定義如下：Jrxxb-眄r這里E是數(shù)據(jù)庫中所有對象的平方誤差的總和， p是空間中的點，mi是簇Ci的平均值。該目標函數(shù)使生成的簇盡可能緊湊獨立，使用的距離度量是歐幾里得距離，當然也可以用其他距離度量。k-means聚類算法的算法流程如下：輸入：包含n個對象的數(shù)據(jù)庫和簇的數(shù)目k；輸出：k個簇，使平方誤差準則最小。步驟：任意選擇k個對象作為初始的簇中心；repeat；根據(jù)簇中對象的平均值，將每個對象(重新)賦予最類似的簇；更新簇的平均值，即計算每個簇中對象的平均值;直到不再發(fā)生變化。主要代碼主程序：clc;clear;closeall;%%聚類算法測試nSample=[500,500,500];%3維情況dim=3;coeff={[-20.8;-10.9;20.7;],[10.9;-20.7;-20.8;],[-20.7;20.8;-10.9;],};data=createSample(nSample,dim,coeff);%%得到訓練數(shù)據(jù)nClass=length(nSample);tlabel=[];tdata=[];fori=1:nClasstlabel=[tlabel;i*ones(nSample(i),1)];tdata=[tdata;data{i}];end%%調(diào)用k-means聚類算法[label]=stpKMeans(tdata,nClass);%%繪圖result=cell(1,nClass);index=0;fori=1:nClassindex=find(label(:,1)==i);result{i}=tdata(index,:);endfigure;subplot(1,2,1);plot3(data{1}(:,1),data{1}(:,2),data{1}(:,3),data{2}(:,1),data{2}(:,2),data{2}(:,3), 'o'data{3}(:,1),data{3}(:,2),data{3}(:,3), 'x');title('初始數(shù)據(jù)');subplot(1,2,2);'o',plot3(result{1}(:,1),result{1}(:,2),result{1}(:,3),'o',result{2}(:,1),result{2}(:,2),result{2}(:,3),result{3}(:,1),result{3}(:,2),result{3}(:,3),title( 'K-Means聚類結(jié)果');K-Means核心算法：function [label]=stpKMeans(data,k)%%KMeans聚類算法，參考%http://www.c/William_Fire/archive/2013/02/09/2909499.html%%%輸入%data 原始數(shù)據(jù)%k 聚多少個簇%%%輸岀%label 按照data數(shù)據(jù)的順序，每個樣本的簇號的列表[n,dim]=size(data);label=zeros(n,1);%任選k個對象作為初始的簇中心seq=stpRandN_K(n,k);nowMeans=data(seq,:);fori=1:klabel(seq(i))=i;enddist=zeros(n,k);

while(true)%計算數(shù)據(jù)到每個簇的歐幾里得距離fori=1:ktemp=data;forj=1:dim%先讓數(shù)據(jù)減去第j個特征temp(:,j)=data(:,j)-nowMeans(i,j);end%點乘后再相加球的距離的平方temp=temp.*temp;dist(:,i)=sum(temp,2);end%從k種距離中找岀最小的，并計算修改次數(shù)[~,Iabel2]=min(dist,[],2);editElem=sum(label(:,1)~=label2(:,1));label=label2;%fori=1:n% % 根據(jù)均值將當前的每個元素重新分簇% minDist=inf;% index=-1;% % 從當前的k個均值中找到離元素 i% forj=1:k% dist=data(i,:)-nowMeans(j,:);% dist=dot(dist,dist);label跟上一次不一樣）最近的一個，將其劃分到該簇label跟上一次不一樣）最近的一個，將其劃分到該簇% if(dist<minDist)% % 修改最近的距離，并記錄測試的簇號% minDist= dist;% index=j;% end% end%% % 判斷是該元素是否重新劃分了簇% if(index~=label(i))% editElem=editElem+1;% label(i)=index;% end%%endifeditElem==0%表示本次沒有修改，那么跳岀循環(huán)break;end%重新分簇后，重新計算均值fori=1:k%計算第k簇的均值[index]=find(label(:,1)==i);nowMeans(i,:)=mean(data(index,:));endendend從n個元素中隨機抽取K個元素的代碼:function[out]=stpRandN_K(n,k)%%從1-n中隨機選中k個不同的元素data=1:n;fori=1:kindex=floor((n-i+1)*rand())+i;%交換i和index上的數(shù)據(jù)temp=data(index);data(index)=data(i);data(i)=temp;endout=data(1:k);end圖片聚類測試代碼：closeall;clc;clear;rgbdata=imread( 'dataWg-1.jpg' );labdata=stpRgb2Lab(rgbdata);[sm,sn,~]=size(labdata);sN=sm*sn;nClass=4;labdata=reshape(labdata,sN,3);[label]=stpKMeans(labdata,nClass);label=reshape(label,sm,sn);figure;subplot(1,2,1);imshow(rgbdata);holdon;subplot(1,2,2);TX=1:sn;TY=1:sm;imagesc(TX,TY,label);結(jié)果分析針對給定的參數(shù)nSanple=[SOOj500^500],%3維情況dim=3：coeff-{[-20.S; -10.9:20.7:J [10.9：-20.7：-20.8：]「…0,7;20務(wù)：-1Q.9;h】；K-Means算法三類聚類結(jié)果:圖1初始數(shù)據(jù)和K-Means聚類結(jié)果當初始數(shù)據(jù)給為如下時：R?案発算迭測試nSample=[5QC>50Oj同Q]:#3維情況di>=3;coeff={['2K3. -1El：2L2.L....[I1.2;-2h3;-21.1;jj...[-21.1;20.2;-I1.3;]r}.K-Means算法三類聚類結(jié)果:圖2初始數(shù)據(jù)和K-Means聚類結(jié)果由此可以看到，K-Means算法會