KMeans聚類算法模式識(shí)別

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

2、點(diǎn)，mi是簇Ci的平均值。該目標(biāo)函數(shù)使生成的簇盡可能緊湊獨(dú)立，使用的距離度量是歐幾里得距離,當(dāng)然也可以用其他距離度量。k-means聚類算法的算法流程如下： 輸入：包含n個(gè)對(duì)象的數(shù)據(jù)庫(kù)和簇的數(shù)目k； 輸出：k個(gè)簇，使平方誤差準(zhǔn)則最小。 步驟：(1) 任意選擇k個(gè)對(duì)象作為初始的簇中心；(2) repeat；(3) 根據(jù)簇中對(duì)象的平均值，將每個(gè)對(duì)象(重新)賦予最類似的簇；(4) 更新簇的平均值，即計(jì)算每個(gè)簇中對(duì)象的平均值；(5) 直到不再發(fā)生變化。2. 主要代碼主程序：clc;clear;close all; % 聚類算法測(cè)試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); % 得到訓(xùn)練數(shù)據(jù)nClass = length(nSample); tlabel = ;tdata = ; for i = 1 : nClass tlabel = tlabel; i * ones(nSample(i), 1); tdata = tdata; datai;end % 調(diào)用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('初始數(shù)據(jù)'); 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聚類結(jié)果'); K-Means核心算法：f

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

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

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

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

10、 n; for i = 1 : k index = floor( (n-i+1)*rand() ) + i; % 交換i和index上的數(shù)據(jù) temp = data(index); data(index) = data(i); data(i) = temp; end out = data(1:k);end圖片聚類測(cè)試代碼：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. 結(jié)果分析針對(duì)給定的參數(shù)K-Means算法三類聚類結(jié)果：圖1 初始數(shù)據(jù)和K-Means聚類結(jié)果當(dāng)初始數(shù)據(jù)給為如下時(shí)：K-Means算法三類聚類結(jié)果：圖2 初始數(shù)據(jù)和K-Means聚類結(jié)果由此可以看到，K-Means算法會(huì)把一些偏離中心較遠(yuǎn)的點(diǎn)分到其它簇內(nèi)。4.