BRINK：基于局部質(zhì)變因子的聚類邊界檢測(cè)算法

邱保志，楊 洋，杜效偉

(1.鄭州大學(xué) 信息工程學(xué)院，河南 鄭州450001;2.漯河職業(yè)技術(shù)學(xué)院，河南 漯河462000)

0 引言

聚類的邊界檢測(cè)是數(shù)據(jù)挖掘新興的研究領(lǐng)域之一，聚類的邊界點(diǎn)是位于高密聚類邊沿，它們通常具有2個(gè)或2個(gè)以上聚類的特征，其歸屬并不明確［1］，有效的提取聚類邊界不但可以提高聚類的精度，還可以研究聚類邊緣的特性，因此聚類的邊界點(diǎn)具有很重要的研究?jī)r(jià)值和廣泛的應(yīng)用價(jià)值.目前對(duì)聚類邊界的研究才剛剛起步，聚類邊界檢測(cè)的算法還不是很多.

CHEN Yi-xia等基于聚類邊界點(diǎn)的反向k近鄰值小于聚類內(nèi)部點(diǎn)的反向k近鄰值這一事實(shí)提出了聚類邊界檢測(cè)算法Border［1］，對(duì)不含噪聲的數(shù)據(jù)集，Border能有效地識(shí)別聚類的邊界，然而對(duì)含有噪聲的數(shù)據(jù)集和多密度數(shù)據(jù)集來說Border都不能正確識(shí)別聚類的邊界.BRIM［2］邊界點(diǎn)檢測(cè)算法利用邊界點(diǎn)的正向半鄰域內(nèi)分布著較多的點(diǎn)，負(fù)向半鄰域內(nèi)分布著較少的點(diǎn)這一特征標(biāo)記邊界點(diǎn)，解決了BORDER不能有效識(shí)別噪聲點(diǎn)和聚類邊界點(diǎn)的問題，但該算法參數(shù)選擇困難且不能用于高維數(shù)據(jù).Band［3］算法根據(jù)聚類的邊界點(diǎn)具有一個(gè)較大的變異系數(shù)這一原理識(shí)別邊界，它能夠有效地識(shí)別含有噪聲的多密度聚類的邊界，但不能用于高維數(shù)據(jù)聚類邊界的識(shí)別.

為了能有效地檢測(cè)聚類的邊界，筆者利用局部質(zhì)變因子特性提取邊界和去除噪聲，利用加權(quán)的歐式距離使算法適用于高維數(shù)據(jù)，提出一種基于局部質(zhì)變因子的聚類邊界檢測(cè)算法.

1 BRINK算法

1.1 相關(guān)概念

在高維空間中，基于歐式距離的方法衡量數(shù)據(jù)間的相似度會(huì)導(dǎo)致“差距趨零”現(xiàn)象的發(fā)生，筆者利用加權(quán)的歐式距離［4］來解決這一問題.

定義1(維度的權(quán)重)D是數(shù)據(jù)集，p∈D，表示對(duì)象p在屬性上的ε鄰域，t為權(quán)值，表示對(duì)象p在屬性Ai上的鄰居數(shù)，點(diǎn)p的各維度權(quán)重定義如下

式中：t≥1且t為整數(shù).

定義2 對(duì)象p，q的加權(quán)的歐式距離定義為

其中wi為對(duì)象p在第i個(gè)維度上的權(quán)重，distp(p，q)表示對(duì)象p對(duì)于對(duì)象q的加權(quán)歐式距離.

定義3對(duì)任意的自然數(shù)K，p的K－距離(K-dist(p))為p和某個(gè)對(duì)象o之間的距離，這里的o滿足：

(1)至少存在 K個(gè)對(duì)象 o'∈D{p}，使得d(p，o')≤(p，o)

(2)至多存在K－1個(gè)對(duì)象o'∈D{p}，使得d(p，o')＜ d(p，o).

定義4對(duì)象p的K距離鄰域?yàn)榘信cp的距離不超過K-dist(p)的對(duì)象，即

為了方便，對(duì)象p的K距離鄰域簡(jiǎn)寫為NK(p).

定義5給定自然數(shù)K，對(duì)象p相對(duì)于對(duì)象o的可達(dá)距離為定義6用MinPts表示p的鄰域中最小的對(duì)象個(gè)數(shù)，那么對(duì)象p的局部可達(dá)密度(記為lrd)為對(duì)象p與它的MinPts－距離鄰域的平均可達(dá)距離的倒數(shù)：

定義7點(diǎn)p的局部質(zhì)變因子(LOF)［5］定義為

依據(jù)局部異常因子的定義，局部異常因子具有如下特性：在簇內(nèi)的對(duì)象的LOF值約等于1，在簇邊緣的對(duì)象的LOF值略大于1，而離簇的距離越遠(yuǎn)，對(duì)象的LOF的值越大，并且LOF的值與該對(duì)象附近的其他對(duì)象的分布密度有關(guān)［6］.

定義8邊界點(diǎn)：數(shù)據(jù)集中任意對(duì)象p的局部質(zhì)變因子LOFMinPts(p)滿足：

則稱點(diǎn)p為邊界點(diǎn).根據(jù)定義7的描述，因?yàn)檫吔鐚?duì)象的局部質(zhì)變因子具有稍大于1的特性，所以α取1，β取1.05較為合適.這里 α，β不作為參數(shù).

1.2 BRINK 算法描述

算法的主要思想：首先掃描整個(gè)數(shù)據(jù)集，計(jì)算出數(shù)據(jù)集中的每個(gè)對(duì)象在每一維上的權(quán)重，其次根據(jù)加權(quán)的歐式距離計(jì)算出每個(gè)對(duì)象在數(shù)據(jù)集中的K近鄰和每個(gè)對(duì)象在其鄰域內(nèi)的可達(dá)距離，然后根據(jù)對(duì)象的可達(dá)距離計(jì)算出每個(gè)對(duì)象的局部可達(dá)密度.最后根據(jù)局部可達(dá)密度得出每個(gè)對(duì)象的局部質(zhì)變因子，并依據(jù)每個(gè)對(duì)象的質(zhì)變程度標(biāo)記聚類的邊界，算法描述如下.

輸入：近鄰閾值K，權(quán)值t;

輸出：聚類的邊界對(duì)象;

步驟1：權(quán)重的計(jì)算.掃描整個(gè)數(shù)據(jù)集，計(jì)算每個(gè)對(duì)象在每一維屬性上的權(quán)重，如果該對(duì)象在某一維上具有的鄰居數(shù)大于近鄰閾值K，就賦予其權(quán)值t，否則就賦予其權(quán)值1.

步驟2：K近鄰的計(jì)算.根據(jù)步驟1得出的數(shù)據(jù)集中每個(gè)對(duì)象在每一維上的權(quán)值和公式(2)得出每個(gè)對(duì)象與其他對(duì)象加權(quán)的歐式距離，進(jìn)而得出每個(gè)對(duì)象在數(shù)據(jù)集中的K近鄰.

步驟3：局部可達(dá)密度的計(jì)算.首先根據(jù)公式(4)計(jì)算出數(shù)據(jù)集中每個(gè)對(duì)象在其鄰域范圍內(nèi)的可達(dá)距離，然后利用公式(5)計(jì)算出每個(gè)對(duì)象的局部可達(dá)密度.

步驟4：局部質(zhì)變因子的計(jì)算.根據(jù)步驟3得出的每個(gè)對(duì)象的局部可達(dá)密度，利用公式(6)計(jì)算出數(shù)據(jù)集中每個(gè)對(duì)象的局部質(zhì)變因子.

步驟5：邊界的輸出.把質(zhì)變因子的值在1到1.05的對(duì)象輸出.

2 實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)環(huán)境：CPU為 Intel(R)dual－core 2.60GHz，內(nèi)存為1.99G，操作系統(tǒng)為 Windows XP professional，算法編寫環(huán)境為 VC++6.0.

2.1 實(shí)驗(yàn)結(jié)果

筆者以一個(gè)含有噪聲的均勻分布二維的數(shù)據(jù)集和一個(gè)含有噪聲的二維多密度數(shù)據(jù)集驗(yàn)證算法在低維空間中檢測(cè)邊界的能力和去除噪聲的能力;使用兩個(gè)真實(shí)數(shù)據(jù)集來驗(yàn)證發(fā)現(xiàn)高維聚類邊界的能力.

圖1(a)給出的是含有噪聲的，不同形狀的均勻數(shù)據(jù)集，含有9 993個(gè)數(shù)據(jù)對(duì)象;圖1(b)是Border算法的邊界檢測(cè)結(jié)果(k=25，n=1 200);圖1(c)是Band算法的邊界檢測(cè)的結(jié)果(k=20，w=1.11，BPT=0.26);圖 1(d)是本算法(BRINK)的運(yùn)行結(jié)果，使用的參數(shù)：近鄰閾值K=100，權(quán)重 t=1.

從圖1可以看出，在含有噪聲的均勻數(shù)據(jù)集上，Border算法不能夠區(qū)分邊界點(diǎn)與噪聲點(diǎn)，BRINK與Band兩種算法都能夠很好的區(qū)分邊界點(diǎn)與噪聲點(diǎn)，正確識(shí)別聚類的邊界.

圖2(a)數(shù)據(jù)集含有5 034個(gè)數(shù)據(jù)對(duì)象，含有不同形狀的非均勻聚類且含有噪聲.圖2(b)是Border算法的結(jié)果(k=120，n=1 200);圖2(c)是BRIM算法的結(jié)果(Eps=40，δ=60);圖2(d)是BRINK算法的運(yùn)行結(jié)果，使用的參數(shù)：近鄰閾值 K=20，權(quán)重 t=1.

從圖2可以看出，Border算法在含有噪聲的非均勻數(shù)據(jù)集上不能正確的區(qū)分聚類的邊界點(diǎn)與噪聲點(diǎn)，BRIM算法雖然能夠去除一部分噪聲，但是吸收了靠近聚類邊緣的噪聲點(diǎn).BRINK算法能夠識(shí)別聚類的邊界，但由于本數(shù)據(jù)集的大圓中部分地方的密度過于稀疏，以至于大圓內(nèi)部的有些點(diǎn)被誤認(rèn)為是聚類的邊界.

真實(shí)數(shù)據(jù)集“biomed”(http：//lib.stat.cmu.edu/datasets/)包含207個(gè)數(shù)據(jù)對(duì)象，每個(gè)對(duì)象4個(gè)屬性.該數(shù)據(jù)集分為兩類：病毒感染者(75人)和正常人(134人，其中有30個(gè)病毒攜帶者).這里30個(gè)病毒的攜帶者就是所要找的聚類邊界.表1是BRINK算法在“biomed”上運(yùn)行的結(jié)果，使用的參數(shù)K=20，t=4.表1，2中用準(zhǔn)確率和召回率兩個(gè)指標(biāo)來驗(yàn)證BRINK算法的有效性，這里令A(yù)=實(shí)驗(yàn)結(jié)果中檢索到是邊界對(duì)象，B=實(shí)驗(yàn)結(jié)果中檢索到不是邊界對(duì)象，C=實(shí)驗(yàn)結(jié)果中未檢測(cè)到的邊界對(duì)象，則準(zhǔn)確率=A/(A+B)，召回率=A/(A+C).

從表1中可以看出，實(shí)驗(yàn)結(jié)果得出的36人中既包含了30個(gè)真實(shí)的邊界對(duì)象(病毒攜帶者)，又包含了6個(gè)正常人，這一檢測(cè)結(jié)果對(duì)疾病防控效果沒有負(fù)面影響.

表1 真實(shí)數(shù)據(jù)集“biomed”邊界檢測(cè)結(jié)果Tab.1 Boundary detection results fordata set“Biomed”

Breast Cancer(http：//archive.ics.uci.edu/ml/)數(shù)據(jù)集包含699個(gè)數(shù)據(jù)對(duì)象，每個(gè)對(duì)象有10個(gè)屬性，它含有兩個(gè)聚類：惡性腫瘤患者(241人)和良性腫瘤患者(458人.其中37個(gè)可能發(fā)展成為惡性腫瘤的患者)，從醫(yī)學(xué)意義上看這37人就是聚類的邊界.表2是 BRINK算法在“Breast Cancer”上運(yùn)行的結(jié)果，所使用的參數(shù) K=20，t=5.

表2 真實(shí)數(shù)據(jù)集“Breast Cancer”邊界檢測(cè)結(jié)果Tab.2 Boundary detection results for“Breast Cancer”

從表2可以看出，實(shí)驗(yàn)結(jié)果所得的29人全部包含在真實(shí)的邊界對(duì)象37人當(dāng)中，所以BRINK算法能夠檢測(cè)出高維聚類空間的邊界.

以上4個(gè)實(shí)驗(yàn)結(jié)果表明，BRINK算法不但對(duì)含有噪聲的均勻密度和非均勻密度的數(shù)據(jù)集有較好的效果，而且能用于高維數(shù)據(jù)的聚類邊界檢測(cè).

2.2 算法的時(shí)間復(fù)雜度分析

在本算法中步驟1的時(shí)間復(fù)雜度為O(kn2)，步驟2的時(shí)間復(fù)雜度為O(n)，步驟3的時(shí)間復(fù)雜度為O(n)，所以本算法的時(shí)間復(fù)雜度為O(kn2)，如果使用索引樹結(jié)構(gòu)，算法的時(shí)間復(fù)雜度可以降為O(knlogn).從圖3可以看出本算法(BRINK)在同規(guī)模的數(shù)據(jù)集上運(yùn)行時(shí)間不如BRIM，但優(yōu)于BORDER.

圖3 三種算法運(yùn)行時(shí)間對(duì)比Fig.3 Running time of three algorithms compared

2.3 參數(shù)討論

BRINK算法有兩個(gè)參數(shù)，即近鄰閾值K與權(quán)值的參數(shù)t，一般來說K值的大小會(huì)影響邊界檢測(cè)的結(jié)果與算法的執(zhí)行效率，最近鄰數(shù)一般不宜過大或過小，過大會(huì)影響算法的執(zhí)行效率，過小局部質(zhì)變因子就沒有意義.對(duì)于小規(guī)模數(shù)據(jù)集近鄰閾值K的取值一般在10到30較為合適;對(duì)于大規(guī)模數(shù)據(jù)集K的取值一般在10到110較為合適.權(quán)值參數(shù)t的值會(huì)影響數(shù)據(jù)集對(duì)象間的差異，權(quán)值過小，在中高維數(shù)據(jù)空間中對(duì)象間的差異會(huì)不明顯.經(jīng)過大量實(shí)驗(yàn)表明，對(duì)于低維數(shù)據(jù)t一般取1較為合適，對(duì)于高維數(shù)據(jù)t一般取2到6較為合適.

3 結(jié)論

筆者提出了一種基于局部質(zhì)變因子的聚類邊界檢測(cè)算法BRINK，該算法既能用于帶有噪聲的均勻密度和非均勻低維數(shù)據(jù)集中聚類邊界識(shí)別，又能適用于高維數(shù)據(jù)集中聚類邊界的識(shí)別，解決了現(xiàn)有聚類邊界算法不能識(shí)別高維數(shù)據(jù)聚類邊界的問題.

［1］CHEN Yi-xia，HSU W，LEE M L，et al.BORDER：Efficient Computation of Boundary Points［J］.IEEE transaction on knowledge and data engineering，2006，18(3)：289－303.

［2］QIU Bao-zhi，YUE Feng，SHEN Jun-yi，et al.BRIM：AnEfficientBoundary Points Detecting Algorithm［C］//Proc.Of Advances in Knowledge Discovery andDataMining.Heidelberg：Springer，2007：761 －768.

［3］薛麗香，邱保志.基于變異系數(shù)的邊界點(diǎn)檢測(cè)算法［J］.模式識(shí)別與人工智能，2009，22(5)：799 －802.

［4］黃王非，陳黎飛，姜青山，等.基于子空間維度加權(quán)的密度聚類算法［J］.計(jì)算工程，2010，36(9)：65 －67.

［5］楊風(fēng)召，朱揚(yáng)勇，IncLOF：動(dòng)態(tài)環(huán)境下局部異常的增量挖掘算法［J］.計(jì)算機(jī)研究與發(fā)展，2004，41(3)：477 －484.