第八周筆記：聚類（clustering）

01-29

聚類很好理解。你左手在地上撒一把鹽，右手在地上撒一把糖。假設你分不清鹽和糖，但是你分別是用左右手撒的，所以兩個東西位置不同，你就可以通過倆玩意的位置，判斷出兩個東西是兩類（左手撒的，右手撒的）。然而能不能區別出是糖還是鹽？不行。你只能分出這是兩類而已。但是分成兩類以後再去分析，就比撒地上一堆分析容易多了。

聚類是典型的非監督學習。上面例子中，如果把鹽和糖改成白色鹽和染成黃色的糖，你可以通過顏色分析，顏色就是標籤，有標籤就是監督學習。沒標籤就是非監督學習。

聚類演算法常用K均值演算法：

隨機選擇包含K個中心的cluster( $mu_1,mu_2,mu_3,mu_4,...,mu_k$ , $Kin R$ )

以K=3為例，假設特徵量是啥我也不知道……反正有特徵量，現在畫3個圈圈：

隨機找3個點（圖中①，②，③的藍色點）當然，你找的點不一定就馬上在中心了。有可能3個點都跑一個cluster裡面去，無所謂……

然後開始迭代，每次迭代方法如下：

對於每個特徵點 $x_i$ ，找到和特徵點 $x_i$ 最近的那個 $mu _i$ （例如 $mu _1$ ），把每個和 $mu _1$ 最近的點放到一起。對於每個 $mu _i$ 都這個操作，例如你選了3個點，就是3個 $mu _i$ （ $mu _1$ ， $mu _2$ ， $mu _3$ ）

然後對於每個 $mu _i$ 的最近點 $x_i$ ，取個平均值 $bar{x_i}$ ，當作該 $mu _i$ 的新值。然後你會神奇的發現，每個 $mu _i$ 都朝著一個cluster的中心近了一步！（一點也不神奇好嗎……）

重複n多次，直到收斂為止……

這是別人網站上可視化的具體收斂過程，做得很好這裡推薦一下：Visualizing K-Means Clustering

你就會神奇地發現這3個點把區域按照某種神奇的規則分出來了（這個規則就是K均值最小……）這3個不同的區域就是3個cluster。

具體的算式如下：

$J=frac{1}{m} sum_{m}^{i=1}{(x_i-mu _c^{(i)})}$

由於這次咱不是監督演算法了，所以沒法去壓導數去迭代。上文也說了怎麼迭代，所以這次迭代方法是： $minJ(c^{(1)}......c^{(m)};mu ^{(1)}......mu ^{(k)})$ 不和導數扯上關係了，自己根據每個點算最小值不斷迭代到收斂就是了……

然後就是選每個初始K的點也有技巧，一旦選不好，有可能3個點選到一個簇，本來應該是分成3個圓形片區，結果把整張圖片分成3個長方塊的也不是不可能……

所以要隨機選，為了保險，可以多隨機幾次。

然後就是另一個問題了：

K元素選幾個？

選少了，偏差很大。選多了，過擬合了。

如果願意畫圖，有個方法叫肘子方法（我餓了……）

諾，就是畫這麼一個圖，那個大概是肘子的地方就是我們要選的K的個數……不過肘子方法缺點很明顯，老畫圖人工去看，一點也不機器。

維數縮減（Rimensionality Reduction ）：

舉個例子。你做房子的數據的爬蟲。假設全是正方形房子，爬蟲中有這3個特徵量：面積，長度，寬度。那麼因為面積和長度寬度相乘相等，就可以縮減了。再例如，你爬到了一個是攝氏度，一個是華氏度，由於數據本身是一樣的，也可以縮減了。把實際內核為同一個特徵的的縮減到同一個，就是維數縮減。估計你也看出來了。K的個數就是維度嘛……所以維數縮減一定程度上可以看作選擇k的個數。

當然……既然數據縮減了，儲存需要的空間也就小了。（對於我們這種屌絲來說，省一張硬碟就是幾百塊錢，四捨五入就是一個億啊……多縮減幾次數據就省出一個王思聰了。）

實際做法，將J維的數據投影到一個I維空間上。

比如這樣：

二向箔攻擊！（容我中二一下……）三維空間里的數據就被壓縮成了二維的了……~

通常要可視化數據的話，由於我們人類很傻，只能看到3維，所以一般要把數據降到3維或者二維……舉個例子……把一個國家雜七雜八的經濟發展指標壓縮成一個GDP，然後分別看人口和GDP關係，工人比率和GDP關係……這種。

主成分分析演算法（PCA）：

上文說了一個可視化數據要壓縮，那怎麼知道壓縮了以後不會產生極大偏差呢？要投影數據，那麼投影到哪個屏幕啊不對平面上呢？

實際做法：找能使投影誤差最小的那個維度（平面）

定義i個向量，將J個特徵量投影到這i個向量組成的子空間上。

如下：

$mu _i = frac{1}{m} sum_{i=1}^{m}{x_j^{(i)}}$ ， $mu _i$ 這玩意就是我們說的向量。

然後把原來的 $x_j^{(i)}$ 變成 $frac{x_j{(i)}-mu _i}{s_j}$ 。 $s_j$ 是數據歸一化用的玩意（例如方差，最大值什麼的。隨便你選個你喜歡的）。

然後問題來了，咱算數據肯定是一列一列算，誰閑著沒事一個一個算。那麼如何一列一列算呢？

定義sigma， $Sigma=frac{1}{m}sum_{a}^{b}{(x^{(i)}*x^{(i)T})}$ 拿矩陣說的話就是 $Sigma=frac{1}{m}*X*X$

然後用一個Octave裡面的演算法svd，神奇的事情就發生了……

[U,S,V]=svd(Sigma)n

然後我們就得到了包含n個（特徵量個數） $mu _i$ 的一個矩陣U了。然後我們要縮減到k個緯度，就從這個矩陣U裡面提取前k個就行了（誤差好大的感覺……不過算了。壓縮數據本來誤差就大）。

用Octave的話就是這麼個玩意,假設我們壓縮到k個緯度。：

U_reduce=U(:,1:k);nZ=U_reduce*Xn

然後就可以用這個U_reduce開開心心地投影出了我們要的z(壓縮過的特徵量)了。

那假如我後悔了。我不該壓縮我親愛的數據的，我一個臭屌絲又沒錢買硬碟所以並沒有數據的備份，那我想要回最初的數據咋辦呢？

那就……那就算一算原數據吧……

由於：Z=U_reduce*Xn

1所以我們可以反推X：

X=U_reduce*Zn

這個X當然是有誤差的。所以就別寫作X了，寫作X_approx好了……

X_approx=U_reduce*Zn

然後就是自動選K的問題。自動選K這事很有趣，如果X被壓縮以後，解壓縮回來誤差很小，那大概可以認為此時選取的k是比較合適的。方法如下：

計算誤差 $error=frac{sum_{i=1}^{m}{(x_i-x_{i,approx})}^2 }{sum_{i=1}^{m}{x_i} ^2}$

如果error<0.01的話，那這時候的k大概就在肘子那裡了……當然，你也可以寫個循環，找出error最小時的k。

順便說一句，PCA也可以用於監督學習中，以便我們這些窮B減少自己心愛的計算機的負荷（好心酸。我要買個顯卡塢來增加運算能力，誰也別攔著我！）具體的做法就是把 $(x_i,y_i)$ PCA成 $(z_i,y_i)$ ，然後代入假定函數中。當然，既然特徵量已經從x變成z了。記得在用交叉函數J_cv和測試函數J_test的時候，也要把x變成z。因為特徵量的數據並不同所以需要再變一次，這地方容易出錯……

由於PCA整個方案都沒用到y，所以過擬合問題並不能用PCA來降維攻擊，還是老老實實的用正則化吧……正則化簡單粗暴還不