0 引言

    由于處理的數據量每天都在增加，因此能夠檢測數據結構并識別數據集中的子集的方法變得越來越重要。聚類是這些方法中的一種。聚類或聚類分析是一項無監督的歸納學習任務，它基于各個點之間的相似性將數據組織到同質的組中。聚類是機器學習，是數據挖掘和統計中已研究的基本問題之一^[1-3]。聚類方法可以產生與分類方法相同的結果，但是不存在預定義的類，因此也可以視為無監督分類^[4-5]。

    聚類算法的性能可以通過其發現數據集中某些或所有隱藏模式的能力來衡量，可以通過測量數據點之間的相似性(不相似性)來發現隱藏的模式。相似度表示在明確定義的意義上測得的數學相似度，通常使用距離函數進行定義，根據聚類算法的規則，可以測量數據點本身之間或數據點與某個特殊點之間的距離。同時，隨著數據的劃分，同一群集中的數據點應盡可能相似，而不同群集中的數據點應盡可能不相似^[6-7]。多年來，已經開發出多種不同的聚類方法。1998年，Fraley C和RAFTERY A E將聚類算法分為層次結構和分區兩組。Han和Kamber在2006年將聚類算法分為5類：分層、分區、基于密度、基于網格和基于模型^[8]。

    JOHNSON S定義的分層方法將點安排到一個基礎層次結構中，該層次結構隨后確定各種聚類^[9]。層次聚類分為聚集和分裂兩種類型。聚集方法具有自下而上的過程，首先將每個數據點放置在其自己的聚類中，然后將聚類連續合并為更大的聚類，或者直到滿足給定的終止條件(例如特定數量的聚類)為止。分裂方法與聚集法相反，并且以自頂向下的方式執行。分區方法將數據集劃分為K個分區，每個分區代表一個聚類，它有兩種類型的分區，即清晰分區和模糊分區。如果數據集的每個數據點僅屬于一個簇，則稱為“清晰”，但如果允許數據點成為多個具有不同程度的簇的成員，則稱為“模糊”^[10]。K-means和K-mediods方法是兩種常用的聚類方法。在K-means算法中，每個聚類由數據點的平均值表示，而在K-mediods中，一個聚類由聚類中位于最中心的數據點表示。

    在基于密度的方法中，簇是數據空間中最密集的區域，被較低密度的區域隔開。ESTER M等人1996年提出的空間聚類是基于密度的方法的一個示例，只要鄰域中的密度超過某個閾值，該方法就會不斷地增長聚類效果^[11]。基于網格的方法將數據空間量化為有限數量的單元，這些單元形成一個網格結構，在該網格結構上執行所有用于聚類的操作，它與數據點無關，但與圍繞數據點的值空間有關。基于統計信息網格是WANG W等人1997年提出的基于網格的方法對空間數據集進行聚類的典型示例，在這種方法中，將空間區域劃分為由分層結構表示的矩形單元^[12]?；谀Ｐ偷木垲惙椒俣〝祿怯赡Ｐ蜕傻?，并嘗試從數據中發現原始模型，統計方法和神經網絡方法是基于模型的兩種主要方法^[13]。

    本文的目的是在分層聚類的基礎上優化分層算法，并使用更多的驗證措施來證明提出算法的強度。該算法使用交點作為鏈接標準，以合理的計算復雜度提供更有效、更準確的聚類結果。該算法的第一步是為每個數據點找出最接近的鄰居(NN)，以形成對，然后找出對之間的交點以形成主聚類。本文以二維示例介紹了新的層次聚類算法，解釋了聚類評估，并介紹了新層次聚類算法與某些現有聚類算法進行比較的實驗結果。

本文詳細內容請下載:http://www.cowatch.cn/resource/share/2000003131

作者信息:

李青旭，陳天鷹，胡  波

(華北計算機系統工程研究所，北京100083)