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