其他
這篇文章的整體排版主要是根據(jù)個人的博客來噠材蹬，如果感興趣的話可以去我的自己搭建的個人博客看這篇文章火邓。
正文
聚類算法上中講了大名鼎鼎的K-Means算法及其優(yōu)化變種袖订，在這篇中幾種講述兩位兩種不同思路的聚類算法。
層聚類算法
傳統(tǒng)層聚類算法—AGNES和DIANA算法
層次聚類和K-Means的思路不太一樣隘截，它的思路有點像是決策樹扎阶，按照層次進行分解汹胃，知道滿足某種條件為止，傳統(tǒng)的層次聚類分為自底而上东臀，和自上而下兩類：
- 凝聚的層次聚類:
這類算法是采用采用自底向上的策略着饥，其中的代表便是AGNES算法(AGglomerative Nesting)，它的核心思想是：最初將每個對象作為一個簇惰赋，然后這些簇根據(jù)某些準則被一步一步合并宰掉，兩個簇間的距離可以由這兩個不同簇中距離最近的數(shù)據(jù)點的相似度來確定。聚類的合并過程反復進行直到所有的對象滿足簇數(shù)目赁濒。 - 分裂的層次聚類：
和凝聚的層次聚類相反轨奄，這種是采用自頂向下的策略，代表算法為DIANA算法(DIvisive Analysis)拒炎。其核心思想是：首先將所有對象置于一個簇中挪拟，然后按照某種既定的規(guī)則逐漸細分為越來越小的簇(比如最大的歐式 距離)，直到達到某個終結條件(簇數(shù)目或者簇距離達到閾值)击你。
在AGNES算法中都提到了舞丛，簇是根據(jù)某些原則進行分裂或者合并的，而這個原則就是簇間距離果漾。計算簇間距離的方法有最小距離（SL聚類）球切，最大距離（CL聚類）以及平均距離（AL聚類），具體的說明如下：
- 最小距離（SL聚類）
選擇兩個聚簇中最近的兩個樣本之間的距離（Single/Word-Linkage）
注：得到的模型容易形成鏈式結構 - 最大距離（CL聚類）
選擇兩個聚簇中最圓的兩個眼本的距離（Complete-Linkage）
注：如果出現(xiàn)了異常值的話绒障，那他們的構建很容易受這個異常值的影響吨凑。 - 平均距離（AL聚類）
選擇兩個聚類中的平均值（Average-Linkage聚類算法）或者中值（Median-Linkage聚類法）
AGNES和DIANA算法優(yōu)缺點如下：
- 簡單，理解容易户辱。
- 合并點/分裂點選擇不太容易鸵钝。
- 合并/分類的操作不能進行撤銷。
- 由于執(zhí)行效率較低
庐镐，
為迭代次數(shù)恩商，
為樣本點數(shù)。
層次聚類優(yōu)化算法
之前我們看到了傳統(tǒng)的層次聚類算法必逆，由于其執(zhí)行效率太低怠堪，且不能動構建的的特點，顯然不適合大數(shù)據(jù)集名眉。于是我們在此基礎上引入了BIRCH算法和CURE算法粟矿。
BIRCH算法
BIRCH (balanced iterative reducing and clustering using hierarchies) 算法，英文的全稱翻譯過來以后是平衡迭代削減聚類算法损拢，其構成和我們考研數(shù)據(jù)結構中學過的B+樹非常的類似陌粹，甚至很多特性都是相同的，具體的說它構建的樹叫做CF（Cluster Feature）-Tree福压。
- 節(jié)點掏秩，即簇的結構：
既然是樹或舞，那么就不得不提它的節(jié)點的結構了。在BIRCH構建CF樹的過程中蒙幻，每個節(jié)點等于說是存放了它之下所有節(jié)點的特征映凳，于是他在節(jié)點中存放了如下的三部分數(shù)據(jù)。- N杆煞，指在這個節(jié)點中有多少個樣本點魏宽。
- LS腐泻，指的是這個節(jié)點中的樣本相應特征的和决乎。
- LS，指的是這個節(jié)點中的樣本相應特征的特征的平方和派桩。
- 節(jié)點之間构诚，節(jié)點和子節(jié)點，以及葉子結點之間的關系
節(jié)點和其子節(jié)點是包含的關系铆惑，也就是父節(jié)點中的N范嘱，LS以及SS是其所有子節(jié)點的和。而相應的樣本點的具體信息指包含在底層節(jié)點中（葉子結點的子節(jié)點）员魏，同時葉子結點構成一個單項鏈表丑蛤，同時有一個指針指向其表頭。這點的特性是同B+樹高度一致的撕阎。 - 最多子女個數(shù)受裹，以及分裂判定
和B+樹一樣，對于樹構建中的分叉?zhèn)€數(shù)是有限制的虏束，這個限制需要提前給出棉饶，即分支因子。同時镇匀，值得注意的是照藻，一般而言在構建節(jié)點簇的中心點的時候，一般選用第一個進入這個節(jié)點的樣本點作為中心點汗侵，然后根據(jù)指定的該簇和中心點限定的距離幸缕，即類直徑，其往往通過LS和SS算出晰韵。判斷新入的點是否可以劃入該簇冀值，而分裂節(jié)點的時候，往往以這個初始點進行分割宫屠。
綜上我們可以看出列疗，BIRCH算法的本質其實就是動態(tài)的插入樣本點，然后動態(tài)的根據(jù)規(guī)則構建一個類B+樹浪蹂。它的優(yōu)點是動態(tài)建樹且效率高是線性效率抵栈，即每個樣本點都是一次性插入的告材，同時也節(jié)省內存，所以非常適合大數(shù)據(jù)集古劲。不過遺憾的是它也是采用距離作為分類標準斥赋，故只適合分布呈凸形或者球形的數(shù)據(jù)集、且需要給定聚類個數(shù)和簇之間的相關參數(shù)产艾，而這些對節(jié)點CF的限制可能導致簇類結果和真實不太一致疤剑。
注1：BIRCH不依賴給定的待分類簇數(shù)量K，但是給定了K值最好闷堡，若不一定K值隘膘，最終CF-Tree的葉子結點樹木就是最終分類的簇的數(shù)目。
注2:BIRCH算法在訓練大規(guī)模數(shù)據(jù)集的時候杠览，和mini-batch K-Means相比弯菊，BIRCH算法更加適合類別數(shù)量K比較多的情況。
注3：由于類直徑是通過LS和SS算出的踱阿，所以當特征維度超過20～30左右的時候管钳，不建議使用該算法。
CURE算法（使用代表點的聚類法）
CURE（Clustering Using REpresentatives）软舌，該算法先把每個數(shù)據(jù)點看成一類才漆，然后合并距離最近的類直至類個數(shù)為所要求的個數(shù)為止。但是和AGNES算法的區(qū)別是：取消了使用所有點佛点，或用中心點+距離來表示一個類醇滥，而是從每個類中抽取固定數(shù)量、 分布較好的點作為此類的代表點恋脚，并將這些代表點乘以一個適當?shù)氖湛s因子腺办，使它們更加靠近類中心點。代表點的收縮特性可以調整模型可以匹配那些非球形的場景糟描，而且收縮因子的使用可以減少噪音對聚類的影響怀喉。
CURE算法的優(yōu)點是能夠處理非球形分布的應用場景，同時彩娛樂隨機抽樣和分區(qū)的方式可以提高算法的執(zhí)行效率船响。
密度聚類算法
密度聚類方法的指導思想是：只要樣本點的密度大于某個閥值躬拢，則將該樣本添加到最近的簇中。這類算法可以克服基于距離的算法只能發(fā)現(xiàn)凸聚類的缺點见间，可以發(fā)現(xiàn)任意形狀的聚類聊闯，而且對噪聲數(shù)據(jù)不敏感。不過這種計算的復雜度高米诉，計算量大菱蔬。
密度聚類算法的常用算法有DBSCAN和密度最大值算法。
DBSCAN算法
DBSCAN（Density-Based Spatial Clustering of Applications with Noise），將簇定義為密度相連的點的最大集合拴泌，能夠將足夠高密度的區(qū)域劃分為簇魏身，并且在具有噪聲的空間數(shù)據(jù)上能夠發(fā)現(xiàn)任意形狀的簇。其核心思路是用一個點的ε鄰域內的鄰居點數(shù)衡量該點所在空間的密度蚪腐，該算法可以找出形狀不規(guī)則的cluster惰蜜，而且聚類的時候事先不需要給定cluster的數(shù)量谭羔。
DBSCAN算法流程
它的算法流程如下：
- 如果一個點
的
領域內包含m個對象，則創(chuàng)建一個x作為核心對象的新簇适掰。
- 尋找并合并核心對象直接密度可達的對象
- 沒有新點可以更新簇的時候朝墩，算法結束
注：
1. 每個簇至少包含一個核心對象赡模；
2. 非核心對象可以是簇的一部分创夜，構成簇的邊緣溶耘；
3. 包含過少對象的簇被認為是噪聲；
4. 最大的密度相連對象的集合C為密度聚類中的一個簇瘾杭，它滿足兩個屬性诅病，Maximality和Connectivity哪亿，Maximality指的是若從
DBSCAN相關名詞解釋
其中提到的定義有領域钝吮，密度，MinPts板辽，核心點奇瘦，邊界點，噪音點劲弦，直接密度可達耳标，密度可達，密度相連邑跪。他們的解釋如下：
密度(density)：在
指的是半徑內的點的個數(shù)砸琅。
MinPts：指得是判定該點是不是核心點的時候使用的閥值，記為M
核心點（core point）：如果
,那么稱
的核心點轴踱，記由
症脂，并記
表示由
邊界點（border point）：如果非核心點
噪音點（noise point）：集合中除了邊界點和核心點之外的點都是噪音點，所有噪音點組成的集合叫做
橙凳，顯然這些點就是對應稀疏區(qū)域的點蕾殴。
直接密度可達：這個是密度聚類中最重要的概念，它指的是給定一個對象集合
密度可達：如果存在一個對象鏈
坚踩，如果滿足
是從
直接密度可達的荡灾，那么稱
是從
密度可達的，簡單的來說就像鐵鏈環(huán)環(huán)相扣差不多瞬铸。
密度相連：在集合
，使得對象
密度可達的嗓节，那么對象
DBSCAN算法優(yōu)缺點
優(yōu)點:
- 不需要事先給定cluster的數(shù)目
- 可以發(fā)現(xiàn)任意形狀的cluster
- 能夠找出數(shù)據(jù)中的噪音，且對噪音不敏感
- 算法只需要兩個輸入參數(shù)
- 聚類結果幾乎不依賴節(jié)點的遍歷順序
缺點: - DBSCAN算法聚類效果依賴距離公式的選取拦宣，最常用的距離公式為歐幾里得距離截粗。但是對于高維數(shù)據(jù)，由于維數(shù)太多鸵隧，距離的度量已變得不是那么重要
- DBSCAN算法不適合數(shù)據(jù)集中密度差異很小的情況
MDCA密度最大值聚類算法
MDCA(Maximum Density Clustering Application)算法基于密度的思想引入劃分聚類中绸罗，能夠自動確定簇數(shù)量并發(fā)現(xiàn)任意形狀的簇。另外MDCA一般不保留噪聲豆瘫，因此也避免了閾值選擇不當情況下造成的對象丟棄情況珊蟀。
注：MDCA的算法和AGNES非常相像，不同的是最初的初始簇確定是通過密度來確定的靡羡。
MDCA算法思路
MDCA算法核心一共分三步系洛，劃分、合并簇以及處理剩余節(jié)點三部分略步。
- 將數(shù)據(jù)集劃分為基本簇：
- 對數(shù)據(jù)集X選取最大密度點
描扯，形成以最大密度點為核心的新簇
，按照距離排序計算出序列
,對序列的前M個樣本數(shù)據(jù)進行循環(huán)判斷趟薄，如果節(jié)點的密度大于等于
绽诚，那么將當前節(jié)點添加
- 循環(huán)處理剩下的數(shù)據(jù)集X，選擇最大密度點
卒落，直到X中剩余的樣本數(shù)據(jù)的密度均小于
。
- 對數(shù)據(jù)集X選取最大密度點
- 使用凝聚層次聚類的思想蜂桶，合并較近的基本簇儡毕，得到最終的簇劃分：
- 在所有簇中選擇距離最近的兩個簇進行合并，合并要求是：簇間距小于等于
扑媚，如果所有簇中沒有簇間距小于
- 在所有簇中選擇距離最近的兩個簇進行合并，合并要求是：簇間距小于等于
- 處理剩余節(jié)點，歸入最近的簇
- 最常用疆股、最簡單的方式是：將剩余樣本對象歸入到最近的簇费坊。
MDCA算法名詞解釋
最大密度點：如字面意思，就是密度最大的點旬痹，密度計算公式一般取DBSCAN算法中的密度計算公式附井。
有序序列：根據(jù)所有對象與最大密度點的距離進行排序。
密度閾值：當節(jié)點的密度值大于密度閾值的時候两残，認為該節(jié)點屬于一個 比較固定的簇永毅，在第一次構建基本簇的時候，就將這些節(jié)點添加到對應簇中磕昼，如果小于這個值的時候卷雕，暫時認為該節(jié)點為噪聲節(jié)點节猿。
簇間距離：對于兩個簇C1和C2之間的距離票从，采用兩個簇中最近兩個節(jié)點之間的距離作為簇間距離。
M值：初始簇中最多數(shù)據(jù)樣本個數(shù)
