一、概述
（1）聚類分析
目標(biāo)是，分組數(shù)據(jù)使得，組內(nèi)的對象是相似的（相關(guān)的），不同組是不同的（不相關(guān)的）。
（2）聚類類型
1、層次、劃分
層次聚類（嵌套聚類，hierarchial clustering）：聚類簇組織成一棵樹，每一個結(jié)點是其子女的并。
劃分聚類（非嵌套聚類，partional clustering）：簡單的將數(shù)據(jù)對象劃分為不重疊的子集。
2、互斥、重疊、模糊
互斥聚類（exclusive）：每個對象被指派到單獨的單個簇。
重疊聚類（overlapping）：一個對象可以同時屬于多個簇。
模糊聚類（fuzzy clustering）：概率聚類，每個對象以0-1之間的的權(quán)值隸屬于一個類，但是每個對象的權(quán)值之和為1。
3、完全、部分
完全聚類（complete clustering）：每個對象指派到一個類。
部分聚類（partial clustering）：某些對象可以不屬于明確定義的類。
（3）簇類型
下面顯示一些簇類型：
類型：明顯分離、基于原型（中心簇）、基于圖（連通）、基于密度、共同性質(zhì)的（概念簇）。
二、K-均值
（1）基本K-均值算法
算法步驟：
目標(biāo)函數(shù)：
^{2}, c_{i}=\frac{1}{m_{i}}\sum_{x\in C_{i}}x)
上面的第3、4步驟試圖最小化目標(biāo)函數(shù)（SSE或者其他的），直到收斂。
常見的鄰近度和目標(biāo)函數(shù)組合：
初始質(zhì)心：
不同的初始質(zhì)心會收斂到不同的結(jié)果。
隨機初始質(zhì)心：問題是，即使運行多次也不一定能得到好的分類。因為，一旦一個簇內(nèi)有多個質(zhì)心，該簇很可能被分裂。
其他方法：先使用層次聚類，從中提取K個類，使用這K個類的質(zhì)心作為初始質(zhì)心。僅對：樣本較小，K較小有效。
（2）K均值：附加問題
處理空簇
所有的點沒有一個分配到一個質(zhì)心。選擇替補質(zhì)心。
離群點
離群點對于k-均值聚類有較大影響，應(yīng)該刪除。
后處理SSE
增加簇：
分裂一個簇：選擇SSE最大的分裂。
引進一個新的質(zhì)心：選擇離所有質(zhì)心最遠的點。
減少簇：
拆散一個簇：刪除簇的對應(yīng)質(zhì)心。簇中的點重新分配。
合并兩個簇：選擇兩個質(zhì)心最接近的兩個簇合并。
增量的更新質(zhì)心
給定一個目標(biāo)函數(shù)，每步要零次或兩次更新質(zhì)心。
可能產(chǎn)生次序依賴性問題，開銷也稍微大一些。
（3）二分K均值
思路：
為了得到 K 個簇，將所有點分裂成兩個簇，從這些簇中，選取一個繼續(xù)分裂，直到產(chǎn)生 K 個簇。
算法：
帶分裂的簇選擇方法有很多：最大的簇，最大SSE的簇等。
（4）優(yōu)點與缺點
優(yōu)點：二分K均值，不太受初始值的影響。
缺點：不能處理非球形簇、不同尺寸、不同密度的簇。
三、凝聚層次聚類
（1）基本算法
（2）距離的度量：
最短距離（min）、最長距離（max）、平均距離、ward和質(zhì)心距離
（3）簇鄰近度的Lance-Williams公式
Lance-Williams公式：
=\alpha_{A}p(A,Q)+ \alpha_{B}p(B,Q)+\beta p(A,B)+\gamma |p(A,Q)-p(B,Q)|)
A、B、Q合并得到R。p(. , .)是鄰近度函數(shù)，以上表示它們?yōu)榫€性函數(shù)。
下面是Lance-Williams公式魚鄰近度函數(shù)的對應(yīng)：
（4）層次聚類的問題
1、缺乏全局目標(biāo)函數(shù)：避開了解決困難的組合優(yōu)化問題，很難選擇初始點的問題。
2、合并是最終的：一旦合并就不能撤銷。
四、DBSCAN
基于密度聚類算法，尋找被低密度區(qū)域分離的高密度區(qū)域。
（1）傳統(tǒng)密度：基于中心的方法
核心點（core point）：該點給定鄰域的點個數(shù)超過用戶給定閾值 MinPts（Eps為用戶定義的距離）。A點。
邊界點（border point）：不是核心點，它落在某個核心點鄰域。B點。
噪聲點（noise point）：即非核心點也非邊界點。C點。
（2）DBSCAN算法
思路：
任意兩個足夠近（Eps之內(nèi)）的核心點將方到一個簇中。
任何與核心點足夠近的邊界點放到相同簇中（如果邊界點靠近不同簇的核心點，要解決平均問題）。
噪聲點丟棄。
算法步驟：
選擇 Eps 和 MinPts
使用 k-距離
k-最近鄰的距離，對于某個k，計算所有點的k-距離，以遞增排序，則k-距離會在某個部分急劇變化（噪聲點的k-距離很大）。選取k為MinPts，合適的距離為Eps。
下面為，使用Eps=10，MinPts=4的結(jié)果：
（3）優(yōu)點與缺點
優(yōu)點：對抗噪音的能力很強，能夠處理任意形狀和大小的簇。
缺點：DBSCAN當(dāng)計算近鄰的時候，開銷很大。
五、簇評估
（1）非監(jiān)督簇評估：凝聚度、分離度
)
K個簇的有效性，為個體簇的有效性加權(quán)和，下面給出度量表：
1、基于圖：凝聚度、分離度
proximity函數(shù)可以是相似度、相異度，或者是這些量的簡單函數(shù)：
=\sum_{x\in C_{i},y\in C_{i}}proximity(x,y))
=\sum_{x\in C_{i},y\in C_{j}}proximity(x,y))
2、基于原型：凝聚度、分離度
ci是Ci的原型（質(zhì)心），c是總體原型（質(zhì)心）：
=\sum_{x\in C_{i}}proximity(x,c_{i}))
=proximity(c_{i},c_{j}))
=proximity(c_{i},c))
3、輪廓系數(shù)
輪廓系數(shù)（silhouette coefficient）：
1、對于第 i 個對象，計算它到所在簇所有點的平均距離：ai
2、對于第 i 個對象，計算它到不含它的其他簇所有對象的平均距離，找出最小的：bi
3、對于第 i 個對象，輪廓系數(shù)為：
}{max(a_{i},b_{i})})
（3）非監(jiān)督簇評估：近鄰矩陣
可以使用某個距離度量法來度量相似度，得到每個點的距離，匯總得到近鄰矩陣。但是僅使用于小數(shù)據(jù)、抽樣。
（4）簇個數(shù)
使用 SSE 和輪廓系數(shù)來判斷，統(tǒng)計上的 SSE 的說明性更強，統(tǒng)計上不止這一個系數(shù)可以分類。
（5）聚類趨勢
度量空間中的點是否為隨機分布的，使用Hopkins統(tǒng)計量：
