《電子技術(shù)應(yīng)用》
您所在的位置：首頁(yè) > 人工智能 > 設(shè)計(jì)應(yīng)用 > 基于交點(diǎn)的新層次聚類算法
基于交點(diǎn)的新層次聚類算法
2020年信息技術(shù)與網(wǎng)絡(luò)安全第10期
李青旭，陳天鷹,，胡 波
華北計(jì)算機(jī)系統(tǒng)工程研究所，北京100083
摘要： 介紹了一種新的分層聚類算法,，該聚類算法的主要目的是利用交點(diǎn)提供更好的聚類質(zhì)量和更高的準(zhǔn)確性。為了驗(yàn)證該聚類算法,，對(duì)基準(zhǔn)數(shù)據(jù)集進(jìn)行了幾次實(shí)驗(yàn),，并與其他五種廣泛使用的聚類算法進(jìn)行對(duì)比。使用純度作為外部標(biāo)準(zhǔn)來(lái)評(píng)估聚類算法的性能，并計(jì)算了由聚類算法得出的每個(gè)聚類的緊密度,，以評(píng)估聚類算法的有效性,。實(shí)驗(yàn)結(jié)果表明，在大多數(shù)情況下,，該算法的錯(cuò)誤率低于研究中使用的其他聚類算法,。
中圖分類號(hào)： TP393
文獻(xiàn)標(biāo)識(shí)碼： A
DOI： 10.19358/j.issn.2096-5133.2020.10.004
引用格式： 李青旭，陳天鷹,，胡波. 基于交點(diǎn)的新層次聚類算法[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ù)量每天都在增加,，因此能夠檢測(cè)數(shù)據(jù)結(jié)構(gòu)并識(shí)別數(shù)據(jù)集中的子集的方法變得越來(lái)越重要,。聚類是這些方法中的一種。聚類或聚類分析是一項(xiàng)無(wú)監(jiān)督的歸納學(xué)習(xí)任務(wù),，它基于各個(gè)點(diǎn)之間的相似性將數(shù)據(jù)組織到同質(zhì)的組中,。聚類是機(jī)器學(xué)習(xí)，是數(shù)據(jù)挖掘和統(tǒng)計(jì)中已研究的基本問(wèn)題之一[1-3],。聚類方法可以產(chǎn)生與分類方法相同的結(jié)果,，但是不存在預(yù)定義的類，因此也可以視為無(wú)監(jiān)督分類[4-5],。

    聚類算法的性能可以通過(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ù)聚類算法的規(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ā)出多種不同的聚類方法。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],。層次聚類分為聚集和分裂兩種類型。聚集方法具有自下而上的過(guò)程,，首先將每個(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ū)域隔開(kāi),。ESTER M等人1996年提出的空間聚類是基于密度的方法的一個(gè)示例,，只要鄰域中的密度超過(guò)某個(gè)閾值，該方法就會(huì)不斷地增長(zhǎng)聚類效果[11],?；诰W(wǎng)格的方法將數(shù)據(jù)空間量化為有限數(shù)量的單元，這些單元形成一個(gè)網(wǎng)格結(jié)構(gòu),，在該網(wǎng)格結(jié)構(gòu)上執(zhí)行所有用于聚類的操作,，它與數(shù)據(jù)點(diǎn)無(wú)關(guān),，但與圍繞數(shù)據(jù)點(diǎn)的值空間有關(guān)?；诮y(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)證措施來(lái)證明提出算法的強(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é)果,。




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




作者信息:

李青旭，陳天鷹,，胡  波

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

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