|
1 聚類 無監(jiān)督學(xué)習(xí)是沒有標記信息的學(xué)習(xí)方式，能夠挖掘數(shù)據(jù)之間的 內(nèi)在規(guī)律 ，聚類算法的目的就是找到這些數(shù)據(jù)之間的內(nèi)在性質(zhì)和規(guī)律。 它將數(shù)據(jù)劃分為幾個互不相交且并集為原集的子集，每個子集可能對應(yīng)于一個 潛在概念 ，例如：購買力強的顧客、待配送的商家群體。 2 基本假設(shè) 聚類算法的核心是 通過距離計算來表征兩個樣本之間相似程度 。一般而言，距離的度量有幾個原則： 1) 非負性：如果，表明距離是非負的，這是符合實際的。 2) 同一性：如果，只有一種可能，表示兩個點是重合的。 3) 對稱性：如果，則說明距離具有對稱性，但是在實際問題中，可能距離不具備這個性質(zhì)，比如轎車導(dǎo)航路線從舊宮到北大的距離，與北大到舊宮的距離可能不等。 4) 直遞性：這個也是距離非常重要的一個性質(zhì)，是說距離滿足，三角形兩邊之和大于第三邊。形象地說，本計劃從家想直接到學(xué)校，但是中間想去超市買瓶水然后再到學(xué)校，除非三點在一條線上，否則一定要多走路程。 以上關(guān)于距離的性質(zhì)就是接下來要討論的聚類算法的一些基本假設(shè)。下面介紹幾種常用的聚類算法，之前已經(jīng)推送過關(guān)于聚類算法的幾篇文章，今天再提煉總結(jié)，順便排版做得更好些，更方便大家學(xué)習(xí)。 3 聚類算法3.1 K-Means 這個算法可能是大家最熟悉的聚類算法，簡單來說， 選取初始中心點 ， 就近吸附到中心點 ， 迭代這一過程直到各個中心點移動很小為止 。接下來，我們詳細討論k-means算法在實際應(yīng)用中的一些注意事項。 注意事項 k-means需要輸入劃分簇的個數(shù)，這是比較頭疼的問題，為了應(yīng)用它得先用別的算法或者不斷試算得出大致數(shù)據(jù)可分為幾類。這可能只是帶來一些麻煩，還不能說是缺陷。不過，k-means算法的確存在如下 缺陷： 首先，它對初始中心點的選取比較敏感，如果中心點選取不恰當，例如隨機選取的中心點都較為靠近，那么最后導(dǎo)致的聚類結(jié)果可能不理想。為了避免，通常都要嘗試多次，每次選取的中心點不同一次來保證聚類質(zhì)量, sklearn中實現(xiàn)了這種初始化框架k-means++. 關(guān)于這個機制可參考論文： k-means++: The advantages of careful seeding 其次，K-means是通過吸附到中心點的方法聚類，它的基本假定: 簇是凸集且是各向同性的，但是實際中并不總是這樣，如果簇是加長型的，具有非規(guī)則的多支路形狀，此時k-means聚類效果可能一般。 最后，在高維空間下歐拉距離會變得膨脹，這就是所謂的 “維數(shù)詛咒” 。為了緩解此問題，通常k-means聚類前要使用PCA等降維算法，將多特征集中表達在低特征空間中，同時加快聚類收斂。 3.2 Mini Batch K-Means K-means算法每次迭代使用所有樣本，這在數(shù)據(jù)量變大時，求解時間就會變長。為了降低時間復(fù)雜度， 隨機選取b個樣本形成一個mini-batch ，這種算法就是 mini-batch k-means.它也是隨機選取初始點，然后就近吸附到中心點，更新中心點直到移動很小為止。 雖然每次迭代只是抽樣部分樣本，但是聚類質(zhì)量與k-means相比差不太多。 3.3 Mean Shift mean shift 的聚類過程大致描述如下：在多維空間中，任選一個點，然后以這個點為圓心，h為半徑做一個高維球，圓心與落在這個球內(nèi)的每個點形成向量，然后把這些向量相加求和，結(jié)果就是Meanshift向量。  再以meanshift向量的終點為圓心再生成一個球。重復(fù)以上步驟，就再可得到一個meanshift向量。  不斷迭代，meanshift算法可以收斂到概率密度最大的區(qū)域，也就是最稠密的部分。  mean shift 算法需要知道 bandwidth ，也就是寬度(或理解為直徑)。在sklearn中實現(xiàn)也實現(xiàn)了這個算法，它需要輸入bandwidth，如果不輸入此值，算法默認計算一個bandwidth. 3.4 層次聚類 層次聚類算法的基本思想：將m個樣本看做 m個已經(jīng)劃分好的子集 ，找出距離最近的兩個聚類子集并將它們合并，不斷重復(fù)這個過程，直到剩余k個子集。 它是分治法思想的代表。 聚類的層次結(jié)構(gòu)可以用一顆樹來表達，根節(jié)點是一個包括所有樣本的簇，葉子節(jié)點僅含有一個樣本。 層次聚類常用的merge策略包括： 1) Ward 最小化簇間的均方誤差，這點和k-means思想不謀而合。  2) Maximum or complete linkage 最小化兩個簇間距的最大值，這個目標和支持向量機的目標函數(shù)有點相似。  Average linkage 最小化所有簇對間的間距。  3.5 DBSCAN DBSCAN算法將高密度區(qū)域視為由與低密度區(qū)域所分離，因此dbscan可以發(fā)現(xiàn)任何形狀的簇，優(yōu)于k-means只能發(fā)現(xiàn)凸形狀的簇。dbscan算法認為，如果某個樣本滿足：在一定距離（ eps ）內(nèi)的能發(fā)現(xiàn)一定個數(shù)( min_samples )的樣本，稱它為核心對象(core sample)，非核心對象是eps范圍內(nèi)找不到滿足一定數(shù)量的樣本。 那么，構(gòu)成一個簇的對象(或樣本)一定是核心對象嗎？如果是這樣，這個簇將會無限遞歸下去而無法終止，由此可以直觀上感知，一個簇的邊緣一定是非核心對象，但是至少距離一個核心對象小于eps.如下圖箭頭所指對象，很小的圓圈代表非核心對象，但是它們至少離一個大圓(核心對象)距離小于eps.  還有一類點，如上圖中的黑點表示的非核心對象，它們不屬于任何一個簇，言外之意，它們離任何一個簇距離至少eps，這類樣本就是 奇異點(outliers) dbscan算法在實際使用中會發(fā)現(xiàn)它與讀入 樣本的順序相關(guān) ，順序會影響到非核心對象所吸附到的簇。如果一個非核心對象離不同簇的兩個核心對象距離都小于eps，此時非核心對象被吸附到的簇是首先被掃描到的核心對象所屬的簇。 還有一處值得留意，為了計算某個樣本的近鄰域，如果構(gòu)造距離矩陣，內(nèi)存消耗n^2，為了避免內(nèi)存消耗，可以構(gòu)建kd-trees或ball-tress，但是對于稀疏矩陣就不能應(yīng)用這些算法，但是有一些其他措施可以解決。 綜上，dbscan需要輸入eps和min_samples作為算法的兩個入?yún)ⅰ?/p> 3.6 高斯混合 一般地，假設(shè)高斯混合模型由K個高斯分布組成，每個高斯分布稱為一個component，這些 component 線性組合在一起就構(gòu)成了高斯混合模型的概率密度函數(shù)： 上式就是GMM的概率密度函數(shù)，可以看到它是K個高斯模型的線性疊加，其中每個高斯分布對GMM整體的概率密度所做的貢獻為系數(shù)。 GMM首先要確定數(shù)據(jù)樣本 x 來自于component k的概率，可以理解為樣本 x 對component k做的貢獻，并且component k 又對整體的GMM做貢獻，這樣間接地樣本 x 對整體的GMM做了一些貢獻，這樣帶出了；然后再用最大似然估計確定所有的樣本點對component k 的影響進而獲得分布參數(shù)：均值和方差，一共確定這3個參數(shù)。 關(guān)于高斯混合模型的不調(diào)包詳細模型代碼實現(xiàn)參考之前推送： 4 聚類評估 聚類算法的結(jié)果好壞可以用adjusted rand index，數(shù)學(xué)模型等，更詳細的參考： http:///stable/modules/clustering.html#clustering-performance-evaluation 這部分可以單獨抽出一篇文章來寫，后續(xù)推送。 文章用心血凝聚，不走捷徑，如不反感可否支持下， 這樣我會更加堅定初心，更有勇氣在這條'與別人不一樣'的艱辛原創(chuàng)之路上一直走下去 … |
|
|
