本實驗的目的是學習和掌握k-均值聚類算法。k-均值算法是一種經典的無監督聚類和學習算法，它屬于迭代優化算法的范疇。本實驗在MATLAB平臺上，編程實現了k-均值聚類算法，并使用20組三維數據進行測試，比較分類結果。實驗中初始聚類中心由人為設定，以便于實驗結果的比較與分析。 ##一、技術論述 **1.無監督學習和聚類** 在之前設計分類器的時候，通常需要事先對訓練樣本集的樣本進行標定以確定類別歸屬。這種利用有標記樣本集的方法稱為“有監督”或“有教師”方法。這一類方法的使用固然十分廣泛，也有著很堅實的理論基礎，但在實際運用中這類方法經常會遇到以下瓶頸： 1. 收集并標記大量樣本集是一件相當費時費力的前期工作； 2. 現實中存在很多應用，其分類模式的性質會隨著時間發生變化，單單使用已標記樣本無法滿足這類情況； 3. 有人希望能逆向解決問題：先用大量未標記的樣本集來自動地訓練分類器，再人工地標記數據分組的結果，如數據挖掘的大型應用，因為這些應用往往不知道待處理數據的具體情況。 可以看到，無監督學習方法的提出是十分必要的。事實上，在任何一項探索性的工作中，無監督的方法均向我們揭示了觀測數據的一些普遍規律。很多無監督方法都可以以獨立于數據的方式工作，為后續步驟提供“靈巧的預處理”和“靈巧的特征提取”等有效的前期處理。在無監督的情況下，聚類算法是模式識別研究中著名的一類技術。 **2.分類與聚類的差別** 分類(Classification)：對于一個分類器，通常需要你告訴它“這個東西被分為某某類”這樣一些例子。通常情況下，一個分類器會從它得到的訓練數據中進行學習，從而具備對未知數據進行分類的能力，這種提供訓練數據的過程通常叫做有監督學習。 聚類(Clustering)：簡單地說就是把相似的東西分到一組。聚類的時候，我們并不關心某一類是什么，這里需要實現的目標只是把相似的東西聚到一起。因此，一個聚類算法通常只需要知道如何計算相似度就可以開始工作了。因此，聚類方法通常并不需要使用訓練數據進行學習，因此桔類方法屬于無監督學習的范疇。 **3.常見的分類與聚類算法** 所謂分類，就是根據數據樣本的特征或屬性，劃分到已有的類別中。前面使用到的模式分類方法主要有：貝葉斯分類算法(Bayesian classifier) 、PCA主分量分析法、Fisher線性判別分析法、Parzen窗估計法、k-最近鄰法(k-nearest neighbor，kNN)、基于支持向量機(SVM)的分類器、人工神經網絡(ANN)和決策樹分類法等等。 分類作為一種有監督學習方法，要求必須在分類之前明確知道各個類別的必要特征和信息，并且標記所有訓練樣本都有一個類別與之相對應。但是很多情況下這些條件往往無法滿足，尤其是在處理海量數據的時候，數據預處理的代價非常大。 聚類算法中最經典的當屬k均值聚類(K-means clustering)算法。該算法又稱為“c均值算法”，因為它的目標就是找到c個均值向量作為聚類中心：μ1,μ2,…,μc，實際上k與c是等價的。   以上是對二維隨機樣本進行聚類的實例。 **4.聚類任務的基本步驟** 假設所有模式都用一組特征表示，模式被表示為L維的特征矢量。聚類任務需包含以下步驟： 1. **特征選擇**。選擇特征盡可能與感興趣的任務相關。特征之間的信息冗余度要盡可能小。 2. **相似性測度**。一個基本的保證是所有選擇的特征對相似性測度計算的貢獻都是均衡的，沒有那一個特征是絕對占優的。 3. **聚類準則**。聚類準則依賴于專家判斷的在數據集合內部隱含類的類型解釋。聚類準則可以被表示為代價函數和其它類型的規則。 4. **聚類算法**。在確定相似性測度和聚類準則后，這一步就是要選擇一個具體的算法方案將數據集合分解為類結構。 5. **結構的有效性**。一旦聚類算法獲得了結果，需要采用合適的檢驗方法檢驗其正確性。 6. **結果的解釋**。應用領域的專家必須結合其它的試驗證據和分析解釋聚類結果，以便得到正確的結論。 **5.k-均值聚類算法** k-均值聚類算法的目標是找到k個均值向量或“聚類中心”。算法的實現步驟如下所示，其中n表示模式的數量，c表示類別的數量，通常的做法是從樣本中隨機取出c個作為初始的聚類中心。當然，初始的聚類中心也可以通過人為來確定：  該算法的計算復雜度為：  其中d代表樣本的維數，T是聚類的迭代次數，一般來說，迭代次數通常遠少于樣本的數量。 該算法是一種典型的聚類算法，把它歸入迭代優化算法的范疇是因為算法規定的c個均值會不斷地移動，使得一個平方誤差準則函數最小化。在算法的每一步迭代中，每個樣本點均被認為是完全屬于某一類別。 ##二、實驗結果討論 實驗所使用的樣本：  設計步驟主要包括以下幾個部分： 編寫程序，實現以上所述的k-均值聚類算法。其中，在算法中樣本與聚類中心的距離采用歐氏距離的形式。 類別數目和聚類中心初始值選為以下參數進行實驗：  再將類別數目和聚類中心初始值改變為以下參數進行實驗。  下圖得到兩次聚類的結果，可以看到當分類類別為2時，初始聚類中心對分類結果影響不大（至少對于樣本少的情況是這樣的），最終兩種情況都能得到一樣的最終聚類中心。   下面測試將樣本分為三類的情況。將類別數目和聚類中心初始值選為以下參數進行實驗：  再將類別數目和聚類中心初始值改變為以下參數進行實驗：  下圖得到兩次聚類的結果，可以看到當分類類別為3時，分類復雜度增加，隨著聚類中心的移動，對于同一組測試樣本可能有不同的劃分結果。雖然初始聚類中心的作用只是將樣本初步地分為幾個區域，但事實上不同的初始中心會給分類結果帶來巨大的差異。   在程序中，使用歐氏距離作為樣本到聚類中心的距離，事實上也可以使用其他多種距離度量進行運算，如街區距離（1范數）、棋盤距離（∞范數）等等。 ##三、完整代碼 ~~~ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % k-均值聚類函數 % 輸入參數： % w：需要分類的樣本 % k：分類數 % m：初始聚類中心 % iteration：迭代次數 % 中間參數： % class_id：存放各個樣本屬于一類的下標 % dist：計算樣本到聚類中心的距離 % 輸出參數： % class_result：存放樣本的分類結果 % class_num：存放被分到各類的樣本個數 % center：迭代結束時的聚類中心 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function [class_result, class_num, center] = kmeans(w, k, m, iteration) [n,d] = size(w); class_result = zeros(1,n); class_num = zeros(1,k); time = 1; % 以下步驟計算每個樣本到聚類中心的距離 while time < iteration % 迭代次數限制 for i = 1:n dist = sqrt(sum((repmat(w(i,:), k, 1) - m).^2, 2)); % 歐氏距離 % dist = sum(abs(repmat(x(i,:), k, 1) - nc), 2); % 街區距離 [y,class_id] = min(dist); % 計算樣本對三類中哪一類有最小距離并存放在class_id class_result(i) = class_id; end for i = 1:k % 找到每一類的所有數據，計算平均值，其值作為新的聚類中心 class_id = find(class_result == i); m(i, :) = mean(w(class_id, :)); % 更新聚類中心 % 統計每一類樣本的個數 class_num(i) = length(class_id); end time = time + 1; end center = m; ~~~ ~~~ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % 樣本分類結果的繪圖函數 % 輸入參數： % w：需要分類的樣本 % class：聚類后的樣本分類結果 % flag：分類類別數 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%function draw(w, class, center) [flag x] = size(center); [n, d] = size(w); % figure; if flag == 2 % 若將樣本分成兩類 for i=1:n if class(i) == 1 plot3(w(i,1),w(i,2),w(i,3),'r+'); % 顯示第一類 hold on; grid on; elseif class(i) == 2 plot3(w(i,1),w(i,2),w(i,3),'go'); %顯示第二類 hold on; grid on; end end for j = 1:flag if j == 1 plot3(center(j,1),center(j,2),center(j,3),'rd'); % 聚類中心 elseif j == 2 plot3(center(j,1),center(j,2),center(j,3),'gd'); % 聚類中心 end end end if flag == 3 % 若將樣本分成三類 % 顯示分類結果 for i = 1:n if class(i) == 1 plot3(w(i,1),w(i,2),w(i,3),'r+'); % 顯示第一類 hold on; grid on; elseif class(i) == 2 plot3(w(i,1),w(i,2),w(i,3),'go'); % 顯示第二類 hold on; grid on; elseif class(i) == 3 plot3(w(i,1),w(i,2),w(i,3),'b*'); % 顯示第三類 hold on; grid on; end end for j = 1:flag if j == 1 plot3(center(j,1),center(j,2),center(j,3),'rd'); % 聚類中心 elseif j == 2 plot3(center(j,1),center(j,2),center(j,3),'gd'); % 聚類中心 elseif j == 3 plot3(center(j,1),center(j,2),center(j,3),'bd'); % 聚類中心 end end end ~~~ ~~~ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % k-均值聚類的研究與實現主函數 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% clear all; close all; % 測試樣本 w = [-7.82 -4.58 -3.97;... -6.68 3.16 2.71;... 4.36 -2.19 2.09;... 6.72 0.88 2.80;... -8.64 3.06 3.50;... -6.87 0.57 -5.45;... 4.47 -2.62 5.76;... 6.73 -2.01 4.18;... -7.71 2.34 -6.33;... -6.91 -0.49 -5.68;... 6.18 2.18 5.28;... 6.72 -0.93 -4.04;... -6.25 -0.26 0.56;... -6.94 -1.22 1.33;... 8.09 0.20 2.25;... 6.81 0.17 -4.15;... -5.19 4.24 4.04;... -6.38 -1.74 1.43;... 4.08 1.30 5.33;... 6.27 0.93 -2.78]; [n, d] = size(w); % 以下是k均值聚類的參數設定（c = 2時） k = 2; m = [1 1 1; -1 1 -1]; % 初始聚類中心 % m = [0 0 0; 1 1 -1]; % 初始聚類中心 iteration = 200; % k均值聚類的迭代次數 % 調用kmeans函數進行聚類 [class, class_num, center] = kmeans(w, k, m, iteration); % 畫出樣本分類結果 figure;subplot(121);draw(w, class, center); title('使用第一種初始聚類中心時，k-均值聚類算法分類結果'); % 顯示信息 disp(['屬于第一類的樣本個數為：',num2str(class_num(1))]); disp(['屬于第二類的樣本個數為：',num2str(class_num(2))]); disp('最終的聚類中心為：'); disp(num2str(center)); % 以下是k均值聚類的參數設定（c = 2時） k = 2; % m = [1 1 1; -1 1 -1]; % 初始聚類中心 m = [0 0 0; 1 1 -1]; % 初始聚類中心 iteration = 200; % k均值聚類的迭代次數 % 調用kmeans函數進行聚類 [class, class_num, center] = kmeans(w, k, m, iteration); % 畫出樣本分類結果 subplot(122);draw(w, class, center); title('使用第二種初始聚類中心時，k-均值聚類算法分類結果'); % 顯示信息 disp(['屬于第一類的樣本個數為：',num2str(class_num(1))]); disp(['屬于第二類的樣本個數為：',num2str(class_num(2))]); disp('最終的聚類中心為：'); disp(num2str(center)); % 以下是k均值聚類的參數設定（c = 3時） k = 3; m = [0 0 0; 1 1 1; -1 0 2]; % 初始聚類中心 % m = [-0.1 0.0 0.1; 0 -0.1 0.1; -0.1 -0.1 0.1]; % 初始聚類中心 iteration = 200; % k均值聚類的迭代次數 % 調用kmeans函數進行聚類 [class, class_num, center] = kmeans(w, k, m, iteration); % 畫出樣本分類結果 figure;subplot(121);draw(w, class, center); title('使用第一種初始聚類中心時，k-均值聚類算法分類結果'); % 顯示信息 disp(['屬于第一類的樣本個數為：',num2str(class_num(1))]); disp(['屬于第二類的樣本個數為：',num2str(class_num(2))]); disp(['屬于第三類的樣本個數為：',num2str(class_num(3))]); disp('最終的聚類中心為：'); disp(num2str(center)); % 以下是k均值聚類的參數設定（c = 3時） k = 3; % m = [0 0 0; 1 1 1; -1 0 2]; % 初始聚類中心 m = [-0.1 0.0 0.1; 0 -0.1 0.1; -0.1 -0.1 0.1]; % 初始聚類中心 iteration = 200; % k均值聚類的迭代次數 % 調用kmeans函數進行聚類 [class, class_num, center] = kmeans(w, k, m, iteration); % 畫出樣本分類結果 subplot(122);draw(w, class, center); title('使用第二種初始聚類中心時，k-均值聚類算法分類結果'); % 顯示信息 disp(['屬于第一類的樣本個數為：',num2str(class_num(1))]); disp(['屬于第二類的樣本個數為：',num2str(class_num(2))]); disp(['屬于第三類的樣本個數為：',num2str(class_num(3))]); disp('最終的聚類中心為：'); disp(num2str(center)); ~~~