• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

      基于網(wǎng)格聚類中邊界點的處理

      2012-08-23 02:02:14江先偉福建船政交通職業(yè)學院福建福州350007
      科技視界 2012年34期
      關鍵詞:邊界點鄰域邊界

      江先偉(福建船政交通職業(yè)學院 福建 福州 350007)

      0 引言

      基于網(wǎng)格的聚類方法是運用網(wǎng)格技術,把對象空間量化為有限數(shù)目的網(wǎng)格單元,形成一個網(wǎng)格結構,所有的聚類操作都在這個網(wǎng)格結構上進行。一個網(wǎng)格單元的鄰居是指與其有共同邊界的或有共同點的那些網(wǎng)格單元。一個網(wǎng)格單元包含對象的數(shù)目超過給定的密度閾值MinPts,則認為它是高密度單元,否則視其為低密度單元。連接相鄰密集單元的最大區(qū)域就形成一個“簇”,在這個區(qū)域內(nèi)的所有對象屬于這個簇。對孤立點,在聚類過程中應該將其丟棄,如果一個低密度單元的相鄰的網(wǎng)格單元中存在高密度單元,那么該單元中的點可能是簇的邊界點,也可能是噪聲點,為此,可利用邊界處理技術作進一步處理。

      聚類的邊界代表了一種潛在的模式,對數(shù)據(jù)挖掘有著重要的意義。但是目前涉及邊界的算法并不多,對其研究遠遠不夠。另一方面,邊界點處于某些簇的相鄰位置,許多聚類算法(如基于網(wǎng)格的方法)不能準確地把這些邊界點劃分到對應的簇中,從而降低了聚類結果的質(zhì)量。

      1 相關工作

      1.1 邊界點的定義

      在DBSCAN算法中,第一次提出了邊界點的概念。算法是基于密度定義了簇的邊界點,即如果一個對象不是核心點(所謂核心點指的是某對象的ε-鄰域內(nèi)至少包含最小數(shù)目MinPts個對象),且它是從某個核心點直接密度可達的 (即該對象落入某核心點的ε-鄰域內(nèi)),則定義該對象為邊界點。

      Chen Xia等提出了聚類邊界點檢測算法BORDER[1],其邊界點的定義如下:

      定義 邊界點(Boundary point):一個邊界點p是指滿足下列兩個條件的數(shù)據(jù)對象:

      ①它位于一個高密的區(qū)域IR;②p的附近存在一個區(qū)域IR′,Density(IR)>>Density(IR′),或者 Density(IR′)>>Density(IR)。

      聚類的邊界代表了一種潛在的模式,對數(shù)據(jù)挖掘有著重要的意義。但是目前涉及邊界的算法并不多,對其的研究遠遠不夠。另一方面,邊界點處于某些簇的相鄰位置,許多聚類算法(如基于網(wǎng)格的方法)不能準確地把這些邊界點劃分到對應的簇中,從而降低了聚類結果的質(zhì)量。

      1.2 邊界點的處理方法

      DBSCAN算法基于密度定義了聚類邊界點,即如果一個對象不是核心點,且它是從某個核心點直接密度可達的,則定義該對象為邊界點。提出聚類邊界提取的BORDER算法中,應用反向k近鄰可以反映出潛在的數(shù)據(jù)分布特征,并可以利用它識別位于兩個或多個分布之間的邊界點。BORDER算法認為邊界點的反向k近鄰個數(shù)低于聚類內(nèi)部點的反向k近鄰個數(shù),如果一數(shù)據(jù)點的k近鄰個數(shù)低于某閾值則把其作為邊界點輸出。該算法的缺點是:①在含有噪聲的數(shù)據(jù)集中,因為噪聲點的反向k近鄰個數(shù)往往比聚類邊界點的反向k近鄰個數(shù)少,因此按照對象的反向k近鄰值從小到大順序排列整個數(shù)據(jù)集后,取出的前n個對象既包含孤立點又包含邊界點,因此該算法在含有噪聲的數(shù)據(jù)集上不能正確地識別邊界;②BORDER算法不能正確地提取變化密度、多密度聚類中的邊界,因為低密度點的反向k近鄰值較小,而高密度點的反向k近鄰值較大。

      文獻[2]提出了利用正負半鄰域關系來判斷聚類的點檢測算法,首先提出正負半鄰域的概念,進而計算出數(shù)據(jù)點的邊界度,根據(jù)邊界度進行邊界點的提取。它解決了DORDER算法不能將邊界與噪聲分離的問題。

      1.3 在網(wǎng)格中邊界點的處理

      傳統(tǒng)基于網(wǎng)格的聚類算法只處理高密度單元,低密度單元中的點作為孤立單元被丟棄,一旦聚類的邊界落入低密度單元,就會降低聚類精度,可能造成小聚類的丟失。并且,算法只能發(fā)現(xiàn)邊界是水平或垂直的簇,而不能檢測到斜的邊界,在大多數(shù)情況下這是不符合實際的。如何有效地提取邊界點,是提高聚類結果的質(zhì)量的關鍵問題之一。

      邊界單元和核心單元形成聚類簇的主要輪廓,而邊界點充實該輪廓,有時聚類簇的邊界點可能落入聚類結果網(wǎng)格單元以外的網(wǎng)格單元中,這就需要將聚類的邊界點從這些單元中提取出來,劃分到對應的簇中,以提高聚類的精度。邊界點提取有兩種方法:一種方法,是對與邊界單元相鄰而未聚類的網(wǎng)格單元進一步細分,如在每一維上再二等分,則每個邊界單元被劃分為2d個子單元,如果在這些子單元中存在與邊界單元相連接的子單元,則子單元中的對象視為邊界點,提取到相應的簇中;另一種方法,是基于這樣一個事實:簇中對象的密度高于簇外部的密度和邊界點的密度,聚類邊界的密度到聚類外部的密度有明顯的跳變,每次聚類都從未聚類中最高密度的網(wǎng)格單元開始逐步向外擴展,遇到邊界單元時進行邊界處理。對于一個與邊界網(wǎng)格單元g1相連的非密集單元g2,在非密集單元g2中取一個與邊界單元g1最近的點x,使用KNN近鄰關系法,在x和單元g1內(nèi)的點中觀測x的密集程度,來判斷x是否作為邊界點提取。如果是則用同樣的方法對下一對象進行處理,否則,x不能作為邊界點被提取。

      文獻[3]出了基于網(wǎng)格的聚類的邊界處理技術,該技術利用限制性k近鄰和相對密度的概念識別網(wǎng)格聚類的邊界點,提高聚類的精度。

      2 本文提出的邊界處理技術

      受DBSCAN算法的啟發(fā),本文提出的邊界處理方法是在網(wǎng)格結構中引入邊界網(wǎng)格單元和孤立網(wǎng)格單元的概念,依據(jù)邊界網(wǎng)格單元中包含對象的數(shù)目,定義該邊界單元的核心點,并依據(jù)核心點的ε-鄰域內(nèi)所有對象都屬于同一個簇的原則提取與邊界單元相鄰的孤立網(wǎng)格單元中的對象。

      本文定義的邊界網(wǎng)格單元:屬于某一簇的網(wǎng)格單元g,在它相鄰的網(wǎng)格單元中,存在與單元g屬于不同簇的單元或存在未聚類的單元,則將單元g定義為邊界網(wǎng)格單元,并稱單元g是其所屬簇的邊界網(wǎng)格單元。從與邊界網(wǎng)格單元相鄰的孤立網(wǎng)格單元中提取靠近的點對象,這種“靠近”的準則是:待提取點對象位于邊界網(wǎng)格單元中某一核心點的Step/2-鄰域內(nèi),則把該點對象作為邊界點提取到對應的邊界網(wǎng)格單元中。

      以邊界網(wǎng)格中的某點對象為圓心,Step/2為半徑的圓內(nèi)包含點對象的數(shù)目達到值τ:則該點對象定義為該邊界單元的核心點。

      其中,n0為該邊界網(wǎng)格單元的密度值。值τ實際上就是該邊界網(wǎng)格單元密度平均值的1/DCT倍取整。

      如圖所示,帶陰影的網(wǎng)格單元(標號為1~6)屬于同一個簇,標號為7~9的網(wǎng)格單元為孤立網(wǎng)格單元,其中點對象c是邊界網(wǎng)格單元(標號為5)的核心點,而孤立網(wǎng)格單元(標號為8)中的點對象o落在核心點c的Step/2-鄰域內(nèi)。則把點對象o作為邊界點提取到邊界網(wǎng)格單元5中。

      邊界點的處理

      對孤立網(wǎng)格單元中點對象的提取只須判斷其Step/2-鄰域內(nèi)是否存在邊界單元的核心點,如果存在,則把點對象o提取到該核心點所在的邊界網(wǎng)格單元中。當提取點對象o后,如果點o的Step/2鄰域內(nèi)包含的點數(shù)超過值τ,則點o也成為邊界網(wǎng)格單元的核心點,這樣邊界點的提取可以逐步向外延伸。

      3 結束語

      基于網(wǎng)絡聚類算法中,效率與精度總是一對矛盾。對孤立點,在聚類過程中應該將其丟棄,如果一個低密度單元的相鄰的網(wǎng)格單元中存在高密度單元,那么該單元中的點可能是簇的邊界點,也可能是噪聲點,為此,可利用邊界處理技術作進一點的處理。本文提出一種應用密度的思想對邊界點進行處理技術,可一定程度上提高基于網(wǎng)格聚類的精度。

      [1]ChenXia,wynne Hsu,Mong Li Lee et al.BORDER:Efficient computation of boundary points[J].IEEE transaction on knowledge and data engineering.2006,18(3):289-303.

      [2]Qiu,B Z,Yue F,Shen J Y et al.A efficient boundary points detecting algorithm.Proceedings of Advances in Knowledge Discovery and Data Mining(PAKDD)[M].New York:ACM Press.2007,4426:761-768.

      [3]邱保志,劉洋.基于網(wǎng)格熵的邊界點檢測算法[J].成都:計算機應用.2008,28(3):732-734.

      猜你喜歡
      邊界點鄰域邊界
      拓展閱讀的邊界
      道路空間特征與測量距離相結合的LiDAR道路邊界點提取算法
      測繪學報(2021年11期)2021-12-09 03:13:12
      層次化點云邊界快速精確提取方法研究
      激光技術(2021年5期)2021-08-17 03:36:02
      稀疏圖平方圖的染色數(shù)上界
      論中立的幫助行為之可罰邊界
      基于鄰域競賽的多目標優(yōu)化算法
      自動化學報(2018年7期)2018-08-20 02:59:04
      關于-型鄰域空間
      “偽翻譯”:“翻譯”之邊界行走者
      外語學刊(2014年6期)2014-04-18 09:11:49
      一種去除掛網(wǎng)圖像鋸齒的方法及裝置
      電腦與電信(2014年6期)2014-03-22 13:21:06
      基于時序擴展的鄰域保持嵌入算法及其在故障檢測中的應用
      芜湖县| 乌审旗| 唐山市| 丰都县| 海晏县| 白水县| 枣强县| 九龙城区| 西乌珠穆沁旗| 那坡县| 天等县| 罗甸县| 西宁市| 井研县| 临汾市| 平阳县| 涡阳县| 莱西市| 广宁县| 台前县| 开封县| 黄石市| 海林市| 和田市| 昌都县| 梅州市| 阳高县| 吐鲁番市| 凤冈县| 遂川县| 巴彦县| 关岭| 陇川县| 全州县| 呼和浩特市| 玉屏| 长沙市| 历史| 邛崃市| 黔西| 伊金霍洛旗|