《K-Means聚类算法-模式识别》由会员分享，可在线阅读，更多相关《K-Means聚类算法-模式识别（11页珍藏版）》请在金锄头文库上搜索。
1、K-Means 聚类算法1. 算法原理k-means 是划分方法中较经典的聚类算法之一。由于该算法的效率高， 所以在对大规模数据进行聚类时被广泛应用。目前，许多算法均围绕着该算 法进行扩展和改进。k-means 算法以 k 为参数，把 n 个对象分成 k 个簇，使簇内具有较高 的相似度，而簇间的相似度较低。k-means算法的处理过程如下：首先，随 机地选择 k 个对象，每个对象初始地代表了一个簇的平均值或中心;对剩余 的每个对象，根据其与各簇中心的距离，将它赋给最近的簇;然后重新计算 每个簇的平均值。这个过程不断重复，直到准则函数收敛。通常，采用平方 误差准则，其定义如下：辰 x x a%
2、ri口】P左G这里 E 是数据库中所有对象的平方误差的总和， p 是空间中的点， mi 是簇 Ci 的平均值。该目标函数使生成的簇尽可能紧凑独立，使用的距离度 量是欧几里得距离,当然也可以用其他距离度量。 k-means 聚类算法的算法流 程如下：输入：包含 n 个对象的数据库和簇的数目 k；输出： k 个簇，使平方误差准则最小。步骤：(1) 任意选择 k 个对象作为初始的簇中心；(2) repeat；(3) 根据簇中对象的平均值，将每个对象(重新)赋予最类似的簇；(4) 更新簇的平均值，即计算每个簇中对象的平均值；(5) 直到不再发生变化。2. 主要代码主程序：clc;clear;close
3、 all;% 聚类算法测试nSample = 500, 500, 500;% 3 维情况dim =3;coeff= -2 0.8;1 0.9; 2 0.7.1 0.9;-20.7; -2 0.8;,.-2 0.7;20.8; -1 0.9;, ;data = createSample(nSample, dim , coeff); % 得到训练数据nClass = length(nSample);tlabel = ;tdata = ;for i = 1 : nClasstlabel = tlabel; i * ones(nSample(i), 1);tdata = tdata; datai;en
4、d% 调用 k-means 聚类算法 label = stpKMeans( tdata, nClass);% 绘图result = cell(1, nClass);index = 0;for i = 1 : nClassindex = find(label(:,1) = i);resulti = tdata(index, :);endfigure;subplot(1, 2, 1);plot3(data1(:, 1), data1(:, 2), data1(:, 3), *, . data2(:, 1), data2(:, 2), data2(:, 3), o, . data3(:, 1), d
5、ata3(:, 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核心算法：function label = stpKMeans( data, k)% KMeans 聚类算法，参考%http:/ 输入%
6、 data原始数据% k聚多少个簇% 输出% label 按照 data 数据的顺序，每个样本的簇号的列表n, dim = size(data);label = zeros(n, 1);% 任选 k 个对象作为初始的簇中心seq = stpRandN_K(n, k);nowMeans = data(seq, :);for i = 1 : klabel(seq(i) = i;enddistzeros(n, k);while(true) % 计算数据到每个簇的欧几里得距离for i = 1 : ktemp = data;for j = 1 : dim% 先让数据减去第 j 个特征temp(:, j
7、) = 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;%for i = 1 : n%根据均值将当前的每个元素重新分簇% minDist = inf;%index = -1;%从% 当前的 k 个均值中找到离元
8、素 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) )editElem = editElem + 1; label(i) = index;endendif editElem = 0% 表示本次没有修改，那么跳出循环 break;end% 重新分簇后，重
9、新计算均值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 : n;for i = 1 : kindex = floor( (n-i+1)*rand() ) + i;% 交换 i 和 index 上的数据temp = data(index);data(index) = da
10、ta(i);data(i) = temp;endout = data(1:k);end图片聚类测试代码：close all;clc;clear;rgbdata = imread(datag-1.jpg);labdata = stpRgb2Lab(rgbdata);sm, sn,size(labdata);sNsmsn;nClass4;labdata = reshape(labdata, sN, 3); label = stpKMeans( labdata, nClass);label = reshape(label, sm, sn);figure;subplot(1, 2, 1);imshow
11、(rgbdata);hold on;subplot(1, 2, 2);TX = 1 : sn;TY = 1 : sm;imagesc(TX, TY, label);3. 结果分析针对给定的参数%翳类算法痢试nSample = 500j 500； 500:% 3维情况dim = 3:coeff = -2 0. 8;-1 0. 9; 2 0. 7;,.1 0. 9; -2 0.7; -2 0. 8; h -2 0.7; 2 0.8; -1 0.9; , :K-Means 算法三类聚类结果：初始数据IIIIIIIIII II54321 Q -1-2-3-4-5K-Means聚类结果5|543210-
12、1-2-3-4图 1 初始数据和 K-Means 聚类结果当初始数据给为如下时：%聚类算法测试nSample = 500 500 500;% 3维情况dim = 3:coeff = -2 1.3;-1 1. 1 ; 2 1.2;,.1 1. 2; -2 1. 3 : -2 1. 1 :,.-2 1. 1 : 2 0.2; -1 1.3;, :K-Means 算法三类聚类结果：6.初始数据6K-Means聚类结果-6,*-N0 I-W 210-1-2-3-4-5-6图 2 初始数据和 K-Means 聚类结果由此可以看到，K-Means算法会把一些偏离中心较远的点分到其它簇内。4. 用于图片的结果以图片的在Lab颜色空间的三通道作为三个特征，每个像素为一个样本点,进行图片聚类，此时，如果类数为 8，则得到：图 3a 图片聚类（8 类）结果100200300400500600图 3b 图片聚类（8 类）结果聚类数量变为 15 时结果如下：图 4a 图片聚类（15类）结果图4b图片聚类（15类）结果当聚类为 4 的时候，结果为：图 5a 图片聚类（4类）结果图 5b 图片聚类（4类）结果
