基于交點(diǎn)的新層次聚類算法

李青旭，陳天鷹，胡 波

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

0 引言

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

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

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

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

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

1 新的聚類算法

與在各領(lǐng)域中使用的其他自下而上的層次聚類方法相比，本文提出的聚類算法的目的是提供具有相同計(jì)算復(fù)雜度O(n2)的、更準(zhǔn)確和更有效的聚類，該算法利用神經(jīng)網(wǎng)絡(luò)和交叉點(diǎn)的優(yōu)勢(shì)進(jìn)行分層聚類。 交集是此算法中使用的基本概念。 新算法的步驟如下：

(1)找到每個(gè)數(shù)據(jù)點(diǎn)的 NN 并將它們配對(duì)，因此，對(duì)于n 個(gè)數(shù)據(jù)點(diǎn)，將有 n 對(duì)配對(duì)(其中一些會(huì)重復(fù))。歐幾里德距離公式(1)將用于測(cè)量數(shù)據(jù)點(diǎn)之間的距離(相似度)以形成 n×n 的距離矩陣，然后每個(gè)數(shù)據(jù)點(diǎn)將與其 NN 成對(duì)， 數(shù)據(jù)點(diǎn) IoP 的索引及其 NN IoNN 將用于配對(duì)。

其中，min 代表數(shù)據(jù)點(diǎn)的所有鄰居，IoP1是第一個(gè)數(shù)據(jù)點(diǎn)的索引，IoNN1是第一個(gè)數(shù)據(jù)點(diǎn)的NN 的索引。

(2)將每對(duì)視為包含一個(gè)數(shù)據(jù)點(diǎn)的索引和其NN的索引的集合，找到點(diǎn)對(duì)之間的交點(diǎn)并將其連接起來。 通過找到集合之間的交點(diǎn)，在每一步都可以將所有最接近的數(shù)據(jù)點(diǎn)放置在同一簇中。

假設(shè)有5 個(gè)數(shù)據(jù)點(diǎn)，并且在上一步中已經(jīng)為每個(gè)數(shù)據(jù)點(diǎn)找到了 NN。 Pairs={(1，2)(2，3)(3，2)(4，5)(5，4)}。第一對(duì)(1，2)顯示第二個(gè)數(shù)據(jù)點(diǎn)是第一個(gè)數(shù)據(jù)點(diǎn)的 NN。 請(qǐng)注意，應(yīng)刪除或忽略諸如(3，2)之類的重復(fù)對(duì)。

為了找到線對(duì)之間的交點(diǎn)，每次考慮兩對(duì)點(diǎn)對(duì)，例如對(duì)于前兩對(duì) (IoP1，IoNN1)和 (IoP2，IoNN2)交 點(diǎn) 是(1，2)∩(2，3)=(2)，可以通過以下計(jì)算得出：

第一對(duì)=(IoP1，IoNN1)=(1，2)

第二對(duì)=(IoP2，IoNN2)=(2，3)

交點(diǎn)=(IoP1，IoP2)=(1-2)=-1

(IoP1-IoNN2)=(1-3)=-2

(IoNN1-IoNN2)=(2-3)=-1

(IoNN1-IoP2)=(2-2)=0

(IoNN1-IoP2)=(2-2)=0 表示 2 是第一和第二對(duì)之間的交點(diǎn)，通過考慮點(diǎn)對(duì)1 與其他點(diǎn)對(duì)，可以找到所有具有交點(diǎn)的點(diǎn)對(duì)并將它們連接起來以構(gòu)成一個(gè)聚類。

(3)計(jì)算上一步得出的每個(gè)聚類的平均值(中心)。

(4)連續(xù)對(duì)平均值重復(fù)步驟(1)和(2)，以達(dá)到所需的簇?cái)?shù)。 這意味著需要找到主要聚類的每個(gè)平均值的NN，然后制作成點(diǎn)對(duì)的平均值，再在下文中尋找成對(duì)的平均值之間的交點(diǎn)以形成聚類。 重復(fù)此過程以獲得所需的簇?cái)?shù)，或者直到所有數(shù)據(jù)點(diǎn)都在一個(gè)簇中。 該算法的流程圖如圖1 所示。

假設(shè)有一個(gè)二維數(shù)據(jù)集，如圖2 所示。 圖2 中的(a)部分顯示每個(gè)數(shù)據(jù)點(diǎn)都與它的最近鄰居配對(duì)，并且其中一些對(duì)于一個(gè)以上的數(shù)據(jù)點(diǎn)是最近鄰居，這些交點(diǎn)用白色圓圈表示。 在(b)部分中，將具有交點(diǎn)的那些對(duì)合并，并使其成為主要簇，計(jì)算每個(gè)主要簇的平均值。 隨后，求平均值和最接近均值來加入最接近的類集。 重復(fù)此過程以達(dá)到所需的簇?cái)?shù)，或者直到所有數(shù)據(jù)點(diǎn)都在一個(gè)簇中。 圖3 和圖4 分別顯示了新算法和現(xiàn)有算法的步驟。

圖1 具有交點(diǎn)的新聚類算法流程圖

圖2 使用新的聚類算法進(jìn)行數(shù)據(jù)聚類的圖示(◆為平均值)

圖3 新算法的聚類步驟

2 聚類評(píng)估

在對(duì)數(shù)據(jù)進(jìn)行聚類之后，用戶希望檢查聚類結(jié)構(gòu)的有效性。 聚類評(píng)估或聚類有效性檢驗(yàn)是一項(xiàng)必要但具有挑戰(zhàn)性的任務(wù)，已成為聚類分析中的核心任務(wù)。通常，驗(yàn)證措施分為內(nèi)部和外部標(biāo)準(zhǔn)，內(nèi)部標(biāo)準(zhǔn)基于數(shù)據(jù)的固有信息并分析聚類結(jié)構(gòu)的優(yōu)劣，而外部標(biāo)準(zhǔn)則基于有關(guān)數(shù)據(jù)的先前知識(shí)并分析聚類

圖4 現(xiàn)有聚類算法聚類的步驟

與參考的標(biāo)準(zhǔn)。 例如預(yù)定義的類標(biāo)簽[14]、邊緣相關(guān)性、結(jié)構(gòu)分析、鄧恩指數(shù)和預(yù)期密度是內(nèi)部標(biāo)準(zhǔn)的一些示例；蘭德指數(shù)、歸一化的互信息、F 度量和純度是聚類質(zhì)量的外部標(biāo)準(zhǔn)的一些示例。 內(nèi)部聚類評(píng)估措施經(jīng)常對(duì)聚類結(jié)構(gòu)的形成做出潛在假設(shè)，并且通常具有很高的計(jì)算復(fù)雜性。 因此，當(dāng)研究目的僅是評(píng)估聚類算法和可用的類別標(biāo)簽時(shí)，研究人員傾向于使用外部標(biāo)準(zhǔn)。 由于本研究的目的是介紹和評(píng)估一種新的聚類算法，并且類別標(biāo)簽也可用于本文的數(shù)據(jù)集，因此本研究使用外部標(biāo)準(zhǔn)。 純度是一種流行的外部標(biāo)準(zhǔn)，本文使用純度來評(píng)估本研究中使用的聚類算法。 要計(jì)算純度，應(yīng)將每個(gè)簇分配給該簇中重復(fù)次數(shù)最多的類別，接下來，將通過對(duì)正確分配的數(shù)據(jù)點(diǎn)數(shù)除以總數(shù)據(jù)點(diǎn)數(shù)[15-16]來測(cè)量此分配的準(zhǔn)確性。

3 實(shí)驗(yàn)

為了驗(yàn)證新的層次聚類算法，將其應(yīng)用于三個(gè)數(shù)據(jù)集[17]，數(shù)據(jù)集的詳細(xì)信息如表1 所示。 所有提到的數(shù)據(jù)集都有預(yù)定義的標(biāo)簽，在不使用其類標(biāo)簽的情況下使用它們來形成聚類。將分層、分區(qū)、基于密度、基于網(wǎng)絡(luò)和基于模型的層次聚類用于數(shù)據(jù)聚類，并將其結(jié)果與新聚類算法的結(jié)果進(jìn)行比較。 如前所述，在這些實(shí)驗(yàn)中，所有數(shù)據(jù)集都預(yù)定義了標(biāo)簽， 因此可以使用它們來計(jì)算聚類算法的純度，并根據(jù)其準(zhǔn)確性對(duì)結(jié)果進(jìn)行排名。 聚類方法的準(zhǔn)確性如圖5 所示，毫無疑問，聚類結(jié)果總是需要最低的聚類間距和最高的聚類相似度。 換句話說，每個(gè)聚類的成員應(yīng)盡可能地彼此靠近，這被定義為緊密度，而方差是緊密度的常用度量，因此，本文還計(jì)算了數(shù)據(jù)集的每個(gè)聚類中的屬性值之間的方差。通過比較每個(gè)聚類的方差值，可以測(cè)量每個(gè)聚類算法如何在一個(gè)聚類中設(shè)置相似的數(shù)據(jù)點(diǎn)。 除了純度之外，方差分析還可以幫助評(píng)估聚類的準(zhǔn)確性。 肝病數(shù)據(jù)集、甲狀腺病數(shù)據(jù)集和糖尿病數(shù)據(jù)集的方差值如圖6～圖8 所示。

表1 數(shù)據(jù)集特征

圖5 聚類方法的準(zhǔn)確性

圖6 肝病數(shù)據(jù)集方差(1 為預(yù)定義標(biāo)簽)

圖7 甲狀腺病數(shù)據(jù)集方差(1 為預(yù)定義標(biāo)簽)

圖8 糖尿病數(shù)據(jù)集方差(1 為預(yù)定義標(biāo)簽)

圖5 介紹了應(yīng)用于基準(zhǔn)數(shù)據(jù)集的六種聚類算法的準(zhǔn)確性，在肝病數(shù)據(jù)集(柱狀圖1)和甲狀腺數(shù)據(jù)集(柱狀圖3)中，新的層次聚類算法的準(zhǔn)確性高于其他聚類算法。 圖6～圖8 介紹了每種聚類算法提供的總方差值，那些具有零密度簇的算法的總值以斜體的形式標(biāo)注，它們不參與排名。 較小的總方差值表示較高的聚類相似度，這是聚類算法所需的。對(duì)于肝病數(shù)據(jù)集，新算法相似度較高，對(duì)于甲狀腺病數(shù)據(jù)集，分區(qū)聚類和新算法方差較小。 對(duì)于糖尿病數(shù)據(jù)集，模型聚類和新聚類算法提供的方差小于其他。 由以上實(shí)驗(yàn)結(jié)果可以看出，在本研究中使用的所有聚類算法中，本文提出的算法在準(zhǔn)確率方面始終位于前 2 位。

4 結(jié)論

本文提出了一種新的基于交點(diǎn)的層次聚類算法，并進(jìn)行了一些基準(zhǔn)數(shù)據(jù)集實(shí)驗(yàn)，以驗(yàn)證提出算法的有效性。 實(shí)驗(yàn)中還使用了其他五種層次聚類算法，使用純度作為外部標(biāo)準(zhǔn)來評(píng)估所有聚類算法的聚類結(jié)果。 計(jì)算每個(gè)聚類的屬性方差值，并將其用于評(píng)估聚類質(zhì)量。實(shí)驗(yàn)結(jié)果表明，在大多數(shù)情況下，無論數(shù)據(jù)點(diǎn)的大小和數(shù)量如何，具有計(jì)算復(fù)雜度為O(n2)的基于交叉點(diǎn)的新層次聚類算法都可以提供良好的結(jié)果，并且錯(cuò)誤率較低。 而具有相同計(jì)算復(fù)雜度的其他聚類算法僅在少數(shù)情況下才能很好地執(zhí)行。