一、概述
（1）聚類分析
目標是精算，分組數據使得瓢宦，組內的對象是相似的（相關的），不同組是不同的（不相關的）灰羽。
（2）聚類類型
1刁笙、層次、劃分
層次聚類（嵌套聚類谦趣，hierarchial clustering）：聚類簇組織成一棵樹，每一個結點是其子女的并座每。
劃分聚類（非嵌套聚類前鹅，partional clustering）：簡單的將數據對象劃分為不重疊的子集。
2峭梳、互斥舰绘、重疊、模糊
互斥聚類（exclusive）：每個對象被指派到單獨的單個簇葱椭。
重疊聚類（overlapping）：一個對象可以同時屬于多個簇捂寿。
模糊聚類（fuzzy clustering）：概率聚類，每個對象以0-1之間的的權值隸屬于一個類孵运，但是每個對象的權值之和為1秦陋。
3、完全治笨、部分
完全聚類（complete clustering）：每個對象指派到一個類驳概。
部分聚類（partial clustering）：某些對象可以不屬于明確定義的類赤嚼。
（3）簇類型
下面顯示一些簇類型：
類型：明顯分離、基于原型（中心簇）顺又、基于圖（連通）更卒、基于密度、共同性質的（概念簇）稚照。
二蹂空、K-均值
（1）基本K-均值算法
算法步驟：
目標函數：
^{2}, c_{i}=\frac{1}{m_{i}}\sum_{x\in C_{i}}x)
上面的第3、4步驟試圖最小化目標函數（SSE或者其他的）果录，直到收斂上枕。
常見的鄰近度和目標函數組合：
初始質心：
不同的初始質心會收斂到不同的結果。
隨機初始質心：問題是雕憔，即使運行多次也不一定能得到好的分類姿骏。因為，一旦一個簇內有多個質心斤彼，該簇很可能被分裂分瘦。
其他方法：先使用層次聚類，從中提取K個類琉苇，使用這K個類的質心作為初始質心嘲玫。僅對：樣本較小，K較小有效并扇。
（2）K均值：附加問題
處理空簇
所有的點沒有一個分配到一個質心去团。選擇替補質心。
離群點
離群點對于k-均值聚類有較大影響穷蛹，應該刪除土陪。
后處理SSE
增加簇：
分裂一個簇：選擇SSE最大的分裂。
引進一個新的質心：選擇離所有質心最遠的點肴熏。
減少簇：
拆散一個簇：刪除簇的對應質心鬼雀。簇中的點重新分配。
合并兩個簇：選擇兩個質心最接近的兩個簇合并蛙吏。
增量的更新質心
給定一個目標函數源哩，每步要零次或兩次更新質心。
可能產生次序依賴性問題鸦做，開銷也稍微大一些励烦。
（3）二分K均值
思路：
為了得到 K 個簇，將所有點分裂成兩個簇泼诱，從這些簇中坛掠，選取一個繼續(xù)分裂，直到產生 K 個簇。
算法：
帶分裂的簇選擇方法有很多：最大的簇却音，最大SSE的簇等改抡。
（4）優(yōu)點與缺點
優(yōu)點：二分K均值，不太受初始值的影響系瓢。
缺點：不能處理非球形簇阿纤、不同尺寸、不同密度的簇夷陋。
三欠拾、凝聚層次聚類
（1）基本算法
（2）距離的度量：
最短距離（min）、最長距離（max）骗绕、平均距離藐窄、ward和質心距離
（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(. , .)是鄰近度函數，以上表示它們?yōu)榫€性函數撤缴。
下面是Lance-Williams公式魚鄰近度函數的對應：
（4）層次聚類的問題
1刹枉、缺乏全局目標函數：避開了解決困難的組合優(yōu)化問題，很難選擇初始點的問題屈呕。
2微宝、合并是最終的：一旦合并就不能撤銷。
四虎眨、DBSCAN
基于密度聚類算法蟋软，尋找被低密度區(qū)域分離的高密度區(qū)域。
（1）傳統(tǒng)密度：基于中心的方法
核心點（core point）：該點給定鄰域的點個數超過用戶給定閾值 MinPts（Eps為用戶定義的距離）嗽桩。A點岳守。
邊界點（border point）：不是核心點，它落在某個核心點鄰域碌冶。B點棺耍。
噪聲點（noise point）：即非核心點也非邊界點。C點种樱。
（2）DBSCAN算法
思路：
任意兩個足夠近（Eps之內）的核心點將方到一個簇中。
任何與核心點足夠近的邊界點放到相同簇中（如果邊界點靠近不同簇的核心點俊卤，要解決平均問題）嫩挤。
噪聲點丟棄。
算法步驟：
選擇 Eps 和 MinPts
使用 k-距離
k-最近鄰的距離消恍，對于某個k岂昭，計算所有點的k-距離，以遞增排序狠怨，則k-距離會在某個部分急劇變化（噪聲點的k-距離很大）约啊。選取k為MinPts邑遏，合適的距離為Eps。
下面為恰矩，使用Eps=10记盒，MinPts=4的結果：
（3）優(yōu)點與缺點
優(yōu)點：對抗噪音的能力很強，能夠處理任意形狀和大小的簇外傅。
缺點：DBSCAN當計算近鄰的時候纪吮，開銷很大。
五萎胰、簇評估
（1）非監(jiān)督簇評估：凝聚度碾盟、分離度
)
K個簇的有效性，為個體簇的有效性加權和技竟，下面給出度量表：
1冰肴、基于圖：凝聚度、分離度
proximity函數可以是相似度榔组、相異度熙尉，或者是這些量的簡單函數：
=\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的原型（質心）骡尽，c是總體原型（質心）：
=\sum_{x\in C_{i}}proximity(x,c_{i}))
=proximity(c_{i},c_{j}))
=proximity(c_{i},c))
3、輪廓系數
輪廓系數（silhouette coefficient）：
1擅编、對于第 i 個對象攀细，計算它到所在簇所有點的平均距離：ai
2、對于第 i 個對象爱态，計算它到不含它的其他簇所有對象的平均距離谭贪，找出最小的：bi
3、對于第 i 個對象锦担，輪廓系數為：
}{max(a_{i},b_{i})})
（3）非監(jiān)督簇評估：近鄰矩陣
可以使用某個距離度量法來度量相似度俭识，得到每個點的距離，匯總得到近鄰矩陣洞渔。但是僅使用于小數據套媚、抽樣。
（4）簇個數
使用 SSE 和輪廓系數來判斷磁椒，統(tǒng)計上的 SSE 的說明性更強堤瘤，統(tǒng)計上不止這一個系數可以分類。
（5）聚類趨勢
度量空間中的點是否為隨機分布的浆熔，使用Hopkins統(tǒng)計量：
