文獻(xiàn)標(biāo)識碼: A
DOI: 10.19358/j.issn.2096-5133.2020.10.004
引用格式: 李青旭,陳天鷹,胡波. 基于交點的新層次聚類算法[J].信息技術(shù)與網(wǎng)絡(luò)安全,2020,39(10):18-22.
0 引言
由于處理的數(shù)據(jù)量每天都在增加,因此能夠檢測數(shù)據(jù)結(jié)構(gòu)并識別數(shù)據(jù)集中的子集的方法變得越來越重要。聚類是這些方法中的一種。聚類或聚類分析是一項無監(jiān)督的歸納學(xué)習(xí)任務(wù),它基于各個點之間的相似性將數(shù)據(jù)組織到同質(zhì)的組中。聚類是機器學(xué)習(xí),是數(shù)據(jù)挖掘和統(tǒng)計中已研究的基本問題之一[1-3]。聚類方法可以產(chǎn)生與分類方法相同的結(jié)果,但是不存在預(yù)定義的類,因此也可以視為無監(jiān)督分類[4-5]。
聚類算法的性能可以通過其發(fā)現(xiàn)數(shù)據(jù)集中某些或所有隱藏模式的能力來衡量,可以通過測量數(shù)據(jù)點之間的相似性(不相似性)來發(fā)現(xiàn)隱藏的模式。相似度表示在明確定義的意義上測得的數(shù)學(xué)相似度,通常使用距離函數(shù)進行定義,根據(jù)聚類算法的規(guī)則,可以測量數(shù)據(jù)點本身之間或數(shù)據(jù)點與某個特殊點之間的距離。同時,隨著數(shù)據(jù)的劃分,同一群集中的數(shù)據(jù)點應(yīng)盡可能相似,而不同群集中的數(shù)據(jù)點應(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定義的分層方法將點安排到一個基礎(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]?;谀P偷木垲惙椒俣〝?shù)據(jù)是由模型生成的,并嘗試從數(shù)據(jù)中發(fā)現(xiàn)原始模型,統(tǒng)計方法和神經(jīng)網(wǎng)絡(luò)方法是基于模型的兩種主要方法[13]。
本文的目的是在分層聚類的基礎(chǔ)上優(yōu)化分層算法,并使用更多的驗證措施來證明提出算法的強度。該算法使用交點作為鏈接標(biāo)準(zhǔn),以合理的計算復(fù)雜度提供更有效、更準(zhǔn)確的聚類結(jié)果。該算法的第一步是為每個數(shù)據(jù)點找出最接近的鄰居(NN),以形成對,然后找出對之間的交點以形成主聚類。本文以二維示例介紹了新的層次聚類算法,解釋了聚類評估,并介紹了新層次聚類算法與某些現(xiàn)有聚類算法進行比較的實驗結(jié)果。
本文詳細(xì)內(nèi)容請下載:http://ihrv.cn/resource/share/2000003131
作者信息:
李青旭,陳天鷹,胡 波
(華北計算機系統(tǒng)工程研究所,北京100083)