其他算法

1. CLARA（Cluster Larger Application）是基于k-中心點(diǎn)類型的算法，能處理更大的數(shù)據(jù)集合。CLARA先抽取數(shù)據(jù)集合的多個樣本，然后用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ī)性地選取一個樣本。

層次聚類方法

層次聚類分為兩種：

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

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

AGNES算法

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

算法描述：

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

輸出：k個簇

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

（2） Repeat

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

（4） 合并兩個簇，生成新的簇的集合

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

算法性能：

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

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

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

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

DIANA用到如下兩個定義：

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

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

算法描述：

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

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

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

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

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

（4） 找出所挑出簇里與其他點(diǎn)平均相異度最大的一個點(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為被選中的簇分裂成的兩個簇，與其他簇一起組成新的簇集合

（9） END

算法性能：

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

其他算法

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

（1） BIRCH算法

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

（2） CURE算法

密度聚類方法

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

DBSCAN算法

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

基本定義：

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

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

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

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

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

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

算法描述：

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

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

(1) repeat

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

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

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

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

算法性能：

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