1    緒論

聚類[1]是根據(jù)數(shù)據(jù)集中數(shù)據(jù)對象之間的相似性[2]，將數(shù)據(jù)對象劃分為若干個類，從而發(fā)現(xiàn)數(shù)據(jù)間的結(jié)構(gòu)。聚類的邊界[3]指的是聚類邊緣處的數(shù)據(jù)對象，它代表了一種模式，對數(shù)據(jù)挖掘[4-6]有著重要的意義。當前，聚類邊界的研究正處于發(fā)展階段，提出的聚類邊界檢測算法并不多。但是，就已經(jīng)提出的邊界檢測算法來講，盡管它們通過使用不同的方法，獲得了數(shù)據(jù)集中所有聚類的整體邊界[7]，卻無法從數(shù)據(jù)集中提取出任一聚類的邊界。為了解決數(shù)據(jù)集中任一聚類的邊界提取問題，本文提出了兩種簇邊界檢測算法：基于 DBSCAN 的任一簇邊界提取算法和基于 K 近鄰[8]的具有聚類功能的簇邊界提取算法。 本章一共分為三節(jié)：第一節(jié)概括了任一聚類邊界檢測的研究背景與意義；第二節(jié)敘述了聚類邊界檢測算法的研究現(xiàn)狀；第三節(jié)則是對本文的組織結(jié)構(gòu)進行說明。 

1.1    研究背景與意義 
聚類是將數(shù)據(jù)分類到不同的類或者簇的一個過程，所以同一個簇中的對象有很大的相似性，而不同簇間的對象有很大的相異性[9]。聚類分析[10-12]是一種非常有用的數(shù)據(jù)分析模式。在現(xiàn)實生活中，我們可以對商場中的消費者進行聚類，通過比較不同消費者購買物品之間的相似性，我們可以制定出“捆綁銷售”的營銷策略[13]。例如，通過聚類分析我們可以發(fā)現(xiàn)這樣的一類消費群體，他們在購買了薯片之后，一般還會再購買可樂。這樣，我們就可以將薯片和可樂進行捆綁銷售，從而促進商品銷量的增加和商場利潤的增長。 聚類技術的研究是近幾年研究的一個熱門，并且現(xiàn)如今已經(jīng)提出了許多聚類算法，比較經(jīng)典的聚類算法如：基于密度的聚類算法 DBSCAN[14]，基于原形的聚類算法 K-MEANS[15]，等等�？墒�，對聚類的邊界的探討卻還不夠多。聚類的邊界指的是聚類邊緣處的數(shù)據(jù)點對象。邊界點與孤立點[16-19]和噪聲點[20-22]不同。對邊界對象[23]來講，它的類歸屬是確定的，但是，它與類中其它對象相比又具有不同的特性，代表著一種數(shù)據(jù)模式。例如，在醫(yī)學領域中，惡性腫瘤患者的檢測與預防一直是近年來我們比較關注的熱點話題。惡性腫瘤患者的來源可能是良性腫瘤患者中的那些邊界對象，也就是說良性腫瘤患者的聚類邊界可能是那些易發(fā)展為惡性腫瘤的患者群體。因此，通過對良性腫瘤患者聚類邊界的檢測與研究，我們可以提前預判哪些良性腫瘤患者可能會發(fā)展成為惡性腫瘤患者，檢測并發(fā)現(xiàn)發(fā)現(xiàn)如是的患者對惡性腫瘤的提前預防和治療具有十分重要的應用意義。 目前，在聚類的邊界檢測方面，已經(jīng)存在一些成熟的、使用不同方法的聚類邊界提取算法。例如基于 K 近鄰的聚類邊界檢測算法：BORDER[24]；基于K-距離的聚類邊界檢測算法 BAND[25]、BRINK[26]；基于密度的聚類邊界檢測算法：BOUND[27]、BRIM[28]；基于證據(jù)積累的聚類邊界提取算法：BERGE[29]，等等。盡管以上聚類邊界檢測算法均可以有效的檢測出數(shù)據(jù)集的整體邊界，但是卻無法識別出數(shù)據(jù)集中的聚類個數(shù)以及每一個聚類的邊界。檢測出數(shù)據(jù)集的整體邊界固然重要，但是檢測出數(shù)據(jù)集中的每一個聚類的邊界，更加重要。文獻[29]中使用 BERGE 算法成功提取出了 Mushroom（包含有毒蘑菇和無毒蘑菇）數(shù)據(jù)集中的聚類邊界，這些聚類邊界表示數(shù)據(jù)集中無法區(qū)分是有毒蘑菇還是無毒蘑菇的數(shù)據(jù)對象。但是如果我們能夠提取出每一個聚類的邊界，即有毒蘑菇的邊界和無毒蘑菇的邊界，我們就可以研究有毒蘑菇和無毒蘑菇之間的聯(lián)系和區(qū)別，進而更加準確的區(qū)分有毒蘑菇和無毒蘑菇，這對我們的生產(chǎn)和生活，具有更加重要的應用意義。因此，對數(shù)據(jù)集中任一聚類的邊界的檢測，即：對數(shù)據(jù)集中所有單聚類邊界的檢測和研究具有十分重要的理論意義與實際意義。 
.........

1.2    聚類邊界研究的現(xiàn)狀
邊界點的概念首先由 Ester 等在 DBSCAN 這一聚類算法中提出的。Ester等人認為，一個對象是否是邊界點應該達到以下兩個要求：1、它是一個非核心點對象；2、它落在某個核心點的 eps-鄰域內(nèi)。盡管 Ester 等人給出了邊界點的定義和計算方法。但是這些定義和計算方法僅僅是針對聚類，并不涉及邊界檢測。也就是說，DBSCAN 算法中邊界點概念的提出，可以使聚類算法的精度得到提高，但其并未給出如何計算并查找出一個給定數(shù)據(jù)集中各個聚類的具體邊界的方法。 聚類的內(nèi)部點[30]有別于聚類的邊界點，聚類的內(nèi)部點通常存在于數(shù)據(jù)空間中的密集區(qū)域，其四周均有大量的數(shù)據(jù)對象圍繞著；邊界點雖然也位于數(shù)據(jù)空間中的密集區(qū)域，但其僅有一側(cè)是被大量的點對象圍繞著。BORDER 算法就是借助邊界點的這種特性，，利用邊界點的反向 K-近鄰個數(shù)小于聚類內(nèi)部點的反向K-近鄰個數(shù)來辨認邊界點。BORDER 算法能夠在不含噪聲的數(shù)據(jù)集上比較完好的獲得給定數(shù)據(jù)集的整體邊界，但是對于含有噪聲的數(shù)據(jù)集，BORDER 算法無法排除噪聲的干擾，即將噪聲點識別為邊界點。BAND 算法提出了 K-距離的概念，它給數(shù)據(jù)集中每一個對象都定義了局部密度，而局部密度的值則定義為給定對象到其 K-距離范圍內(nèi)其它對象的距離和的平均值的倒數(shù)。在局部密度的基礎上，BAND 算法又給數(shù)據(jù)集中每一個對象定義了變異系數(shù)，任一對象的變異系數(shù)的值為該對象 K-距離范圍內(nèi)其它對象的局部密度的標準差與這些對象的局部密度的平均值的比值。由于聚類內(nèi)部點、噪聲點的變異系數(shù)較小，邊界點的變異系數(shù)較大，所以 BAND 算法能夠在含有噪聲的數(shù)據(jù)集上提取出數(shù)據(jù)集的整體邊界。BRINK 算法在 K 距離的基礎上提出了局部質(zhì)變因子 LOF 的概念來識別邊界點。對于給定的數(shù)據(jù)集，通常簇內(nèi)對象的 LOF 值約等于 1，簇邊緣對象的 LOF 值略大于 1，而且數(shù)據(jù)對象距離簇的距離越遠，該對象的 LOF 值就越大。BRINK 利用 LOF 的值來提取邊界點，它可以排除噪聲的干擾并且實現(xiàn)在高維數(shù)據(jù)集上檢測整體邊界目的。BOUND 算法利用數(shù)據(jù)集中給定數(shù)據(jù)對象的 Eps 鄰域內(nèi)其它數(shù)據(jù)對象在該對象的正負半鄰域內(nèi)分布不均的特點來識別邊界點。如果一個數(shù)據(jù)點的正半鄰域中所包含的數(shù)據(jù)點的個數(shù)總和除以負半領域中所包含的數(shù)據(jù)點的個數(shù)總和的商超過給定的閾值，那么這個點就被視為邊界點。BOUND 算法能夠在含有噪聲的且具有不同形狀簇的數(shù)據(jù)集上提取出數(shù)據(jù)集的整體邊界。BERGE 算法將模糊聚類引入了邊界檢測，它采用證據(jù)積累的思想克服了模糊 C-MEANS[31-32]隨機初始化聚類中心所帶來的誤差，并且根據(jù)數(shù)據(jù)對象的隸屬度定義了邊界因子 BOF 來識別邊界點。給定對象的 BOF 值越大，那么它就越有可能是邊界點。BERGE 算法能夠有效地從含有噪聲的高維數(shù)據(jù)集中提取出邊界點。 
..........

2    基于 DBSCAN 的任一簇邊界提取算法 

本章在點密度、平均密度、連通距離、邊界度等概念的基礎上提出了一種基于 DBSCAN 的任一簇邊界檢測算法 DBORDER。本章主要包含 4 個部分：第一部分是相關工作，主要分析介紹 DBSCAN 算法在邊界檢測方面存在的不足。第 2 部分是算法定義，對 DBORDER 算法所用到的一些術語、方法或概念進行詳細的解釋和說明。第 3 部分是算法描述，對 DBORDER 算法執(zhí)行的具體步驟進行解釋和說明。第 4 部分是實驗結(jié)果及分析，將 DBORDER 算法同其它邊界檢測算法做比較實驗以及對實驗結(jié)果、算法進行分析。

2.1    相關工作 
Ester 等提出了聚類算法 DBSCAN，它認為邊界點是位于核心點的 eps-鄰域內(nèi)的非核心點對象[14]。雖然作為一種聚類算法，DBSCAN 卻可以通過求邊界點、聚類來獲取數(shù)據(jù)集中聚類的整體邊界以及數(shù)據(jù)集中各個聚類的邊界。盡管如此，DBSCAN 算法在邊界提取、邊界點識別以及聚類個數(shù)的確定上還存在著一些不足： 第一，DBSCAN 使用全局 eps。所以，當 eps 取值較大時，DBSCAN 算法很容易將靠近聚類邊緣的噪聲點誤識別為邊界點，將相互之間比較靠近的類誤識別為一個類；當 eps 取值較小時，DBSCAN 算法很容易將聚類內(nèi)部點誤分為噪聲點或邊界點，將一個類誤分為若干各類。 圖 2.1(a)是一個完整的簇，圖 2.1(b)是圖 2.1(a)中黑框部分的放大圖像。圖2.1(b)中，eps 取值為 3，minpts 取值為 10，A 點的點密度為 16，B 點的點密度為 9，C 點的點密度為 14。由于 A、C 兩點的點密度大于 minpts，B

 點的點密度小于 minpts，所以，DBSCAN 算法根據(jù) minpts 的取值，將 A、C 識別為核心點，B 識別為邊界點。

......

2.2    算法定義
給出 eps，就意味著數(shù)據(jù)集中所有數(shù)據(jù)對象鄰域范圍的大小是一致的[36]。而當數(shù)據(jù)集中各個聚類的位置比較靠近，或者數(shù)據(jù)對象的點密度分布不均，或者各個聚類的內(nèi)部對象分布不均時，過大的 eps 會導致本不應該合并的聚類被強行地合并成一個類，本應該排除的噪聲點被強行的劃分到聚類中；而過小的eps 又會導致同一個類被強行地劃分成若干個類，本應該屬于聚類內(nèi)部中的點被強行的識別為噪聲點或邊界點。因此，給定連通度，求出連通半徑，讓核心點關于連通半徑連通，而不是像 DBSCAN 算法中的那樣關于 eps 連通，就可以將 eps 的取值同聚類個數(shù)以及噪聲點的識別過程相互剝離，從而降低 eps 的取值對全局的影響，提高數(shù)據(jù)集中聚類數(shù)目和噪聲點識別的精確性。 
............

3 基于 K 近鄰的具有聚類功能的簇邊界提取算法 .... 19 
3.1 背景介紹 .......... 19 
3.2 算法定義 .......... 20 
3.3 算法描述 .......... 22 
3.4 實驗結(jié)果及分析 .... 23 
3.4.1 綜合數(shù)據(jù)集上的對比實驗 ............ 23 
3.4.2 高維真實數(shù)據(jù)集上的對比實驗 ......... 27
3.5 算法時間復雜度分析 ......... 35 
3.6 參數(shù)討論 .......... 35 
3.7 本章小結(jié) .......... 35 
4 總結(jié)與展望 ............ 36
4.1 總結(jié) ..... 36 
4.2 展望 ..... 36 

3    基于 K 近鄰的具有聚類功能的簇邊界提取算法 

本章在 K 近鄰、反向 K 近鄰、邊界度等概念的基礎上提出了一種基于 K近鄰的具有聚類功能的簇邊界提取算法 KBORDER。本章主要包含 3 個部分：第 1 部分是算法定義，主要是對 KBORDER 算法所用到的一些術語、方法或概念進行詳細的解釋和說明。第 2 部分是算法描述，主要是對 KBORDER 算法執(zhí)行的具體步驟進行解釋和說明。第 3 部分是實驗結(jié)果及分析，主要將 KBORDER算法同其它邊界檢測算法做比較實驗以及對實驗結(jié)果進行分析。 

3.1    背景介紹

目前，在聚類方面，已經(jīng)提出了很多聚類算法，如基于原型的 K-MEANS[38]算法，基于密度的  Revised DBSCAN[39]算法等。K-MEANS 算法在含有“圓形簇”或者簇間間距比較大的數(shù)據(jù)集上能夠得到良好的聚類結(jié)果，但在含有噪聲以及不規(guī)則簇的數(shù)據(jù)集上，K-MEANS 算法的聚類效果不佳。Revised DBSCAN算法可以在含有噪聲、具有不同形狀和大小的均勻簇的數(shù)據(jù)集上能夠得到良好的聚類結(jié)果，但是 Revised  DBSCAN 算法由于使用全局 Eps，使得它在含有變密度的簇的數(shù)據(jù)集上無法得到理想的聚類結(jié)果[40]。K-MEANS 算法和 Revised DBSCAN 算法均可以有效的檢測出數(shù)據(jù)集中的聚類個數(shù)以及聚類劃分，但在數(shù)據(jù)集的整體邊界模式以及各個聚類的邊界模式的提取上，卻缺乏相關的研究與探討。 在聚類的邊界檢測方面，已經(jīng)提出了一些檢測算法，如 BOUND、BORDER等。BORDER 算法在不含噪聲的數(shù)據(jù)集上能夠得到良好的邊界檢測結(jié)果，但在含有噪聲的數(shù)據(jù)集上，BORDER 算法無法排除噪聲的干擾，會將噪聲點全部識別為邊界點。BOUND 算法無論在含有或者不含有噪聲的數(shù)據(jù)集上都能得到良好的邊界檢測結(jié)果，但是 BOUND 算法只適用于低維數(shù)值屬性的數(shù)據(jù)集，它無法在高維數(shù)值屬性的數(shù)據(jù)集上檢測出數(shù)據(jù)集的邊界。BORDER 和 BOUND 算法均可以有效的檢測出數(shù)據(jù)集的整體邊界模式，但對某個聚類的邊界模式的提取，卻缺乏相關的研究與探討，而且也無法獲取數(shù)據(jù)集中的聚類個數(shù)以及聚類劃分。 

.........

總結(jié) 

聚類的邊界指的是聚類邊緣處的數(shù)據(jù)對象，它代表了一種模式，對數(shù)據(jù)挖掘有著重要的意義。當前，聚類邊界的研究正處于發(fā)展階段，提出的聚類邊界檢測算法并不多。但是，就已經(jīng)提出的邊界檢測算法來講，盡管它們能夠獲得數(shù)據(jù)集的整體邊界，但卻不能獲得數(shù)據(jù)集中任一聚類的邊界。 為了提取數(shù)據(jù)集中任一聚類的邊界，本文提出了 2 種簇邊界提取算法：1.基于 DBSCAN 的任一簇邊界提取算法，該算法在 DBSCAN 的基礎上，將連通度、邊界度、正負半鄰域等概念引入邊界處理，能夠獲取數(shù)據(jù)集中任一聚類的邊界以及數(shù)據(jù)集的整體邊界；2.基于 K 近鄰的具有聚類功能的簇邊界提取算法，該算法基于 K 近鄰與反向 K 近鄰，不但能夠獲取數(shù)據(jù)集中任一聚類的邊界和數(shù)據(jù)集的整體邊界，而且還能獲取給定數(shù)據(jù)集中的聚類數(shù)目與劃分。通過對這兩種算法的定義、具體執(zhí)行步驟、時間復雜度，參數(shù)進行說明和分析，將其同其它算法在綜合數(shù)據(jù)集上以及在真實數(shù)據(jù)集上進行對比實驗，并對實驗結(jié)果、實驗數(shù)據(jù)進行量化分析，檢驗了 DBORDER 算法與 KBORDER 算法在數(shù)據(jù)集上對任一聚類邊界的提取能力。 
.........
參考文獻(略)

本文編號：193945