邱保志，楊 洋，杜效偉

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

0 引言

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

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

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

1 BRINK算法

1.1 相關(guān)概念

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

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

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

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

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

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

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

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

定義4對象p的K距離鄰域為包含所有與p的距離不超過K-dist(p)的對象，即

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

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

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

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

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

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

1.2 BRINK 算法描述

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

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

輸出：聚類的邊界對象;

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

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

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

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

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

2 實驗結(jié)果及分析

實驗環(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 實驗結(jié)果

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖3 三種算法運行時間對比Fig.3 Running time of three algorithms compared

2.3 參數(shù)討論

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

3 結(jié)論

筆者提出了一種基于局部質(zhì)變因子的聚類邊界檢測算法BRINK，該算法既能用于帶有噪聲的均勻密度和非均勻低維數(shù)據(jù)集中聚類邊界識別，又能適用于高維數(shù)據(jù)集中聚類邊界的識別，解決了現(xiàn)有聚類邊界算法不能識別高維數(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ù)的邊界點檢測算法［J］.模式識別與人工智能，2009，22(5)：799 －802.

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

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