一阶界、了解層次聚類

????層次聚類方法對給定的數(shù)據(jù)集進行層次的分解摘盆，直到滿足某種條件為止挺尿，傳統(tǒng)的層次聚類算法主要分為兩大類算法：

1奏黑、凝聚的層次聚類：AGNES算法(AGglomerative NESting)==>采用自底向上的策略。最初將每個對象作為一個簇编矾，然后這些簇根據(jù)某些準則被一步一步合并熟史，兩個簇間的距離可以由這兩個不同簇中距離最近的數(shù)據(jù)點的相似度來確定；聚類的合并過程反復進行直到所有的對象滿足簇數(shù)目窄俏。

2蹂匹、分裂的層次聚類：DIANA算法(DIvisive ANALysis)==>采用自頂向下的策略。首先將所有對象置于一個簇中凹蜈，然后按照某種既定的規(guī)則逐漸細分為越來越小的簇(比如最大的歐式距離)限寞，直到達到某個終結(jié)條件(簇數(shù)目或者簇距離達到閾值)忍啸；

二、AGNES和DIANA算法優(yōu)缺點

1履植、簡單计雌，理解容易。

2玫霎、合并點/分裂點選擇不太容易凿滤。

3、合并/分類的操作不能進行撤銷庶近。

4翁脆、大數(shù)據(jù)集不太適合。

5拦盹、執(zhí)行效率較低O(t*n2)鹃祖，t為迭代次數(shù)，n為樣本點數(shù)普舆。

三恬口、AGNES算法中簇間距離

1、最小距離(SL聚類)

????兩個聚簇中最近的兩個樣本之間的距離(single/word-linkage聚類法)沼侣。

????最終得到模型容易形成鏈式結(jié)構(gòu)祖能。

2、最大距離(CL聚類)

????兩個聚簇中最遠的兩個樣本的距離(complete-linkage聚類法)蛾洛。

????如果存在異常值养铸，那么構(gòu)建可能不太穩(wěn)定。

3轧膘、平均距離(AL聚類)

????兩個聚簇中樣本間兩兩距離的平均值(average-linkage聚類法)钞螟。

????兩個聚簇中樣本間兩兩距離的中值(median-linkage聚類法)。

四谎碍、層次聚類優(yōu)化算法?

1鳞滨、CF-Tree：

? ??CF-Tree(Cluster Feature Tree)：每個節(jié)點是由三個聚類特征組成。這三個聚類特征構(gòu)成一個三元組蟆淀，用(N, LS, SS)來表示拯啦。

其中：

N表示這個CF中包含的樣本數(shù)量；

LS表示這個CF中包含的樣本點的向量和熔任；

SS表示這個CF中包含的樣本點各個特征的平方和褒链。

CF-Tree中父節(jié)點的某個CF值等于其指向的所有子節(jié)點CF值的總和。

CF-Tree的幾個關(guān)鍵超參數(shù)：

B：每個內(nèi)部節(jié)點最大的CF個數(shù)疑苔。

L：每個葉節(jié)點最大的CF個數(shù)甫匹。

T：新樣本若被分到某一CF中，其到該CF中心的距離最大值。

CF-Tree構(gòu)建步驟：

1兵迅、初始狀態(tài)哀墓，CF樹是空的，無任何樣本喷兼。讀入第一個樣本x(a,b)，生成一個CF三元組后雷，此處N=1季惯，LS=(a,b)，SS=a2+b2臀突，我們令其為CF1勉抓。

2、讀入第二個樣本候学，若到CF1的距離小于T藕筋，那么這個樣本也歸入CF1，更新三元組數(shù)據(jù)梳码；如果大于T隐圾，則新劃分出一個CF，這個樣本作為CF2當中的首個樣本掰茶，生成一個CF三元組暇藏。

注意：此時都是在節(jié)點內(nèi)進行CF的建立，而非產(chǎn)生新的節(jié)點濒蒋。

3盐碱、分裂：如果新數(shù)據(jù)進入該節(jié)點后，距離所有CF中心的距離都大于T沪伙，且Cf個數(shù)在生成新CF后大于B瓮顽，則該節(jié)點需要進行劃分。

4围橡、找到該分支內(nèi)各個CF之間的距離最大的兩個CF期奔，分別作為兩個新葉子結(jié)點的CF，再計算剩余CF到這兩個CF之間的距離锦援，距離近的分到一個節(jié)點當中剃袍。

5、如果節(jié)點分裂過后葉子節(jié)點個數(shù)超過L黔漂，則該節(jié)點要進行分裂诫尽，分裂方式和上一步相同。

6炬守、生成CF和分裂過程直至所有樣本均進入CF樹后停止牧嫉。

BIRCH算法

? ??BIRCH算法(平衡迭代削減聚類法)：聚類特征使用3元組進行一個簇的相關(guān)信息，通過構(gòu)建滿足分枝因子和簇直徑限制的聚類特征樹(CF-Tree)來求聚類，聚類特征樹其實是一個具有兩個參數(shù)分枝因子(B酣藻、L)和類直徑(T)的高度平衡樹曹洽；分枝因子規(guī)定了樹的每個節(jié)點的子女的最多個數(shù)，而類直徑體現(xiàn)了對這一類點的距離范圍辽剧；非葉子節(jié)點為它子女的最大特征值送淆；聚類特征樹的構(gòu)建可以是動態(tài)過程的，可以隨時根據(jù)數(shù)據(jù)對模型進行更新操作怕轿。對應生成的結(jié)果就是一個簇(聚類特征 - CF)偷崩；BIRCH算法的過程就是建立CF-Tree的過程。

優(yōu)缺點：

1撞羽、適合大規(guī)模數(shù)據(jù)集阐斜，線性效率；

? 層次聚類算法的復雜度為OT(n2)诀紊；

? 優(yōu)化后的BIRCH算法構(gòu)建聚類特征樹(CF-Tree)的時間復雜度為O(n)谒出；

2、只適合分布呈凸形或者球形的數(shù)據(jù)集邻奠、需要給定聚類個數(shù)和簇之間的相關(guān)參數(shù)笤喳；

CURE算法

CURE算法(使用代表點的聚類法)：是一種凝聚算法(AGNES)。該算法先把每個數(shù)據(jù)點看成一類碌宴，然后合并距離最近的類直至類個數(shù)為所要求的個數(shù)為止莉测。但是和AGNES算法的區(qū)別是：取消了使用所有點或用中心點+距離來表示一個類，而是從每個類中抽取固定數(shù)量唧喉、分布較好的點作為此類的代表點捣卤，并將這些代表點(一般10個)乘以一個適當?shù)?b>收縮因子(一般設置0.2~0.7之間)，使它們更加靠近類中心點八孝。代表點的收縮特性可以調(diào)整模型可以匹配那些非球形的場景董朝，而且收縮因子的使用可以減少噪音對聚類的影響。

代表點不是原來的點干跛，而是那些需要重新計算的點子姜。