基于密度權(quán)值平均變化率的CFSFDP聚類(lèi)算法

董炎焱

(晉中師范高等專(zhuān)科學(xué)校 數(shù)理科學(xué)系,山西 晉中 030600)

0 引言

聚類(lèi)分析可以對(duì)數(shù)據(jù)集不進(jìn)行訓(xùn)練而劃分簇,簇內(nèi)的數(shù)據(jù)相似特征明顯,不同簇的數(shù)據(jù)存在差異性．實(shí)際應(yīng)用中對(duì)聚類(lèi)算法不斷的優(yōu)化,使其能夠處理不同的數(shù)據(jù)類(lèi)型,具有可伸縮性,適應(yīng)任意簇形狀,排除噪聲干擾,適應(yīng)高維數(shù)據(jù)等．

自從DBSCAN算法結(jié)合密度后,密度的概念逐漸被強(qiáng)化,CFSFDP算法適應(yīng)于對(duì)任意簇形狀的聚類(lèi),文獻(xiàn)[1]計(jì)算最佳局部密度,并設(shè)置距離閾值,文獻(xiàn)[2]對(duì)于低密度的簇進(jìn)行單獨(dú)聚類(lèi)等等,許多研究圍繞密度從細(xì)節(jié)優(yōu)化CFSFDP算法,以解決人為設(shè)置截?cái)嗑嚯xdc和肉眼觀察決策圖以挑選聚類(lèi)中心所帶來(lái)的偏差．

1 CFSFDP聚類(lèi)算法

1.1 傳統(tǒng)的CFSFDP算法

CFSFDP算法存在假設(shè)條件:聚類(lèi)中心必是局部密度最高的點(diǎn)且一個(gè)簇對(duì)應(yīng)一個(gè)聚類(lèi)中心,各簇之間的邊界保持清晰．

設(shè)有數(shù)據(jù)點(diǎn)集{D},定義每個(gè)點(diǎn)Di的參數(shù)如下:

局部密度ρ,ρ=∑P(dij-dc);其中dij為兩點(diǎn)的歐式距離,dc為人為設(shè)定的截?cái)嗑嚯x;當(dāng)dij-dc≥0時(shí),不計(jì)數(shù),dij-dc0時(shí),計(jì)數(shù)是1,即該點(diǎn)與其他點(diǎn)的距離大于等于截?cái)嗑嚯x時(shí)不考慮,否則P(dij-dc)=1,求和以得到該點(diǎn)的局部密度ρ．

CFSFDP算法如下:

1) 計(jì)算數(shù)據(jù)點(diǎn)集{D}的距離矩陣;

2) 根據(jù)局部密度ρ的定義求各數(shù)據(jù)點(diǎn)的ρ;

3) 根據(jù)距離δ的定義求各數(shù)據(jù)點(diǎn)的δ;

4) 根據(jù)ρ和δ畫(huà)出決策圖,通過(guò)觀察找到聚類(lèi)中心{w1,w2…wi};

動(dòng)脈導(dǎo)管開(kāi)放是早產(chǎn)兒常見(jiàn)疾病，目前早產(chǎn)兒PDA的自然發(fā)展過(guò)程仍未完全明確,PDA發(fā)生的部分高危因素仍存在爭(zhēng)議,對(duì)PDA是否進(jìn)行藥物、手術(shù)干預(yù),何時(shí)進(jìn)行藥物、手術(shù)干預(yù)仍存在爭(zhēng)議。盡管已經(jīng)有大量證據(jù)證實(shí)動(dòng)脈導(dǎo)管持續(xù)開(kāi)放可能有害，但是目前尚缺乏關(guān)閉PDA治療方案的遠(yuǎn)期益處或害處的相關(guān)證據(jù)。盡管產(chǎn)前激素、肺泡表面活性物質(zhì)及非創(chuàng)傷性呼吸支持已經(jīng)得到廣泛應(yīng)用，目前尚無(wú)評(píng)估動(dòng)脈導(dǎo)管持續(xù)開(kāi)放對(duì)早產(chǎn)兒死亡率及并發(fā)癥影響的臨床試驗(yàn)，近年來(lái)關(guān)于PDA治療的研究最大的改變是減少PDA的治療[3]。

1.2 CFSFDP算法的決策圖

以局部密度ρ為橫坐標(biāo),距離δ為縱坐標(biāo),畫(huà)出決策圖．如圖1所示.

圖1 CFSFDP決策圖

由圖1可以看出在決策圖的右上角存在密度峰值點(diǎn),通常把這些點(diǎn)稱(chēng)為聚類(lèi)中心,它們的ρ值最大,δ較高．理論上可以通過(guò)觀察找到聚類(lèi)中心．

1.3 CFSFDP算法的局限性

ρδ的決策圖較為直觀,如果根據(jù)圖1選擇聚類(lèi)中心,會(huì)發(fā)現(xiàn)只有一個(gè)密度峰值點(diǎn)．但由數(shù)據(jù)表發(fā)現(xiàn)ρ1=8,δ1=13.243 513 23;ρ2=8,δ2=13.289 747 16,存在兩個(gè)密度峰值點(diǎn),這兩個(gè)點(diǎn)在圖中基本重合在一起,人工選擇就會(huì)出現(xiàn)漏選．因此單純地以決策圖來(lái)確定聚類(lèi)中心存在不確定性,影響算法的準(zhǔn)確性．

2 基于密度權(quán)值平均變化率的CFSFDP算法

2.1 算法原理

根據(jù)原算法對(duì)ρ和δ的定義,如果ρ是最大,那么它是密度峰值點(diǎn),取的是與密度峰值點(diǎn)最遠(yuǎn)的距離作為δ;如果是非密度峰值點(diǎn),從比該點(diǎn)更高的ρ的范圍內(nèi)選取與該點(diǎn)最近的距離作為δ,也就是說(shuō)密度峰值點(diǎn)的都ρ和δ較大,分布在決策圖的右上角．針對(duì)聚類(lèi)中心點(diǎn)重疊而人工不能分辨的問(wèn)題,本文提出基于密度權(quán)值平均變化率的CFSFDP算法．

區(qū)分點(diǎn)最直接的方法是增加點(diǎn)的差異性,因此采用的ρ和δ乘積作為密度權(quán)值．為了能夠通過(guò)計(jì)算得到聚類(lèi)中心,將權(quán)值繼續(xù)變化,引入權(quán)值差,實(shí)際為線段的斜率,也稱(chēng)為平均變化率,反應(yīng)偏離的變化趨勢(shì)．

基于密度權(quán)值平均變化率的CFSFDP算法如下:

1) 根據(jù)傳統(tǒng)的CFSFDP算法求出ρ和δ;

3) 搜索拐點(diǎn),在權(quán)值差圖從左向右遍歷,設(shè)拐點(diǎn)為x,滿(mǎn)足x=argmax|Δγi+1-Δγi|;

4) 拐點(diǎn)x左邊的點(diǎn)(包括x)均為聚類(lèi)中心;

5) 根據(jù)原算法的5)完成其余非聚類(lèi)中心數(shù)據(jù)點(diǎn)的歸類(lèi)．

3 實(shí)驗(yàn)

實(shí)驗(yàn)數(shù)據(jù)來(lái)源http://www.stats.gov.cn/tjsj/pcsj/rkpc/6rp/indexch.htm,沒(méi)有噪聲數(shù)據(jù),去除了數(shù)據(jù)標(biāo)簽,并取對(duì)數(shù)．

根據(jù)改進(jìn)算法的2)畫(huà)出權(quán)值圖,如圖2.

圖2 權(quán)值圖

可以看出密度權(quán)值表現(xiàn)為下降趨勢(shì),呈現(xiàn)為“先急后緩”,從左向右遍歷時(shí)極值點(diǎn)出現(xiàn)在左邊的幾率較大．計(jì)算權(quán)值的平均變化率,也是線段的斜率,得到圖3權(quán)值差圖．

圖3 權(quán)值差圖

權(quán)值差圖中可以看出拐點(diǎn)的位置,但是考慮到截?cái)嗑嚯xdc的人為選取影響拐點(diǎn)的位置,所以計(jì)算平均變化率以求得準(zhǔn)確的拐點(diǎn)．計(jì)算結(jié)果見(jiàn)表1.

表1 密度權(quán)值平均變化率

表1中選取前30個(gè)數(shù)值,極大值出現(xiàn)的位置為100.312 7,對(duì)應(yīng)于圖3的拐點(diǎn)x,因此選擇x左邊的點(diǎn)包括x,產(chǎn)生2個(gè)聚類(lèi)中心,將基本重疊的聚類(lèi)中心有效地分開(kāi)．原算法由圖1的決策圖只能看到一個(gè)聚類(lèi)中心．

4 結(jié)論

改進(jìn)的CFSFDP聚類(lèi)算法原則上解決了決策圖中聚類(lèi)中心重疊而造成漏選的問(wèn)題,以計(jì)算密度權(quán)值的平均變化率得到拐點(diǎn),從而產(chǎn)生聚類(lèi)中心,去除了人為的因素,客觀地反應(yīng)了聚類(lèi)中心的存在個(gè)數(shù)．不足之處在于沒(méi)有判斷選出鄰近的聚類(lèi)中心是否需要合并．