0 引言

    由于處理的數(shù)據(jù)量每天都在增加，因此能夠檢測(cè)數(shù)據(jù)結(jié)構(gòu)并識(shí)別數(shù)據(jù)集中的子集的方法變得越來(lái)越重要。聚類(lèi)是這些方法中的一種。聚類(lèi)或聚類(lèi)分析是一項(xiàng)無(wú)監(jiān)督的歸納學(xué)習(xí)任務(wù)，它基于各個(gè)點(diǎn)之間的相似性將數(shù)據(jù)組織到同質(zhì)的組中。聚類(lèi)是機(jī)器學(xué)習(xí)，是數(shù)據(jù)挖掘和統(tǒng)計(jì)中已研究的基本問(wèn)題之一^[1-3]。聚類(lèi)方法可以產(chǎn)生與分類(lèi)方法相同的結(jié)果，但是不存在預(yù)定義的類(lèi)，因此也可以視為無(wú)監(jiān)督分類(lèi)^[4-5]。

    聚類(lèi)算法的性能可以通過(guò)其發(fā)現(xiàn)數(shù)據(jù)集中某些或所有隱藏模式的能力來(lái)衡量，可以通過(guò)測(cè)量數(shù)據(jù)點(diǎn)之間的相似性(不相似性)來(lái)發(fā)現(xiàn)隱藏的模式。相似度表示在明確定義的意義上測(cè)得的數(shù)學(xué)相似度，通常使用距離函數(shù)進(jìn)行定義，根據(jù)聚類(lèi)算法的規(guī)則，可以測(cè)量數(shù)據(jù)點(diǎn)本身之間或數(shù)據(jù)點(diǎn)與某個(gè)特殊點(diǎn)之間的距離。同時(shí)，隨著數(shù)據(jù)的劃分，同一群集中的數(shù)據(jù)點(diǎn)應(yīng)盡可能相似，而不同群集中的數(shù)據(jù)點(diǎn)應(yīng)盡可能不相似^[6-7]。多年來(lái)，已經(jīng)開(kāi)發(fā)出多種不同的聚類(lèi)方法。1998年，F(xiàn)raley C和RAFTERY A E將聚類(lèi)算法分為層次結(jié)構(gòu)和分區(qū)兩組。Han和Kamber在2006年將聚類(lèi)算法分為5類(lèi)：分層、分區(qū)、基于密度、基于網(wǎng)格和基于模型^[8]。

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

    在基于密度的方法中，簇是數(shù)據(jù)空間中最密集的區(qū)域，被較低密度的區(qū)域隔開(kāi)。ESTER M等人1996年提出的空間聚類(lèi)是基于密度的方法的一個(gè)示例，只要鄰域中的密度超過(guò)某個(gè)閾值，該方法就會(huì)不斷地增長(zhǎng)聚類(lèi)效果^[11]。基于網(wǎng)格的方法將數(shù)據(jù)空間量化為有限數(shù)量的單元，這些單元形成一個(gè)網(wǎng)格結(jié)構(gòu)，在該網(wǎng)格結(jié)構(gòu)上執(zhí)行所有用于聚類(lèi)的操作，它與數(shù)據(jù)點(diǎn)無(wú)關(guān)，但與圍繞數(shù)據(jù)點(diǎn)的值空間有關(guān)。基于統(tǒng)計(jì)信息網(wǎng)格是WANG W等人1997年提出的基于網(wǎng)格的方法對(duì)空間數(shù)據(jù)集進(jìn)行聚類(lèi)的典型示例，在這種方法中，將空間區(qū)域劃分為由分層結(jié)構(gòu)表示的矩形單元^[12]。基于模型的聚類(lèi)方法假定數(shù)據(jù)是由模型生成的，并嘗試從數(shù)據(jù)中發(fā)現(xiàn)原始模型，統(tǒng)計(jì)方法和神經(jīng)網(wǎng)絡(luò)方法是基于模型的兩種主要方法^[13]。

    本文的目的是在分層聚類(lèi)的基礎(chǔ)上優(yōu)化分層算法，并使用更多的驗(yàn)證措施來(lái)證明提出算法的強(qiáng)度。該算法使用交點(diǎn)作為鏈接標(biāo)準(zhǔn)，以合理的計(jì)算復(fù)雜度提供更有效、更準(zhǔn)確的聚類(lèi)結(jié)果。該算法的第一步是為每個(gè)數(shù)據(jù)點(diǎn)找出最接近的鄰居(NN)，以形成對(duì)，然后找出對(duì)之間的交點(diǎn)以形成主聚類(lèi)。本文以二維示例介紹了新的層次聚類(lèi)算法，解釋了聚類(lèi)評(píng)估，并介紹了新層次聚類(lèi)算法與某些現(xiàn)有聚類(lèi)算法進(jìn)行比較的實(shí)驗(yàn)結(jié)果。

本文詳細(xì)內(nèi)容請(qǐng)下載:http://www.jysgc.com/resource/share/2000003131

作者信息:

李青旭，陳天鷹，胡  波

(華北計(jì)算機(jī)系統(tǒng)工程研究所，北京100083)