吴恩达机器学习ex7：Kmeans分类

1、K-means分类
1.1、执行K-means算法
K-means算法能够自动将相似的数据样本分为多个簇。
其算法的步骤如下&＃xff1a;

% Initialize centroids
centroids &＃61; kMeansInitCentroids(X, K);
for iter &＃61; 1:iterations
% Cluster assignment step: Assign each data point to the
% closest centroid. idx(i) corresponds to cˆ(i), the index
% of the centroid assigned to example i
idx &＃61; findClosestCentroids(X, centroids);
% Move centroid step: Compute means based on centroid
% assignments
centroids &＃61; computeMeans(X, idx, K);
end


1.1.1、找到样本最近的中心点
对于每个样本i来说&＃xff1a;

此处ci表示的是样本点xi距离最近簇中心的索引&＃xff0c;uj指的是第j个簇中心的位置。
补充完整idx &＃61; findClosestCentroids(X, centroids)函数有&＃xff1a;

function idx &＃61; findClosestCentroids(X, centroids)K &＃61; size(centroids, 1);idx &＃61; zeros(size(X,1), 1);%distance &＃61; zeros(1,K);
%for i &＃61; 1:size(X,1)
% for j &＃61; 1:K
% distance(j) &＃61; (X(i,:)-centroids(j,:))*(X(i,:)-centroids(j,:))&＃39;;
% [temp,idx(i,1)] &＃61; min(distance);
% end
%enddistance &＃61; zeros(size(X,1),K);
for i&＃61;1:Kdistance(:,i)&＃61;sum((X - ones(size(X,1),1)*centroids(i,:)).*...(X - ones(size(X,1),1)*centroids(i,:)),2);
end
[temp,index] &＃61; min(distance&＃39;);
idx &＃61; index&＃39;;
end


运行程序有&＃xff1a;

Closest centroids for the first 3 examples: 1 3 2
(the closest centroids should be 1, 3, 2 respectively)


1.1.2、计算簇中心平均值
对于每个新的簇中心&＃xff0c;重新计算其坐标为&＃xff1a;

完成函数centroids &＃61; computeCentroids(X, idx, K)有&＃xff1a;

function centroids &＃61; computeCentroids(X, idx, K)% Useful variables
[m n] &＃61; size(X);% You need to return the following variables correctly.
centroids &＃61; zeros(K, n);for i &＃61; 1:Kindex &＃61; find(idx&＃61;&＃61;i);for j &＃61; 1:size(index,1)newXi(j,:) &＃61; X(index(j),:);endcentroids(i, :) &＃61; mean(newXi,1);newXi &＃61; zeros(1,n);
end
end


运行程序有&＃xff1a;

Centroids computed after initial finding of closest centroids: 2.428301 3.157924 5.813503 2.633656 7.119387 3.616684 the centroids should be[ 2.428301 3.157924 ][ 5.813503 2.633656 ][ 7.119387 3.616684 ]


1.2、样本数据集上的k-means算法
运行下列代码&＃xff1a;

load(&＃39;ex7data2.mat&＃39;);
K &＃61; 3;
max_iters &＃61; 10;
initial_centroids &＃61; [3 3; 6 2; 8 5];
[centroids, idx] &＃61; runkMeans(X, initial_centroids, max_iters, true);


1.3、簇中心的随机初始化
在实际中&＃xff0c;应该随机选择样本作为簇中心坐标&＃xff0c;对簇中心进行初始化。
补充完整函数centroids &＃61; kMeansInitCentroids(X, K)&＃xff0c;有&＃xff1a;

function centroids &＃61; kMeansInitCentroids(X, K)
centroids &＃61; zeros(K, size(X, 2));randidx &＃61; randperm(size(X,1));
centroids &＃61; X(randidx(1:K),:);end


改用随机初始化簇中心的方式执行k-means算法&＃xff0c;执行下列代码&＃xff1a;

clear
load(&＃39;ex7data2.mat&＃39;);K &＃61; 3;
max_iters &＃61; 10;
initial_centroids &＃61; kMeansInitCentroids(X, K);
[centroids, idx] &＃61; runkMeans(X, initial_centroids, max_iters, true);


得到的分类为&＃xff1a;

1.4、使用K-means算法进行图像压缩
在本小节&＃xff0c;将使用K-means算法进行图像压缩。在一个24位的彩色图像中&＃xff0c;每个像素由3个8位不带符号整型构成&＃xff0c;灰度变化范围为0-255&＃xff0c;其分别代表RGB。该图像含有上千种颜色&＃xff0c;本次需要将颜色压缩至16种。
为了进行压缩&＃xff0c;需要存储该16种颜色的RGB值&＃xff0c;并且图像中的每个像素需要存储其分类到16种颜色的索引。
1.4.1、像素的K-means算法
执行下列代码&＃xff1a;

>> A &＃61; double(imread(&＃39;bird_small.png&＃39;));
>> A &＃61; A / 255;
>> img_size &＃61; size(A);
>> X &＃61; reshape(A, img_size(1) * img_size(2), 3);
>> K &＃61; 16;
>> max_iters &＃61; 10;
>> initial_centroids &＃61; kMeansInitCentroids(X, K);
>> [centroids, idx] &＃61; runkMeans(X, initial_centroids, max_iters);


得到16个簇中心为&＃xff1a;

下面对原图像进行压缩&＃xff0c;其关键的一步即为根据将簇中心&＃xff08;即对应的16种颜色&＃xff09;映射到对应的点。

>> idx &＃61; findClosestCentroids(X, centroids);
>> X_recovered &＃61; centroids(idx,:);
>> X_recovered &＃61; reshape(X_recovered, img_size(1), img_size(2), 3);
>> subplot(1, 2, 1);
>> imagesc(A);
>> title(&＃39;Original&＃39;);
>> subplot(1, 2, 2);
>> imagesc(X_recovered);
>> title(sprintf(&＃39;Compressed, with %d colors.&＃39;, K));