一、概述
K-means聚類算法和主成分分析的應用。
終于從監督學習轉向非監督學習了。可惜隻講了聚類分析，然後就去講PCA了。
本次作業有Find Closet Centroids，Compute Centroid Means，PCA，Project Data，Recover Data五個函數。
二、分析
1、K-means聚類分析
K-means聚類分析的具體步驟如下：
①、選擇k個初始點；
②、訓練集X中有m個樣本，對每個樣本，分别計算其與k個初始點的距離，選擇距離最小的初始點，該樣本标記為屬于該初始點；
③、對每個初始點所包括的樣本，計算其平均值，作為新的初始點，将k個初始點都更新一遍；
④、重複②、③，直到更新後的初始點與更新前沒有變化，即收斂。這時，樣本分類完成。
原理還是很容易了解的。
其中，Find Closet Centroids函數用于實作②。代碼如下：
for i=1:length(idx)
nowNode=X(i,:);
nowDis=100000000;
nowNum=0;
for j=1:K
nowCen=centroids(j,:);
tempDis=sum((nowCen-nowNode).^2);
if tempDis<nowDis
nowDis=tempDis;
nowNum=j;
end
end
idx(i,:)=nowNum;
end
兩個循環即可。很簡單。
Compute Centroid Means用于實作③中的計算平均值，代碼如下：
for i=1:K
centroids(i,:)=mean(X(find(idx==i),:));
end
然後疊代即可。疊代使用runkMeans函數，這個函數作業自帶，才是核心函數，不用寫這個真是遺憾。
另外，選擇初始點也是一個技術活，初始點選擇不同，對最後的聚類結果差距會很大。是以，一般選擇多次随機選取初始點的方法來進行聚類。
2、主成分分析（PCA）
主成分分析一般用于降維和資料可視化。降維，直覺來說就是降低資料的次元，三維拍扁了變成二維，二維搓一搓變成一維。這樣計算起來就友善一些，少用一些時間。另外，對于四維及以上的資料，不可能以視覺形式呈現出來，如果想将其可視化，那就需要将高維降到三維或者二維。
然而，降維并不是随意降，它需要滿足兩個特性：最大可分性，最近重構性。前者指的是，對于高維空間中距離較遠的樣本，降維後它們的距離也應較遠；反之，對于高維空間中較近的樣本，降維後它們的距離應較近。也就是說，應保留樣本間的差別。
對于後者，我們首先将降維這一操作換一種方式解釋：降維即是選擇一個超平面，對所有高維空間的樣本進行表達。那麼，這個超平面應該距離所有樣本盡可能近，離得太遠會導緻所有樣本均有了一個偏置，這将影響其性質。
對于降維後效果的評價，選擇利用如下公式進行量化：
以二維降一維為例，xi表示二維平面上第i個樣本原來的坐标，xapproxi表示投影到直線上後第i個樣本的坐标，它們的距離的平方就可以用來表示資訊的損失。注意，所有的xapprox都處于一條直線上，是以可以認為是降維了。
一般令上述公式的結果小于0.01，0.05，0.1等。
接下來對PCA的步驟進行說明。
①、資料預處理，即對所有資料減去其平均值。令資料的平均值均為0。例如，樣本的某一特性的值為2 3 4 5，預處理之後的值為-1.5 -0.5 0.5 1.5；
②、計算協方差矩陣；
③、利用奇異值分解svd，對協方差矩陣M分解得到矩陣U、S、V。SVD可以了解為：将一個比較複雜的矩陣用更小更簡單的3個子矩陣的相乘來表示，這3個小矩陣描述了大矩陣重要的特性。其中，矩陣U和矩陣V為兩個正交基矩陣，矩陣S為奇異值矩陣。它們的含義是：矩陣M乘一個向量，就是将M從以V為基的空間映射到了以U為基的空間，并在S的方向上進行了大小變化。該段引自這裡；
④、利用③中得到的U矩陣，選取前k列，得到一個新的矩陣Ureduce，這個矩陣的轉置乘以原矩陣，就将原矩陣降維到了k維；
⑤、對于k的選取，要遵循讓上述公式的值最小化的原則，但是用上面那個公式太麻煩了，經過化簡，可以得到下文中的公式：
，該公式指的是資訊的保留度，也就是說，該公式與上文公式之和應為1。而該公式中的Sii就是指的svd中得到的矩陣S的對角線上的元素值。由此可以簡單的得出資訊保留度。
PCA與svd的關系很複雜，本文在此不做說明。
在代碼方面，函數pca一手包辦了第②步和第③步。代碼如下：
sigma=X'*X/m;
[U,S,V]=svd(sigma);
簡單的要死，matlab給出了svd的計算函數，真是謝天謝地。
函數project data負責對X進行降維，其代碼如下：
Ureduce=U(:,1:K);
for i=1:size(X,1)
Z(i,:)=X(i,:)*Ureduce;
end
函數recover data負責對已降維的Z進行重建，得到的就是Xapprox。代碼如下：
for i=1:size(Z,1)
X_rec(i,:)=Z(i,:)*U(:,1:K)';
end
要注意一點，我們在二維降一維的時候，會感覺PCA和線性回歸很像，實際上它們本質并不同。線性回歸要求的代價函數是y1-y的和最小，其中y1是樣本x在直線上的取值，y是樣本的實際取值，(x,y1)與(x,y)的連線和y軸平行；PCA要求的代價函數是樣本到直線的距離和最小，(x,y1)與(x,y)的連線和PCA所得的直線垂直。
同時注意，不要用PCA去減少過拟合現象，這是正則化來做的。
三、總結
本次作業簡單的應用了聚類分析和PCA，對于其原理進行了淺嘗辄止的描述，關鍵的代碼還是現成的，很簡單。