文章目錄
- 聚類簡介
- 聚類和分類的差別
- 基礎概念
- 外部名額
- 内部名額
- 距離度量和非距離度量
- 距離度量方法
- 有序屬性和無序屬性
- 原型聚類
- k均值算法(K-means)
- 學習向量化（LVQ）
- 高斯混合聚類（GMM）
- 密度聚類(DBSCAN)
- 層次聚類(AGNES)
- 學習參考
聚類簡介
之前學習的決策樹、随機森林或者邏輯回歸都屬于有監督學習，就是有老師在指導他，給了他特征和真實标簽lable。
今天的這個聚類算法就是無監督學習，不需要真實标簽lable。
聚類結果:将資料劃分成有意義的‘簇’ （類似于集合），簇内樣本盡快可能的相同，簇間盡可能的不同。
聚類和分類的差別
可以看下面這張圖，紅色哪裡有一個 X 分類是将X分類到三種三色中的一種，而聚類一開始都是灰色，聚類将他們分類，這也看出來了聚類是無監督學習，原始資料沒有lable。
基礎概念
概念：簇與質心
簇：KMeans将一組N個樣本的特征矩陣X劃分為K個無交集的簇，在一個簇中的資料就認為是同一類。
質心：簇中所有資料的均值被稱為這個簇的質心(centroids)。
外部名額 ： 外界給個标準進行比較.（有監督）
内部名額 ： 沒有标準，和自己比.（無監督）
外部名額
用一個例子來看一下各種名額的原理，假設有abcd四個變量，且字母S代表相同，字母D代表不同。
左邊是自己分類的，右邊是參考(lable)，相當于lable。顯然隻有 X1和X2是自己分類也在C1，參考(lable)也在C1.
是以 SS 就是 X1 ,X2。
以此類推可以得到其他: x1,x3 一開始同在C1簇 就是S，但參考一個C1一個C2 就是D，是以結果SD。
x1,x2,x3,x4,x5 兩兩排列組合 一共10種情況。
然後可以計算各種名額，這裡帶入的值就是 b裡有三個集合 是以b就是3。
m是樣本數量，本例中 m=5。
這幾個值在 0-1區間，越大越好。
内部名額
同樣用一個例子來說明。
avg 簇内樣本平均距離。
diam 簇内樣本最大距離。
dmin 簇内樣本最小距離。
dcen 簇中心距離。
DB指數: 越小越好：
Dunn指數：越大越好
簇間樣本最小距離 / 簇内樣本最大距離
距離度量和非距離度量
在不斷優化聚類的過程中需要有一個距離的計算來判斷樣本與質心之間的距離。
距離度量滿足的性質 ：
非負性 距離大于零
同一性 重疊等于零
對稱性，互換相等
直遞性 有三個點，類似于兩邊之和大于第三邊。 當k點在i和j點連線上時 等号成立
距離度量方法
樣本到質心的距離度量方法 ，x表示其中一個樣本點，u表示該簇質心，n表示每個樣本點中的特征數目，i表示組成點的每個特征。
曼哈頓距離 與 歐幾裡得距離 同屬于闵氏距離的特例（p=1為曼哈頓距離；p=2為歐氏距離）
采用歐幾裡得距離，則一個簇中所有樣本到質點的距離平方和
其中 ，m為一個簇中的樣本個數，j為樣本編号。
該公式被稱為 簇内平方和(Inertia).
将資料集中所有簇的簇内平方和相加，就得到了整體平方和，(total inertia) 該值越小，表示簇内樣本越相似，聚類效果越好。
雖然像KNN 決策樹等這類算法中沒有損失函數，但Inertia的功能卻類似于損失函數。
Sklearn中隻能使用歐氏距離。
非距離度量的例子：
不符合 直遞性 兩邊之和不大于第三邊。
有序屬性和無序屬性
有序屬性：
歐氏距離與曼哈頓距離：
下圖中 中間的綠線就是歐氏距離， 黃色 紅色 藍色 就是曼哈頓距離 這三個距離相等。
切比雪夫距離
國際象棋，中間的那個棋子，每一圈是1個距離。 可能是橫縱坐标取移動的最大值。
無序屬性無序屬性計算距離 VDM距離。
混合距離: 有序和無序相加 闵可夫斯基距離 和 VDM距離相加。
權重距離: 按照屬性重要性不同權重
原型聚類
先對原型初始化，然後疊代更新。
k均值算法(K-means)
- 一開始一堆的樣本點。
- 初始化分為不同的簇，然後不斷的疊代最後收斂。
更形象的:
1.藍點就是樣本點，紅點就是随機生成的簇的中心點。
2.分别計算每個樣本點到簇的中心點的距離，将他們分成不同的簇(那個點距離近就屬于那個簇)。
3. 之後暫且忽略紅點，然後重新計算每個簇區域的中心點。新計算的中心點就是綠點。
綠色作為新的簇的中心點，繼續重新計算每個樣本距離中心點的位置，繼續重新劃分簇的區域。不斷疊代直到收斂。
學習向量化（LVQ）
每個樣例有類别标簽，是有監督學習
結果輸出不會給簇的劃分，而是給每個類别的原型向量(即中心點)
步驟:
假設一開始都是黑點，然後也是随機選了幾個點作為簇中心點(紅點)。
開始分析每一個點輸入那個簇。顯然此時x1點輸入p5簇。
因為這個是有監督的學習，假設 X1和p5是同類别，則p5就靠近一點x1。
同樣 如果現在看x24 ，其屬于p4的簇，如果 他倆是不同的類别。則p4就遠離x24.
最後輸出的是這五個中心點，其中紅線就是兩點之間的垂直平分線。
高斯混合聚類（GMM）
這裡的k就是幾個高斯分布，或者說像分成幾個簇。
密度聚類(DBSCAN)
通過樣本分布的緊密程度确定簇，不斷疊代。
由密度可達關系導出最大密度相連的樣本集合（聚類）。這樣的一個集合中有一個或多個核心對象，如果隻有一個核心對象，則簇中其他非核心對象都在這個核心對象的ε鄰域内；如果是多個核心對象，那麼任意一個核心對象的ε鄰域内一定包含另一個核心對象（否則無法密度可達）。這些核心對象以及包含在它ε鄰域内的所有樣本構成一個類。
對比:
DBSCAN使用一組關于“鄰域”概念的參數來描述樣本分布的緊密程度，将具有足夠密度的區域劃分成簇，且能在有噪聲的條件下發現任意形狀的簇。
一些概念:
鄰域：對于任意給定樣本x和距離ε，x的ε鄰域是指到x距離不超過ε的樣本的集合；
核心對象：若樣本x的ε鄰域内至少包含minPts個樣本，則x是一個核心對象；
密度直達：若樣本b在a的ε鄰域内，且a是核心對象，則稱樣本b由樣本x密度直達；
密度可達：對于樣本a，b，如果存在樣例p1,p2,…,pn,其中，p1=a,pn=b,且序列中每一個樣本都與它的前一個樣本密度直達，則稱樣本a與b密度可達；
密度相連：對于樣本a和b，若存在樣本k使得a與k密度可達，且k與b密度可達，則a與b密度相連。
層次聚類(AGNES)
在不同層次對資料集進行劃分，進而形成樹狀的聚類結構。
凝聚的層次聚類：一種自底向上的政策，首先将每個對象作為一個簇，然後合并這些原子簇為越來越大的簇，直到某個終結條件被滿足。
分裂的層次聚類：采用自頂向下的政策，它首先将所有對象置于一個簇中，然後逐漸細分為越來越小的簇，直到達到了某個終結條件。
自底向上是主要的。
cluster R和cluster S之間的距離計算方法:
1）最小連接配接距離法（Single Linkage）
取兩個簇中距離最近的兩個樣本的距離作為這兩個簇的距離。
（2）最大連接配接距離發（Complete Linkage）
取兩個簇中距離最遠的兩個點的距離作為這兩個簇的距離。
（3）平均連接配接距離法（Average Linkage）
把兩個簇中的點的兩兩的距離全部放在一起求均值，取得的結果也相對合适一點。
學習參考
https://zhuanlan.zhihu.com/p/367956614