K-Means聚类算法
1.算法原理
k-means是划分方法中较经典的聚类算法之一。
由于该算法的效率高，所以在对大规模数据进行聚类时被广泛应用。
目前，许多算法均围绕着该算法进行扩展和改进。
k-means算法以k为参数，把n个对象分成k个簇，使簇内具有较高的相似度，而簇间的相似度较低。
k-means算法的处理过程如下：首先，随机地选择k个对象，每个对象初始地代表了一个簇的平均值或中心;对剩余的每个对象，根据其与各簇中心的距离，将它赋给最近的簇;然后重新计算每个簇的平均值。
这个过程不断重复，直到准则函数收敛。
通常，采用平方误差准则，其定义如下：
这里E是数据库中所有对象的平方误差的总和，p是空间中的点，mi 是簇Ci的平均值。
该目标函数使生成的簇尽可能紧凑独立，使用的距离度量是欧几里得距离,当然也可以用其他距离度量。
k-means聚类算法的算法流程如下：
输入：包含n个对象的数据库和簇的数目k；
输出：k个簇，使平方误差准则最小。
步骤：
(1) 任意选择k个对象作为初始的簇中心；
(2) repeat；
(3) 根据簇中对象的平均值，将每个对象(重新)赋予最类似的簇；
(4) 更新簇的平均值，即计算每个簇中对象的平均值；
(5) 直到不再发生变化。
2.主要代码
主程序：
clc;
clear;
close all;
%% 聚类算法测试
nSample = [500, 500, 500];
% 3维情况
dim = 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; data{i}];
end
%% 调用k-means聚类算法
[ label ] = stpKMeans( tdata, nClass);
%% 绘图
result = cell(1, nClass);
index = 0;
for i = 1 : nClass
index = find(label(:,1) == i);
result{i} = tdata(index, :);
end
figure;
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('初始数据');
subplot(1, 2, 2);
plot3(result{1}(:, 1), result{1}(:, 2), result{1}(:, 3), '*', ... result{2}(:, 1), result{2}(:, 2), result{2}(:, 3), 'o', ...
result{3}(:, 1), result{3}(:, 2), result{3}(:, 3), 'x');
title('K-Means聚类结果');
K-Means核心算法：
function [ label ] = stpKMeans( data, k)
%% KMeans 聚类算法，参考
%
/William_Fire/archive/2013/02/09/2909499.html %
%% 输入
% 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)
% 计算数据到每个簇的欧几里得距离
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;
% 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) )
% editElem = editElem + 1;
% label(i) = index;
% end
%
% end
if editElem == 0
% 表示本次没有修改，那么跳出循环
break;
end
% 重新分簇后，重新计算均值
for i = 1 : k
% 计算第k簇的均值
[index] = find(label(:, 1) == i );
nowMeans(i, :) = mean(data(index, :));
end
end
end
从n个元素中随机抽取K个元素的代码：
function [ out ] = stpRandN_K(n, k)
%% 从1-n中随机选中k个不同的元素
data = 1 : 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('data\\g-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);
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.用于图片的结果
以图片的在Lab颜色空间的三通道作为三个特征，每个像素为一个样本点，进行图片聚类，此时，如果类数为8，则得到：
图3a 图片聚类（8类）结果
图3b 图片聚类（8类）结果聚类数量变为15时结果如下：
图4a 图片聚类（15类）结果
图4b 图片聚类（15类）结果当聚类为4的时候，结果为：
图5a 图片聚类（4类）结果
图5b 图片聚类（4类）结果。
