數(shù)據(jù)挖掘—聚類算法（2）

其他算法

1. CLARA（Cluster Larger Application）是基于k-中心點(diǎn)類型的算法，能處理更大的數(shù)據(jù)集合。CLARA先抽取數(shù)據(jù)集合的多個(gè)樣本，然后用PAM方法在抽樣的樣本中尋找最佳的k中心點(diǎn)，返回最好的聚類結(jié)果作為輸出。但不然k-中心點(diǎn)準(zhǔn)確，CLARA準(zhǔn)確度取決于抽樣算法。

2. CLArANS(Cluster Larger Application baed upon RANdomized search,隨機(jī)搜索聚類算法)，另一種k-中心點(diǎn)的算法，與CLARA類似采用抽樣方法，但也有不同：CLArANS在搜索的每一步都帶一定隨機(jī)性地選取一個(gè)樣本。

層次聚類方法

層次聚類分為兩種：

（1） 凝聚的層次聚類：自底向上的策略，首先將每個(gè)對(duì)象作為一個(gè)簇，然后合并這些原子簇為更大的簇，直到所有的對(duì)象都在同一個(gè)簇中，或者滿足終止條件。

（2） 分類的層次聚類：自頂向下的策略。

AGNES算法

AGNES(Agglomerative Nesting) 是凝聚的層次聚類算法，如果簇C1中的一個(gè)對(duì)象和簇C2中的一個(gè)對(duì)象之間的距離是所有屬于不同簇的對(duì)象間歐式距離中最小的，C1和C2可能被合并。這是一種單連接方法，其每個(gè)簇可以被簇中的所有對(duì)象代表，兩個(gè)簇之間的相似度由這兩個(gè)簇中距離最近的數(shù)據(jù)點(diǎn)對(duì)的相似度來確定。

算法描述：

輸入：包含n個(gè)對(duì)象的數(shù)據(jù)庫，終止條件簇的數(shù)目k

輸出：k個(gè)簇

（1） 將每個(gè)對(duì)象當(dāng)成一個(gè)初始簇

（2） Repeat

（3） 根據(jù)兩個(gè)簇中最近的數(shù)據(jù)點(diǎn)找到最近的兩個(gè)簇

（4） 合并兩個(gè)簇，生成新的簇的集合

（5） Until達(dá)到定義的簇的數(shù)目

算法性能：

（1） 簡單，但遇到合并點(diǎn)選擇困難的情況。

（2） 一旦一組對(duì)象被合并，不能撤銷

（3） 算法的復(fù)雜度為O(n的平方)，不適合大數(shù)據(jù)集計(jì)算DIANA算法

DIANA（Divisive Analysis）算法屬于分裂的層次聚類，首先將所有的對(duì)象初始化到一個(gè)簇中，然后根據(jù)一些原則（比如最鄰近的最大歐式距離），將該簇分類。直到到達(dá)用戶指定的簇?cái)?shù)目或者兩個(gè)簇之間的距離超過了某個(gè)閾值。

DIANA用到如下兩個(gè)定義：

（1） 簇的直徑：在一個(gè)簇中的任意兩個(gè)數(shù)據(jù)點(diǎn)都有一個(gè)歐氏距離，這些距離中的最大值是簇的直徑

（2） 平均相異度（平均距離）：

算法描述：

輸入：包含n個(gè)對(duì)象的數(shù)據(jù)庫，終止條件簇的數(shù)目k

輸出：k個(gè)簇，達(dá)到終止條件規(guī)定簇?cái)?shù)目

（1） 將所有對(duì)象整個(gè)當(dāng)成一個(gè)初始簇

（2） For ( i=1;i!=k;i++) Do Begin

（3） 在所有簇中挑選出具有最大直徑的簇；

（4） 找出所挑出簇里與其他點(diǎn)平均相異度最大的一個(gè)點(diǎn)放入splinter group，剩余的放入old party中。

（5） Repeat

（6） 在old party里找出到splinter group中點(diǎn)的最近距離不大于old party中點(diǎn)的最近距離的點(diǎn)，并將該點(diǎn)加入splinter group

（7） Until 沒有新的old party的點(diǎn)被分配給splinter group；

（8） Splinter group 和old party為被選中的簇分裂成的兩個(gè)簇，與其他簇一起組成新的簇集合

（9） END

算法性能：

缺點(diǎn)是已做的分裂操作不能撤銷，類之間不能交換對(duì)象。如果在某步?jīng)]有選擇好分裂點(diǎn)，可能會(huì)導(dǎo)致低質(zhì)量的聚類結(jié)果。大數(shù)據(jù)集不太適用。

其他算法

層次聚類方法比較簡單，但是經(jīng)常遇到的一個(gè)問題，就是在合并或分裂點(diǎn)選擇困難的問題。一個(gè)有希望的改進(jìn)方向是將層級(jí)聚類和其他聚類技術(shù)進(jìn)行集成，形成多階段聚類。

（1） BIRCH算法

BIRCH（利用層次方法的平衡迭代規(guī)約和聚類）是一個(gè)總和的層次聚類方法，

（2） CURE算法

密度聚類方法

基本思想：只要一個(gè)區(qū)域的點(diǎn)的密度大于某個(gè)閾值，就把它加到預(yù)置最近的聚類中區(qū)。密度聚類可以發(fā)現(xiàn)任意形狀的聚類，且對(duì)噪聲數(shù)據(jù)不敏感。但是計(jì)算復(fù)雜度大，且對(duì)數(shù)據(jù)維數(shù)的伸縮性較差。需要掃描整個(gè)數(shù)據(jù)庫，每個(gè)數(shù)據(jù)對(duì)象都可能引起一次查詢，因此當(dāng)數(shù)據(jù)量大時(shí)會(huì)造成頻繁的I/O操作。

DBSCAN算法

DBSCAN（Density-Based Spatial Clustering of Applications with Noise）算法將簇定義為密度相連的點(diǎn)的最大集合，能夠把具有足夠高密度的區(qū)域戶分成簇，并且可以在有“噪聲”的空間數(shù)據(jù)庫中發(fā)現(xiàn)任意形狀的聚類。

基本定義：

（1） 對(duì)象的 -臨域：給定對(duì)象的半徑 內(nèi)的區(qū)域。

（2） 核心對(duì)象：如果一個(gè)對(duì)象的 -臨域至關(guān)于 少包含最小數(shù)目MinPts個(gè)對(duì)象，則成該對(duì)象為核心對(duì)象。

（3） 直接密度可達(dá)：給定一個(gè)對(duì)象集合D，如果p是在q的 -臨域內(nèi)，而且q是一個(gè)核心對(duì)象，我們就說對(duì)象p從對(duì)象q出發(fā)是直接密度可達(dá)的。

（4） 密度可達(dá)：如果存在一個(gè)對(duì)象鏈p1, p2,…,pn, p1=q， pn=p，對(duì)于任意的pi屬于D，pi+1是從pi關(guān)于 和MinPts直接密度可達(dá)的，則對(duì)象p是從對(duì)象q關(guān)于 和MinPts密度可達(dá)的。

（5） 密度相連的：如果對(duì)象集合D中存在一個(gè)對(duì)象o，使得對(duì)象p和q是從o關(guān)于 和MinPits密度可達(dá)的，那么對(duì)象p和q是關(guān)于 和MinPts可達(dá)的。

（6） 噪聲：一個(gè)基于密度的簇是基于密度可達(dá)性的最大的密度相連對(duì)象的集合。不包含在任何簇中的對(duì)象被認(rèn)為是“噪聲”。

算法描述：

輸入：包含n個(gè)對(duì)象的數(shù)據(jù)庫，半徑 ，最少數(shù)目MinPts

輸出：所有生成的簇，到達(dá)密度要求

(1) repeat

(2) 從數(shù)據(jù)庫中抽取出一個(gè)未處理過的點(diǎn)

(3) If 抽出的點(diǎn)是核心點(diǎn) then 找出所有從改密度可達(dá)的對(duì)象，形成一個(gè)簇

(4) Else 抽出的點(diǎn)是邊緣點(diǎn)（非核心對(duì)象），跳出本次循環(huán)，尋找下一個(gè)點(diǎn)

(5) Until 所有點(diǎn)都被處理

算法性能：

可以發(fā)現(xiàn)任意形狀的簇，但是該算法對(duì)用戶定義的參數(shù)是敏感的，為了解決這個(gè)問題，OPTICS(ordering points to identify the clustering structure)被提出，通過引入核心距離和可達(dá)距離，使得聚類算法對(duì)輸入的參數(shù)不敏感。