聚類分析 Cluster Analysis

---

肝到爆炸嗚嗚嗚

一、什么是聚類分析

關鍵詞

1?? 簇 Cluster：數(shù)據(jù)對象的集合，相同簇中的數(shù)據(jù)彼此相似，不同簇中的數(shù)據(jù)彼此相異。

2?? 聚類分析 Cluster analysis：根據(jù)數(shù)據(jù)特征找到數(shù)據(jù)中的相似性，并將相似的數(shù)據(jù)聚集(分組)到一個簇中。

3?? 無監(jiān)督學習 Unsupervised learning：并沒有為數(shù)據(jù)給出預先定義好的類別

---

好啦，我們現(xiàn)在有了理論儲備啦！就讓我們一起走進聚類分析吧~

聚類分析在我們的生活中并不陌生，甚至是隨處可見的：比如商場的促銷活動呀，城市規(guī)劃的地塊評估呀，生物學中基因的分組呀，GIS中的空間模式分布評估呀，還有各種標簽tag什么的。在數(shù)據(jù)挖掘領域中，聚類分析常常用于：

• 作為一個深入了解數(shù)據(jù)分布的獨立工具(As a stand-along tool to get insight into data distribution)
• 作為其他算法的預處理過程(As a preprocessing step for other algorithms)

這樣一個依托于無監(jiān)督的分組方法，結果可是隨心所欲千奇百怪的哦，比如在動漫角色特征聚類里，有的聚類方法把灰毛的伊蕾娜分到了白毛組，有的聚類方法則是分到了銀發(fā)組。

為了避免這種情況，我們需要設定指標去評估一個聚類方法的好壞，讓不同的聚類結果之間有了可比性，就能知道哪些是好孩子啦。

一種好的聚類方法可以生成好質(zhì)量的簇，而這些簇滿足：

• 簇內(nèi)相似性高
• 簇間相似性低

可以理解為，不同學校的小孩子之間應該接觸的少，一個學校的小孩子之間應該接觸的多。

在這基礎上，聚類結果的具體質(zhì)量應該取決于相似度度量算法，以及它的實現(xiàn)。如果一個聚類還能挖掘一些或者全部的隱藏模式，我們也可以認為它是一個高質(zhì)量的聚類方法。

The quality of clustering result depends on both the similarity measure used by the method and its implementation.

The quality of a clustering method is also measured by its ability to discover some or all of the hidden patterns.

通常，數(shù)據(jù)科學家們使用相異度/相似度矩陣 Dissimilarity/Similarity metric來對不同數(shù)據(jù)特征之間的相似度進行度量，一般是通過距離公式進行，數(shù)據(jù)$i$和$j$之間的距離可以記作$d(i,j)$。

當然，不同數(shù)據(jù)類型之間，比如連續(xù)數(shù)據(jù)、布爾型數(shù)據(jù)、分類數(shù)據(jù)、語義數(shù)據(jù)、序數(shù)數(shù)據(jù)，他們所運用的距離度量方法也是不同的。對于距離度量方法的權重分配，也是由數(shù)據(jù)語義和應用所決定的。

Weights may be assigned to different variables based on applications and data semantics.

相似性度量只是最基本的，下表給出了聚類的一些其他需求：

需求解釋

Scalability	可擴展的
Ability to deal with different types of attributes	能夠處理不同屬性
Ability to handle dynamic data	能處理動態(tài)數(shù)據(jù)
Discovery of clusters with arbitrary shape	發(fā)現(xiàn)任意形狀的簇
Minimal requirements for domain knowledge to determine input parameters	對確定輸入?yún)?shù)的領域知識的最低要求
Able to deal with noise and outliers	能處理噪聲和離群數(shù)據(jù)
Insensitive to order of input records	對于輸入數(shù)據(jù)順序的不敏感性
High dimensionality	高維特性
Incorporation of user-specified constraints	合并用戶指定的約束條件
Interpretability and usability	可解釋性和可應用性

除卻聚類方法的評估外，我們也可以基于簇的屬性進行評估哦，那么一個普通的簇有什么屬性呢？

質(zhì)心 Centroid

一般是一個簇的中間，可以寫作：
$$C=\frac{{\sum }_i^N(t_i)}{N}$$
半徑 Radius

簇中點到簇質(zhì)心的距離的平均（點與中心），寫作：
$$R=\sqrt{\frac{{\sum }_i^N(t_i?c{)}^2}{N}}$$
直徑 Diameter

簇中所有點之間的平均距離的平方根（點與點)，寫作：
$$D=\sqrt{\frac{{\sum }_i^N{\sum }_j^N(t_i?t_j{)}^2}{N(N?1)}}$$

---

二、聚類分析中的數(shù)據(jù)類型

好了，上一節(jié)我們知道了什么是簇，什么是聚類，以及如何評價一個聚類方法的好壞，下面我們就要進一步了解聚類分析是如何運作的。數(shù)據(jù)挖掘是以數(shù)據(jù)為主導，以數(shù)據(jù)為驅(qū)動的，拋開具體數(shù)據(jù)空談算法是不合理的。所以，我們需要來看看聚類分析中的輸入數(shù)據(jù)究竟都什么牛馬。

關鍵字

1?? 數(shù)據(jù)矩陣 Data matrix：數(shù)據(jù)矩陣就是把數(shù)據(jù)堆疊在一起形成的二維表啦，每一行是一個記錄record，每一列是一個屬性class, feature, attribute... etc.，可以寫作如下形式：
$$?\begin{array}{ccc}{x}_{11}& ?& x_{1n}\\ ?& & ?\\ x_{m1}& ?& x_{mn}\end{array}?$$
2?? 相異矩陣 Dissimilarity matrix：用于衡量各個數(shù)據(jù)之間的相異程度，等于$1?相似度$，所以元素自己和自己之間的相異度是0啦：
$$?\begin{array}{ccc}0& & \\ ?& 0& \\ d(n,1)& ?& 0\end{array}?$$

---

從上文聚類好壞的討論中，我們提到不同數(shù)據(jù)之間的相似性需要采用不同的距離度量方式，在聚類分析中，常見的數(shù)據(jù)源大致可分為六種：

類型解釋

Interval-scaled variables	數(shù)值變量
Binary variables	二值數(shù)據(jù)
Nominal variables	名義數(shù)據(jù)
Ordinal variables	順序數(shù)據(jù)
Ration-scaled variables	比率尺度數(shù)據(jù)
Variables of mixed type	混合數(shù)據(jù)

1?? 數(shù)值變量

我們對這類數(shù)據(jù)的處理是需要先進行標準化將其進行區(qū)間縮放的，標準化方法稱為z得分(z-score)法：
$$z_{if}=\frac{x_{if}?m_f}{s_f}$$
其中，
$$m_f=\frac{x_{1f}+x_{2f}+...+x_{nf}}{n}$$
也就是數(shù)據(jù)集中$f$屬性的平均值；
$$s_f=\frac{\sum |x_{if}?m_f|}{n}$$
也就是采用絕對值替代開平方算法的標準差，z-score與標準差標準化的區(qū)別就在于使用了絕對值。使用平均絕對偏差，要比使用標準差更加穩(wěn)健。

Using mean absolute deviation is more robust than using standard deviation.

好啦，標準化完后，我們就可以用距離度量公式計算相似性啦，距離度量公式有很多，例如歐氏距離、馬氏距離、切比雪夫距離、曼哈頓距離、閔可夫斯基距離、漢明距離、余弦距離等等，這里我們介紹閔可夫斯基距離。
$$d(i,j){=}^q\sqrt{\sum |x_{in}?x_{jn}|}$$
當$q$取1，就成了曼哈頓距離，當$q$取2，就成了歐氏距離。

---

2?? 二值變量

對于一個二值數(shù)據(jù)表，我們可以寫作：

其中，數(shù)據(jù)之間的對稱性度量表示為：
$$d(i,j)=\frac{b+c}{a+b+c+d}$$
不對稱性度量表示為：
$$d(i,j)=\frac{b+c}{a+b+c}$$
在不對稱矩陣中，我們需要注意的是后面那個不對稱性度量。

---

3?? 名義數(shù)據(jù)

這類數(shù)據(jù)呢，一般來說不具備可比性。比如小明小紅小芳，紅黃藍什么的。

目前主流的處理方法有兩種：

第一種，簡單匹配。
$$d(i,j)=\frac{p?m}{p}$$
其中，$p$表示總的名義數(shù)據(jù)數(shù)量，$m$表示兩個數(shù)據(jù)匹配到的數(shù)據(jù)次數(shù)。

第二種，構建one-hot編碼。

第一種方法常在簡單處理中使用，而第二種一般多見于機器學習和深度學習。

---

4?? 序數(shù)數(shù)據(jù)

這類數(shù)據(jù)相較于名義數(shù)據(jù)，雖然還是屬于定性數(shù)據(jù)范疇但是帶上了可比性哦。比如：大中小，優(yōu)良差什么的。

對其的處理分為三步：

第一步，將其按照大小排列，用大小次序代替數(shù)據(jù)值。
$$r_{if}\in \{1,...,M_f\}$$
第二步，將數(shù)據(jù)的范圍縮放到$[0,1]$區(qū)間：
$$z_{if}=\frac{r_{i}f?1}{M_f?1}$$
第三步，通過數(shù)值的方式，對數(shù)據(jù)的不相似性進行計算。

---

5?? 比率數(shù)據(jù)

比率數(shù)據(jù)是一個非線性的尺度，一般不同比率之間的差距是指數(shù)倍的。對其進行的處理分為三步：

首先先取對數(shù)，使其區(qū)間縮放：
$$y_{if}=log(x_{if})$$
接著，假設他們是一個連續(xù)數(shù)據(jù)，并將他們的秩作為定序數(shù)據(jù)

最后，在利用處理區(qū)間縮放數(shù)據(jù)的方式對其進行計算。

---

6?? 混合數(shù)據(jù)

一種常用的權衡多種屬性距離的公式如下所示：
$$d(i,j)=\frac{{\sum }_{f=1}^p{\sigma }_{ij}^{(f)}{d}_{ij}^{(f)}}{{\sum }_{f=1}^p{\sigma }_{ij}^{(f)}}$$
其中，${\sigma }_{ij}^{(f)}$是一個二值量，當兩個數(shù)據(jù)同時具有屬性列$f$時，這個值取到$1$，否則，在任意數(shù)據(jù)缺失該屬性列，或者當$f$是一個非對稱屬性，且$x_{if}=x_{jf}=0$時取到$0$。$d$的計算則是根據(jù)屬性類型，應用各自的公式。

---

好了，說完了每種類型以及距離度量后，我們來做個小練習吧！

這樣一組數(shù)據(jù)中，Test-1是分類數(shù)據(jù)，Test-2是定序數(shù)據(jù)，Test-3則是比率數(shù)據(jù)。

我們現(xiàn)在要計算整張表的數(shù)據(jù)相異度矩陣。

根據(jù)混合數(shù)據(jù)計算公式，我們需要分別對不同種的屬性計算距離。

首先是對Test-1的分類數(shù)據(jù)，我們采用簡單匹配規(guī)則進行計算，得到的相異矩陣為：
$$?\begin{array}{ccccc}0& & & & \\ 1& 0& & & \\ 1& 1& 0& & \\ 0& 1& 1& 0& \end{array}?$$
對于Test-2的定序數(shù)據(jù)，我們需要先轉(zhuǎn)換成rank值，然后進行區(qū)間縮放，最后距離公式進行計算，這里我們選用的是曼哈頓距離

原始數(shù)據(jù)Rank值縮放值

excellent	3	1
fair	1	0
good	2	0.5
excellent	3	1

計算的結果為：

d(1,0)1

d(2,0)	0.5
d(2,1)	0.5
d(3,0)	0
d(3,1)	1
d(3,2)	0.5

$$?\begin{array}{ccccc}0& & & & \\ 1& 0& & & \\ 0.5& 0.5& 0& & \\ 0& 1& 0.5& 0& \end{array}?$$

對于Test-3，我們先對取對數(shù)，然后將對數(shù)視作數(shù)值型數(shù)據(jù)進行規(guī)范化后，再計算距離。

規(guī)范化公式為：
$$y=\frac{x?min}{max?min}$$

原始數(shù)據(jù)對數(shù)縮放值

445	2.65	0.75
22	1.34	0
164	2.21	0.5
1210	3.08	1

于是T3最終的結果為：
$$?\begin{array}{ccccc}0& & & & \\ 0.75& 0& & & \\ 0.25& 0.5& 0& & \\ 0.25& 1& 0.5& 0& \end{array}?$$
綜合三個屬性列，計算結果為：
$$d(i,j)=\frac{d_1(i,j)+d_2(i,j)+d_3(i,j)}{3}$$

$$\begin{gathered} ?\begin{array}{ccccc}0& & & & \\ \frac{0.75+1+1}{3}& 0& & & \\ \frac{0.25+0.5+1}{3}& \frac{0.5+0.5+1}{3}& 0& & \\ \frac{0.25+0+0}{3}& \frac{1+1+1}{3}& \frac{0.5+0.5+1}{3}& 0& \end{array}? \\ =?\begin{array}{ccccc}0& & & & \\ 0.92& 0& & & \\ 0.58& 0.67& 0& & \\ 0.08& 1& 0.67& 0& \end{array}? \end{gathered}$$

---

三、主要聚類算法的分類

我們終于要進入聚類分析的核心：聚類分析算法啦!

根據(jù)算法之間的異同，我們可以將他們分為五大類(沒錯，這也算是一種聚類)。

1?? 分區(qū)方法

• 構建各種分區(qū)，然后通過準則對他們進行評估，例如均方差。
• 典型方法：k-means, k-medoids, CLARANS

2?? 層次方法

• 使用某些準則創(chuàng)建數(shù)據(jù)的層次分解
• 典型方法：Diana, Agnes, BIRCH, ROCK, CHAMELEON

3?? 基于密度的方法

• 基于連通性和密度函數(shù)
• 典型方法：DBSACN, OPTICS, DenClue

4?? 基于格網(wǎng)的方法

• 基于多粒度的結構
• 典型方法：STING, WaveCluster, CLIQUE

5?? 基于概率統(tǒng)計學模型

• 典型方法：EM

---

四、分區(qū)方法 Partitioning Methods

基本概念

將有n個對象的數(shù)據(jù)庫D按照規(guī)則(如最小平方和)劃分成k個簇。

經(jīng)典算法

1?? K-Means聚類

• 初始化：給定k個隨機初始化的中心點
• 迭代：計算每個簇當前的質(zhì)心
• 計算每個點到點前簇中心的距離，并將他們分配進最近的簇

時間復雜度：$O(tkn)$，$n$是對象個數(shù)，$k$是簇個數(shù)，$t$是迭代次數(shù)。

通常條件下會止于全局最優(yōu)解。

缺點：

• 不適用于分類數(shù)據(jù)(只能計算數(shù)值)
• 需要指定聚類簇的個數(shù)
• 無法處理有噪聲的情況和異常值
• 不適合發(fā)現(xiàn)非凸型的簇

變化

🏷 處理分類數(shù)據(jù)：k-modes算法

• 用模式(modes)代替原先的均值
• 基于新的不相似度量方式處理分類對象
• 使用一種基于頻率的方式對簇進行更新

🏷 處理混合數(shù)據(jù)：k-prototype

🏷 期望最大化擴展

• 基于加權度量進行計算

🏷 處理異常數(shù)據(jù)：k-Medoids算法

• 采用簇中最中心的點來代替原先的均值，此時，這個中心點是實際存在的點

實現(xiàn)

import random import math# 隨機生成100個點 points=[(random.randint(-50,50),random.randint(-50,50)) for i in range(100)]def k_Means(poi,k=5,epochs=100):# 初始化centroid=[] # 質(zhì)心點cluster=[[0]*(len(poi[0]))+[0] for i in range(k)] # 記錄一個簇中所有點每一個維度上坐標的總和，以及簇點的個數(shù)，這步是方便計算罷了PoiClass=[-1 for i in range(len(poi))]# 映射表，輸出每個點對應的類Break=[-1 for i in range(len(poi))] # 用來控制邏輯，比如當這個表跟映射表的差距小于2時，我們就不迭代了# 隨機選取中心點# 無放回抽樣for i in range(k):if (v:=random.choice(poi)) not in centroid:centroid.append(v)# 計算每個點的歐氏距離def edis(x,y):return math.sqrt(sum([(x[i]-y[i])**2 for i in range(len(x))]))# 開始迭代for i in range(epochs):# 計算每個點到中心的距離for pId,p in enumerate(poi):dis,idx=2e31,0for Idx,c in enumerate(centroid):if (v:=edis(p,c))<dis:dis,idx=v,Idx # 獲取最小值時候的坐標# 簇統(tǒng)計量，方便計算for i in range(len(p)):cluster[idx][i]+=p[i]cluster[idx][-1]+=1 # 簇的數(shù)量# 更新映射表PoiClass[pId]=idx# 重新計算每個簇的中心，這個中心是平均值，并不一定是存在的點for i,v in enumerate(cluster):new_c=[]for j in range(len(v)-1):new_c.append(v[j]/v[-1])centroid[i]=new_ccluster[i]=[0]*len(poi[0])+[0] # 將常量清零# 設置終止迭代條件if sum(PoiClass[i]==Break[i] for i in range(len(poi)))>=len(poi):return PoiClassBreak=PoiClass[:]return PoiClass

---

五、層次方法 Hierarchical Methods

這類方法并不需要設置初始的聚類簇k，但是需要設置終止條件。例如：

相較于分區(qū)的方法，層次方法是一種基于概念級的，不需要人為給定簇大小的方法，他能夠遠距離的獲取相似對象。

下面我們來介紹幾個經(jīng)典算法：

1?? AGNES (Agglomerative Nesting)

• 由Kaufmann和Rousseeuw在1990年提出
• 使用單鏈路方法和相異矩陣
• 合并相異度最小的點
• 采用一種非下降的方式進行合并
• 最終，所有的點都會屬于一個集群

2?? DIANA (Divisive Analysis)

• 還是那兩人在同一年提出的
• 就是AGNES的逆變換

主要缺點：

• 不能很好的進行擴展，時間復雜度至少是$O(n^2)$級別
• 不能撤銷之前的操作，類似于馬爾科夫鏈

集成基于距離和層次的聚類算法

• BIRCH(1996) 采用cf -樹，逐步調(diào)整子聚類質(zhì)量

• ROCK (1999)

• CHAMELEON(1999)

3?? BIRCH

BIRCH是一種聚合層次聚類，他構建了一個CF樹(Clustering Feature Tree)，用于增量生長。

階段一 Phase 1

掃描數(shù)據(jù)庫，生成一個在內(nèi)存中的初始CF樹(數(shù)據(jù)的多層次壓縮，試圖保留數(shù)據(jù)固有的聚類模式)

階段二 Phase 2

使用聚類算法對CF樹的節(jié)點進行聚類

CF要素是一個記錄了點數(shù)量，坐標向量，坐標平方和的要素，用這些屬性去描述數(shù)據(jù)。

CF樹是一個高度平衡樹，它分層級的去存儲了CF要素。

構建CF樹有兩個要素：

• 分支系數(shù)：子項的最大數(shù)量
• 閾值：葉子結點上子簇的最大直徑

大概跟這個一樣。

算法步驟：

• 將每個對象插入到最近的葉子結點
• 如果一個葉子結點的直徑超過閾值，那么將被分類
• 更新CF要素以及該路徑上所有祖先
• 如果CF樹的大小太大，從葉節(jié)點重新構建樹，不重新掃描原始對象
• 兩個參數(shù)（分支因子，閾值），控制樹的大小

復雜度

• $O(n)$
• 只需要一次掃描就行，$IO$開銷很小

缺點

?只處理數(shù)字數(shù)據(jù)，并對數(shù)據(jù)記錄的順序敏感

?不擅長任意形狀的集群

4?? CURE

CURE算法是一種采用表征量進行聚類的算法。

算法步驟

• 將每個獨立點作為一個分割聚類開始
• 合并周圍的簇，直到每個簇包含超過c個點
• 對于每個簇，使用c個散列點作為代表
• 如果有超過k個簇，那么將會合并表征量最接近的簇，并且更新代表點

選擇表征點

• 首先先選擇一個離簇平均值最遠的點
• 然后，選擇(c-2)個最遠點采樣點
• 將散列點朝著均值縮小$\alpha$
• 于是，每個散列點$p$的表征都有：$p+\alpha (mean?p)$

合并

• 兩個簇表征點最小的歐氏距離

特點

• 由于存在多個代表點，所以CURE可以用于發(fā)現(xiàn)任意形狀的簇
• 對于異常值不敏感
  • 由于向平均值做了縮小
• 時間復雜度為：$O(n^{2}log(n))$
• 對于大規(guī)模的數(shù)據(jù)庫，還是要進行分區(qū)和采樣的

---

六、 基于密度的方法 Density-Based Methods

特點

• 發(fā)現(xiàn)任意形狀的簇
• 能夠處理噪聲
• 需要密度參數(shù)作為終止條件
• 復雜度是$O(n^2)$

一般來說，基于密度的方法有兩個主要的參數(shù)：

1?? n鄰域

• 點半徑n內(nèi)的鄰域

2?? 最小點

• 鄰域內(nèi)包含的最小點數(shù)量

核心對象

如果一個點鄰域內(nèi)的點超過了最小點數(shù)量，那么這個點就是一個核心對象(core object)

直接密度可達

• 一個點$p$是一個點$q$的直接密度可達點
  • $p$屬于$q$的鄰域
  • $q$是一個核心對象

例如：

密度可達

如果$p$可以由$q$的直接可達鏈得到，那么$p$稱為$q$的密度可達點。

這個意思是，$o$是$q$的直接可達點，$p$是$o$的直接可達點，于是有：
$$q?>o?>p$$

密度連接

密度連接點表示如果$p$和$q$都是$o$的密度可達點，那么$p$和$q$稱為密度連接點

下面我們介紹一個老大哥：DBSCAN

算法步驟

• 設置每個對象為未訪問

• 隨機選擇一個未訪問的點$p$,標記$p$表示訪問

• 如果p的半徑為$n$的鄰域中至少存在MinPts個對象

  • 我們就創(chuàng)建一個新的簇，并將$p$加入$c$
  • 設N 是$p$鄰域中對象的集合
  • 對在$N$中的每個點$p^{\prime }$
    • 如果$p^{\prime }$是未訪問的
      • 標記$p^{\prime }$為訪問節(jié)點
      • 如果這個$p^{\prime }$也是核心節(jié)點，那么將它范圍內(nèi)的點加入到$N$
    • 如果$p^{\prime }$還不是任何簇中的成員，我們就把$p^{\prime }$加入$c$
  • 輸出簇$c$

• 否則，標記$p$為噪聲

• 重復以上直到每個點被訪問

實現(xiàn)

def DBSCAN(poi,radius=1,MinPts=5):def edis(x,y):return math.sqrt(sum((x[i]-y[i])**2 for i in range(len(x))))unvisit=set([i for i in range(len(poi))]) # 創(chuàng)建訪問表Clusters=[-1]*len(poi) # 一個hash表，判斷哪個點對應哪個簇c=0while len(unvisit):# 隨機選一個中心點p=random.choice(list(unvisit))unvisit.remove(p)# 鄰域展開！neighbor=set()for id,pn in enumerate(poi):if edis(poi[p],pn)<=radius:neighbor.add(id)if len(neighbor)>=MinPts:# 創(chuàng)建一個新的簇Clusters[p]=c# 遍歷鄰域點while neighbor:id=neighbor.pop()if id in unvisit:unvisit.remove(id)# 找他的鄰域n=set()for Id,pi in enumerate(poi):if edis(poi[id],pi)<radius:n.add(Id)if len(n)>=MinPts:# 合并neighbor|=n# 如果這個點不屬于任何簇，將其加入cif Clusters[id]==-1:Clusters[id]=c# 否則，我們認為p是一個噪聲(-1)c+=1return Clustersprint(DBSCAN(points))

結果展示

嗯，離群點被標記為了-1

如何選擇距離也會對結果產(chǎn)生很大的影響。

---

七、基于格網(wǎng)的方法 Grid-Based Methods

采用多分辨率網(wǎng)格數(shù)據(jù)結構

有幾種有趣的方法

• STING(一種統(tǒng)計信息網(wǎng)格方法) by Wang, Yang, Muntz)(1997)

• WaveCluster由Sheikholeslami、Chatterjee和Zhang設計

  • 利用小波方法的多分辨率聚類方法

• CLIQUE: Agrawal等人(SIGMOD ’ 98)

  • 在高維數(shù)據(jù)上處理

我們來看一個算法：STING

描述

• 空間區(qū)域被劃分為矩形單元格

• 有幾個級別的單元對應不同的分辨率級別

• 上層的每個單元都被劃分為下一層的一些更小的單元

• 每個單元格的統(tǒng)計信息預先計算和存儲，并用于回答查詢
• 從低級單元的統(tǒng)計量可以很容易計算出高級單元
• 群集是根據(jù)計數(shù)、單元格大小等來識別的

有點像高維度的線段樹

查詢方法

• 使用自頂向下的方法來回答空間數(shù)據(jù)查詢
• 從一個預先選擇的層開始-通常有少量的單元
• 對于當前級別中的每個單元格，計算置信區(qū)間
• 將不相關的單元格從進一步的考慮中刪除
• 完成檢查當前層后，繼續(xù)檢查下一層相關單元格
• 重復這一過程，直到到達底層

優(yōu)勢

• 獨立查詢
• 增量更新
• $O(k$)查詢復雜度
• $O(n)$生成復雜度

缺點

• 所有的簇邊界都是水平或垂直的，沒有檢測到對角線邊界
• 處理時間取決于每個網(wǎng)格的大小

這類方法用的比較少，所以就簡略介紹下了

---

八、異常分析 Outlier Analysis

什么是異常值(極端值、離群點)Outlier？

• 這組對象與其余的數(shù)據(jù)有很大的不同
  • 可能是由于測量或者執(zhí)行時的誤差引起的
  • 也可能是變量內(nèi)在可變性引起的

尋找異常值是非常有價值的。

那么如何找到一組數(shù)據(jù)中不聽話的孩子呢？

1?? 可視化

2?? 聚類

3?? 計算方法

• 基于統(tǒng)計學的檢測方法
• 基于偏差的檢測方法
• 基于距離的檢測方法

基于統(tǒng)計學的聚類檢查方法

• 假設數(shù)據(jù)集有一個分布(例如正態(tài)分布)，然后使用不一致性檢驗找到異常值

缺點

• 大多數(shù)測試只能對單個屬性進行
• 很多時候，數(shù)據(jù)的分布并不會給出
• 需要輸入?yún)?shù)

基于距離的異常值檢測方法

• 這個方法不需要統(tǒng)計假設和分布，克服了傳統(tǒng)統(tǒng)計學方法的不足

• 基于距離的離群值:如果$A$是數(shù)據(jù)庫中的一個離群值，那么在數(shù)據(jù)集$T$中，至少有一部分$p$到$A$的距離要超過$d$

• 大致可分為：

  • 基于索引的算法
  • 基于單元的算法

1?? 基于索引的算法

• 搜索每個物體$O$的半徑為$d$鄰居
• 基于多維索引結構，如$kd$樹
• 確定每個鄰接內(nèi)的最大目標數(shù)量
• 最大開銷$O(K{n}^2)$
• 缺點：
  • 樹的構建是計算密集型的

2?? 基于單元的算法

• 單元分區(qū)

  • 將數(shù)據(jù)空間分成邊長是$d/2k^{1/2}$的單元

  • 每個單元有兩層

    • 第一層只有一個單元厚度
    • 第二層則是$2k^{1/2}?1$單元厚度

• 異常檢測

  • 如果第一層計數(shù)為>M，則此單元中無異常值
  • 如果第二層計數(shù)<=M，則所有對象都是異常值
  • 否則，檢查單元格中的每個對象

基于偏差的方法

• 通過檢測每個組中的主要特征來識別異常
• “偏離”此描述的對象被認為是異常值

---

九、總結

• 聚類分析根據(jù)對象的相似性對對象進行分組，具有廣泛的應用

• 可以對各種類型的數(shù)據(jù)計算相似性度量

• 聚類算法可以分為分區(qū)方法、層次方法、基于密度的方法和基于網(wǎng)格的方法

• 異常點檢測和分析對于欺詐檢測等非常有用，可以通過統(tǒng)計、基于距離或基于偏差的方法進行

總結

以上是生活随笔為你收集整理的【数据挖掘】聚类分析的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。