KMeans聚類算法模式識別

1、K-Means聚類算法1. 算法原理k-means是劃分方法中較經典的聚類算法之一。由于該算法的效率高，所以在對大規(guī)模數據進行聚類時被廣泛應用。目前，許多算法均圍繞著該算法進行擴展和改進。k-means算法以k為參數，把n個對象分成k個簇，使簇內具有較高的相似度，而簇間的相似度較低。k-means算法的處理過程如下：首先，隨機地選擇k個對象，每個對象初始地代表了一個簇的平均值或中心;對剩余的每個對象，根據其與各簇中心的距離，將它賦給最近的簇;然后重新計算每個簇的平均值。這個過程不斷重復，直到準則函數收斂。通常，采用平方誤差準則，其定義如下：這里E是數據庫中所有對象的平方誤差的總和，p是空間中的

2、點，mi是簇Ci的平均值。該目標函數使生成的簇盡可能緊湊獨立，使用的距離度量是歐幾里得距離,當然也可以用其他距離度量。k-means聚類算法的算法流程如下： 輸入：包含n個對象的數據庫和簇的數目k； 輸出：k個簇，使平方誤差準則最小。 步驟：(1) 任意選擇k個對象作為初始的簇中心；(2) repeat；(3) 根據簇中對象的平均值，將每個對象(重新)賦予最類似的簇；(4) 更新簇的平均值，即計算每個簇中對象的平均值；(5) 直到不再發(fā)生變化。2. 主要代碼主程序：clc;clear;close all; % 聚類算法測試nSample = 500, 500, 500; % 3維情況dim =

3、 3;coeff = -2 0.8; -1 0.9; 2 0.7;, . 1 0.9; -2 0.7; -2 0.8; , . -2 0.7; 2 0.8; -1 0.9; , ; data = createSample(nSample, dim , coeff); % 得到訓練數據nClass = length(nSample); tlabel = ;tdata = ; for i = 1 : nClass tlabel = tlabel; i * ones(nSample(i), 1); tdata = tdata; datai;end % 調用k-means聚類算法 label = st

4、pKMeans( tdata, nClass); % 繪圖result = cell(1, nClass);index = 0;for i = 1 : nClass index = find(label(:,1) = i); resulti = tdata(index, :);end figure;subplot(1, 2, 1);plot3(data1(:, 1), data1(:, 2), data1(:, 3), '*', . data2(:, 1), data2(:, 2), data2(:, 3), 'o', . data3(:, 1), data3(

5、:, 2), data3(:, 3), 'x');title('初始數據'); subplot(1, 2, 2);plot3(result1(:, 1), result1(:, 2), result1(:, 3), '*', . result2(:, 1), result2(:, 2), result2(:, 3), 'o', . result3(:, 1), result3(:, 2), result3(:, 3), 'x');title('K-Means聚類結果'); K-Means核心算法：f

6、unction label = stpKMeans( data, k)% KMeans 聚類算法，參考% % 輸入% data 原始數據% k 聚多少個簇% 輸出% label 按照data數據的順序，每個樣本的簇號的列表 n, dim = size(data); label = zeros(n, 1); % 任選k個對象作為初始的簇中心 seq = stpRandN_K(n, k); nowMeans = data(seq, :); for i = 1 : k label(seq(i) = i; end dist = zeros(n, k); while(true) % 計算數據到每個簇的歐

7、幾里得距離 for i = 1 : k temp = data; for j = 1 : dim % 先讓數據減去第j個特征 temp(:, j) = data(:, j) - nowMeans(i, j); end % 點乘后再相加球的距離的平方 temp = temp .* temp; dist(:, i) = sum(temp, 2); end % 從k種距離中找出最小的，并計算修改次數（label跟上一次不一樣） , label2 = min(dist, , 2); editElem = sum(label(:, 1) = label2(:, 1); label = label2; %

8、 for i = 1 : n% % 根據均值將當前的每個元素重新分簇% minDist = inf;% index = -1;% % 從當前的k個均值中找到離元素i最近的一個，將其劃分到該簇% for j = 1 : k% dist = data(i,:) - nowMeans(j, :);% dist = dot(dist, dist);% % if(dist < minDist)% % 修改最近的距離，并記錄測試的簇號% minDist = dist;% index = j;% end% end% % % 判斷是該元素是否重新劃分了簇% if(index = label(i) )%

9、editElem = editElem + 1;% label(i) = index;% end% % end if editElem = 0 % 表示本次沒有修改，那么跳出循環(huán) break; end % 重新分簇后，重新計算均值 for i = 1 : k % 計算第k簇的均值 index = find(label(:, 1) = i ); nowMeans(i, :) = mean(data(index, :); end endend 從n個元素中隨機抽取K個元素的代碼：function out = stpRandN_K(n, k)% 從1-n中隨機選中k個不同的元素 data = 1 :

10、 n; for i = 1 : k index = floor( (n-i+1)*rand() ) + i; % 交換i和index上的數據 temp = data(index); data(index) = data(i); data(i) = temp; end out = data(1:k);end圖片聚類測試代碼：close all;clc;clear; rgbdata = imread('datag-1.jpg');labdata = stpRgb2Lab(rgbdata); sm, sn, = size(labdata); sN = sm * sn; nClass

11、= 4;labdata = reshape(labdata, sN, 3); label = stpKMeans( labdata, nClass);label = reshape(label, sm, sn);figure;subplot(1, 2, 1);imshow(rgbdata);hold on; subplot(1, 2, 2); TX = 1 : sn;TY = 1 : sm;imagesc(TX, TY, label);3. 結果分析針對給定的參數K-Means算法三類聚類結果：圖1 初始數據和K-Means聚類結果當初始數據給為如下時：K-Means算法三類聚類結果：圖2 初始數據和K-Means聚類結果由此可以看到，K-Means算法會把一些偏離中心較遠的點分到其它簇內。4.