障礙空間中一種基于密度的快速聚類算法.pdf

1、傳統(tǒng)聚類算法中各個數據對象之間的相似度衡量標準一般是各種距離的度量，如歐幾里德距離或者曼哈頓距離。在障礙空間中，由于障礙的存在，各個數據對象的連接性被阻斷，它們之間的傳統(tǒng)距離就失去了意義。因此，傳統(tǒng)的聚類算法在障礙空間中失去了相似度判斷的有效性，從而不能很好的工作。為此，已經有少數學者開始致力于障礙空間中聚類算法的研究。DBCO算法就是在此背景下致力于解決障礙空間中聚類算法的研究?？傮w來說，DBCO是基于密度的聚類算法，它主要集中于下面

2、三個方面的研究。
　　 第一個方面是如何對障礙空間中的障礙進行模型化。模型化目的是使得障礙的表示形式化，利于數據對象的相互操作。模型化不應該以增加過多的數據預處理為代價。第二個方面是如何有效的判斷障礙空間中各個數據對象之間的相似度。相似度的判斷是聚類算法的核心部分。如何在障礙空間中消除障礙對相似度的影響，是障礙空間中聚類算法研究的一個核心環(huán)節(jié)。第三個方面是在實現上述兩個方面的前提上如何有效的保證聚類算法的效率。效率是一個算法的重

3、要衡量標準，障礙空間中的聚類算法在障礙建模、改變相似度判斷標準的同時，不能增加過多的開銷而影響算法的效率。
　　 在對障礙建模的同時對障礙模型進行簡化，是減少數據預處理的有效辦法。所建立的障礙模型簡化方法具有簡化行和完整性。新的相似度判斷方法不僅保證了被障礙阻斷聯(lián)系的對象之間的不可達性，還保留了鄰域沿著障礙上的連接點和端點方向上的擴展性。而選取領域中的部分代辦點進行聚類擴展，能夠很好的保證聚類算法在障礙空間中的聚類效率。