《電子技術(shù)應用》
您所在的位置：首頁 > 人工智能 > 設(shè)計應用 > 基于交點的新層次聚類算法
基于交點的新層次聚類算法
2020年信息技術(shù)與網(wǎng)絡(luò)安全第10期
李青旭，陳天鷹，胡 波
華北計算機系統(tǒng)工程研究所，北京100083
摘要： 介紹了一種新的分層聚類算法，該聚類算法的主要目的是利用交點提供更好的聚類質(zhì)量和更高的準確性。為了驗證該聚類算法，對基準數(shù)據(jù)集進行了幾次實驗，并與其他五種廣泛使用的聚類算法進行對比。使用純度作為外部標準來評估聚類算法的性能，并計算了由聚類算法得出的每個聚類的緊密度，以評估聚類算法的有效性。實驗結(jié)果表明，在大多數(shù)情況下，該算法的錯誤率低于研究中使用的其他聚類算法。
中圖分類號： TP393
文獻標識碼： A
DOI： 10.19358/j.issn.2096-5133.2020.10.004
引用格式： 李青旭，陳天鷹，胡波. 基于交點的新層次聚類算法[J].信息技術(shù)與網(wǎng)絡(luò)安全，2020，39(10)：18-22.
New hierarchical clustering algorithm based on intersection
Li Qingxu，Chen Tianying，Hu Bo
National Computer System Engineering Research Institute of China，Beijing 100083，China
Abstract： This paper introduces a new hierarchical clustering algorithm. The main purpose of this clustering algorithm is to provide better clustering quality and higher accuracy by using intersections. In order to verify this clustering algorithm, we conducted several experiments on the benchmark data set. In addition to the algorithm we proposed, five well-known clustering algorithms were also used. The purity was used as an external standard to evaluate the performance of the clustering algorithm, and the tightness of each cluster obtained by the clustering algorithm was also calculated to evaluate the effectiveness of the clustering algorithm. Finally, the experimental results show that in most cases, the error rate of the proposed algorithm is lower than other clustering algorithms used in this study.
Key words : data mining；unsupervised learning；cluster analysis；clustering algorithm；hierarchical clustering

0 引言

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

    聚類算法的性能可以通過其發(fā)現(xiàn)數(shù)據(jù)集中某些或所有隱藏模式的能力來衡量，可以通過測量數(shù)據(jù)點之間的相似性(不相似性)來發(fā)現(xiàn)隱藏的模式。相似度表示在明確定義的意義上測得的數(shù)學相似度，通常使用距離函數(shù)進行定義，根據(jù)聚類算法的規(guī)則，可以測量數(shù)據(jù)點本身之間或數(shù)據(jù)點與某個特殊點之間的距離。同時，隨著數(shù)據(jù)的劃分，同一群集中的數(shù)據(jù)點應盡可能相似，而不同群集中的數(shù)據(jù)點應盡可能不相似[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定義的分層方法將點安排到一個基礎(chǔ)層次結(jié)構(gòu)中，該層次結(jié)構(gòu)隨后確定各種聚類[9]。層次聚類分為聚集和分裂兩種類型。聚集方法具有自下而上的過程，首先將每個數(shù)據(jù)點放置在其自己的聚類中，然后將聚類連續(xù)合并為更大的聚類，或者直到滿足給定的終止條件(例如特定數(shù)量的聚類)為止。分裂方法與聚集法相反，并且以自頂向下的方式執(zhí)行。分區(qū)方法將數(shù)據(jù)集劃分為K個分區(qū)，每個分區(qū)代表一個聚類，它有兩種類型的分區(qū)，即清晰分區(qū)和模糊分區(qū)。如果數(shù)據(jù)集的每個數(shù)據(jù)點僅屬于一個簇，則稱為“清晰”，但如果允許數(shù)據(jù)點成為多個具有不同程度的簇的成員，則稱為“模糊”[10]。K-means和K-mediods方法是兩種常用的聚類方法。在K-means算法中，每個聚類由數(shù)據(jù)點的平均值表示，而在K-mediods中，一個聚類由聚類中位于最中心的數(shù)據(jù)點表示。

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

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




本文詳細內(nèi)容請下載:http://ihrv.cn/resource/share/2000003131




作者信息:

李青旭，陳天鷹，胡  波

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

此內(nèi)容為AET網(wǎng)站原創(chuàng)，未經(jīng)授權(quán)禁止轉(zhuǎn)載。