Kmeans++

2019-11-08 02:26:47

字體：大中小

來源：轉載

供稿：網友

Kmeans算法源碼

標簽（空格分隔）：算法學習

（1）算法概述

首先要來了解的一個概念就是聚類，簡單地說就是把相似的東西分到一組，同 Classification (分類)不同，對于一個 classifier ，通常需要你告訴它“這個東西被分為某某類”這樣一些例子，理想情況下，一個 classifier 會從它得到的訓練集中進行“學習”，從而具備對未知數據進行分類的能力，這種提供訓練數據的過程通常叫做 supervised learning (監督學習)，而在聚類的時候，我們并不關心某一類是什么，我們需要實現的目標只是把相似的東西聚到一起，因此，一個聚類算法通常只需要知道如何計算相似度就可以開始工作了，因此 clustering 通常并不需要使用訓練數據進行學習，這在 Machine Learning 中被稱作 unsupervised learning (無監督學習)。

　　我們經常接觸到的聚類分析，一般都是數值聚類，一種常見的做法是同時提取 N 種特征，將它們放在一起組成一個 N 維向量，從而得到一個從原始數據集合到 N 維向量空間的映射——你總是需要顯式地或者隱式地完成這樣一個過程，然后基于某種規則進行分類，在該規則下，同組分類具有最大的相似性。

　　假設我們提取到原始數據的集合為(x1, x2, …, xn)，并且每個xi為d維的向量，K-means聚類的目的就是，在給定分類組數k（k ≤ n）值的條件下，將原始數據分成k類 S = {S1, S2, …, Sk}，在數值模型上，即對以下表達式求最小值： /underset{/mathbf{S}} {/Operatorname{arg,min}} /sum_{i=1}^{k} /sum_{/mathbf x_j /in S_i} /left| /mathbf x_j - /boldsymbol/mu_i /right|^2 這里μi 表示分類Si 的平均值。

　　那么在計算機編程中，其又是如何實現的呢？其算法步驟一般如下：

1、從D中隨機取k個元素，作為k個簇的各自的中心。

2、分別計算剩下的元素到k個簇中心的相異度，將這些元素分別劃歸到相異度最低的簇。

3、根據聚類結果，重新計算k個簇各自的中心，計算方法是取簇中所有元素各自維度的算術平均數。

4、將D中全部元素按照新的中心重新聚類。

5、重復第4步，直到聚類結果不再變化。

6、將結果輸出。

（2）matlab源代碼實現

% 【函數描述】C=bsxfun(fun,A,B)：兩個數組間元素逐個計算，fun是函數句柄或者m文件，也可以為如下內置函數 % @plus 加 % @minus 減 % @times 數組乘 % @rdivide 左除 % @ldivide 右除 % For example：如何將一個矩陣的每行或每列元素分別擴大不同的倍數？% 如[1 2 3;4 5 6 ;7 8 9],第一列元素乘以1，第二列元素以2，第三列元素乘以4。% 利用bsxfun函數，可以給出下列代碼：% % a = [1,2,3;4,5,6;7,8,9];% acol = bsxfun(@times,a,[1 2 4])function [centroids, labels] = run_kmeans(X, k, max_iter)% 該函數實現Kmeans聚類% 輸入參數：% X為輸入樣本集，dxN% k為聚類中心個數% max_iter為kemans聚類的最大迭代的次數% 輸出參數：% centroids為聚類中心 dxk% labels為樣本的類別標記%% 采用K-means++算法初始化聚類中心% k-means++算法選擇初始seeds的基本思想就是：初始的聚類中心之間的相互距離要盡可能的遠。%% 1. 從輸入的數據點集合中隨機選擇一個點作為第一個聚類中心% 2. 對于數據集中的每一個點x，計算它與最近聚類中心(指已選擇的聚類中心)的距離D(x)% 3. 選擇一個新的數據點作為新的聚類中心，選擇的原則是：D(x)較大的點，被選取作為聚類中心的概率較大% 4. 重復2和3直到k個聚類中心被選出來% 5. 利用這k個初始的聚類中心來運行標準的k-means算法% % % 1. 先從我們的數據庫隨機挑個隨機點當“種子點”% 2. 對于每個點，我們都計算其和最近的一個“種子點”的距離D(x)并保存在一個數組里，然后把這些距離加起來得到Sum(D(x))。% 3. 然后，再取一個隨機值，用權重的方式來取計算下一個“種子點”。這個算法的實現是，先取一個能落在Sum(D(x))中的隨機值% Random，然后用Random -= D(x)，直到其<=0，此時的點就是下一個“種子點”。% 4. 重復2和3直到k個聚類中心被選出來% 5. 利用這k個初始的聚類中心來運行標準的k-means算法%% %第3步的核心思想：Sum(D(x))*random時，該值會以較大的概率落入D(x)較大的區間內，所以對應的點會以較大的概率被選中作為% 新的聚類中心。|-----5-----|----------10----------|----4----| centroids = X(:, 1 + round(rand * (size(X, 2)-1))); % 從輸入的數據點集合中隨機選擇一個點作為第一個聚類中心 labels = ones(1, size(X, 2)); % 初始化每個數據點的標號為1 for i = 2:k% pp = centroids(:, labels); D = X - centroids(:, labels); % 計算每一個點與聚類中心的差值 D = sqrt(dot(D, D, 1));% 每一點與聚類中心的差值的二范數 D = cumsum(D); % 累積求和，便于查找下一個種子點 if D(end) == 0, centroids(:, i:k) = X(:, ones(1, k-i+1)); return; end nextCentroid = find(rand < D / D(end), 1); % 查找下一聚類中心點的坐標，Random -= D(x)，直到其<=0 centroids(:, i) = X(:, nextCentroid); % 添加新的聚類中心% a = 2*real(centroids' * X);% b = dot(centroids, centroids, 1).'; [~, labels] = max(bsxfun(@minus, 2*real(centroids' * X), dot(centroids, centroids, 1).'));%舉例當前中心點為 end%% 標準Kmeans算法 for iter = 1:max_iter for i = 1:k, l = labels==i; centroids(:,i) = sum(X(:, l), 2) / sum(l); end [~, labels] = max(bsxfun(@minus, 2*real(centroids' * X), dot(centroids,centroids,1).'), [], 1); endend

(3)源代碼調用示例

該段調用代碼是將一副RGB圖像轉化在HSV顏色模型空間下進行聚類，輸出為染色聚類結果

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%功能：利用kmeans算法對rgb圖像進行聚類，并顯示聚類染色結果%kmeans算法中當聚類的中心距離過小，或者某一類數量過低，可以將這些類合并到旁邊類%調用run_kmeans算法%輸入參數：% X：輸入樣本數據集% k: 聚類中心個數% max_iter:kmeans最大迭代次數%輸出參數：% centroids:類中心的坐標維數與樣本集一致% labels: （1：k）被標記好的分類輸出%rgb2ycbcrclear all;close all;clc;%%讀圖% image=double(imread('lena.bmp'));% % figure(1);% % imshow(uint8(image)),title('Input image');% %%存儲圖像尺寸% image_rows=size(image,1);% image_cols=size(image,2);%%% %把圖片存成樣本X% X=(reshape(image,[image_rows*image_cols,3])');% % scatter(X(1,:),'r','filled');% % figure();% %scatter3(X(1,:)', X(2,:)', X(3,:)', c,'filled'),view(0,255); %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%rgb2hsv%讀一張rgb圖像，在hsv模型里面處理圖像%功能：rgb圖像轉換成HSV模型圖像，弄明白HSV圖像在matlab中的存儲方式，并reshape成圖像進行輸入clear all;close all;clc;% H=double(I);%H為RGB圖像% [hue,s,v]=rgb2hsv(H);image=double(imread('lena.bmp'));image_rows=size(image,1);image_cols=size(image,2);[hue,s,v]=rgb2hsv(image);figure;imshow(hue),title('hue');figure;imshow(s),title('s');figure;imshow(uint8(v)),title('v');% image_hsv=rgb2hsv(image);hue=reshape(hue,1,image_rows*image_cols);s=reshape(s,1,image_rows*image_cols);v=reshape(v,1,image_rows*image_cols);X=[hue;s;v];%%%對樣本空間進行聚類k=3;%聚類個數max_iter=100;%最大迭代次數[centroids, labels] = run_kmeans(X, k, max_iter); %kmeans把圖像聚成3類% labeled_X=[X;labels];%%顯示染色結果% if labeled_X(4,:)==1% out_image=image(:,:,1)% elseif labeled_X(4,:)==2% out_image=image(:,:,2)% elseif labeled_X(4,:)==3% out_image=image(:,:,3)% end;pixels_labeled=reshape(labels,image_rows,image_cols);image_r=zeros(image_rows,image_cols);image_r(pixels_labeled==1)=255;% reshape(image_r,image_rows,image_cols);image_g=zeros(image_rows,image_cols);image_g(pixels_labeled==2)=255;% reshape(image_g,image_rows,image_cols);image_b=zeros(image_rows,image_cols);image_b(pixels_labeled==3)=255;% reshape(image_b,image_rows,image_cols);out_image=zeros(size(image));out_image(:,:,1)=image_r;out_image(:,:,2)=image_g;out_image(:,:,3)=image_b;figure(2)imshow(uint8(out_image));

上一篇：遞歸

下一篇：STL常用數據結構總結