密度聚類算法報(bào)告.doc

1、密度聚類算法報(bào)告密度聚類算法報(bào)告 1.【摘要】：p 聚類分析p 是數(shù)據(jù)挖掘的重要方法。該文闡述了基于密度聚類分析p 的基本概念及其經(jīng)典的算法思想，并提出了一種基于核心點(diǎn)進(jìn)行聚類的算法。該算法首先對(duì)點(diǎn)進(jìn)行分類，分出核心點(diǎn)、邊界點(diǎn)和噪音點(diǎn)。然后采用自下而上的方式對(duì)簇進(jìn)行合并。對(duì)所有數(shù)據(jù)進(jìn)行分類并合并標(biāo)記后，給出最后結(jié)果圖。算法保證了數(shù)據(jù)處理的完整性。2.密度聚類的相關(guān)概念 對(duì)于構(gòu)成簇的每個(gè)對(duì)象，其Eps鄰域包含的對(duì)象個(gè)數(shù)必須不小于一個(gè)給定值（MinPts），也就是說(shuō)其鄰域的密度必須不小于某個(gè)閾值。下面給出基于密度聚類算法分析p 中的一些定義。直接密度可達(dá)：設(shè) p是核心點(diǎn)，如果q在p的Eps鄰域內(nèi)，

2、則稱從p出發(fā)直接可達(dá)q。密度相連：如果樣本集合中存在一個(gè)對(duì)象o ，使得對(duì)象p 和q 是從o 關(guān)于Eps鄰域和MinPts 密度可達(dá)的，那么對(duì)象p 和q 關(guān)于Eps和MinPts 密度相連 。簇：基于密度可達(dá)性的最大的密度相連的點(diǎn)的集合稱為簇。噪音點(diǎn)：不在任何簇中的對(duì)象。3.原理 考察樣本集中的某一點(diǎn)o，若o是核心點(diǎn)，則通過(guò)區(qū)域查詢得到該點(diǎn)的鄰域，鄰域中的點(diǎn)和o同屬于一個(gè)簇，這些點(diǎn)將作為下一輪的考察對(duì)象（即種子點(diǎn)），并通過(guò)不斷地對(duì)種子點(diǎn)進(jìn)行區(qū)域查詢來(lái)擴(kuò)展它們所在的簇，直至找到一個(gè)完整的簇。然后，依此程序?qū)ふ移渌拇?。最后剩下的不屬于任何類的點(diǎn)即為噪音點(diǎn)。4.算法流程 算法描述：算法：dbscan

3、 輸入：Eps半徑。MinPts給定點(diǎn)在Eps鄰域內(nèi)成為核心對(duì)象的最小鄰域點(diǎn)數(shù)。數(shù)據(jù)集。輸出：聚成的簇的圖形。1.Repeat 2.從數(shù)據(jù)集中抽取一個(gè)未處理的點(diǎn)；3.If 該點(diǎn)為核心點(diǎn) Then找出該點(diǎn)密度可達(dá)的點(diǎn)，構(gòu)成一個(gè)簇；4.Else goto 2；5.簇外的點(diǎn)都標(biāo)記成噪聲；6.Until 所有的點(diǎn)都被處理過(guò)；5.輸入函數(shù)和子函數(shù) 5.1輸入函數(shù)：MinPts=5; 閾值 Eps=1; 半徑 m,n=size(data);得到數(shù)據(jù)的大小 _=(1:m) data;將數(shù)據(jù)存到_中，并加上標(biāo)號(hào)1->m m,n=size(_);載入數(shù)據(jù)集的大小 type=zeros(m,1);用于區(qū)分核

4、心點(diǎn)1，邊界點(diǎn)0和噪音點(diǎn)-1 dealed=zeros(m,1);用于判斷該點(diǎn)是否處理過(guò),0表示未處理過(guò),1表示處理過(guò) dis=calDistance(_(:,2:n-1);距離矩陣計(jì)算 class=zeros(1,m);顏色分類 number=1;簇號(hào) 5.2子函數(shù)：計(jì)算矩陣中點(diǎn)與點(diǎn)之間的距離 function dis = calDistance( _ ) m,n = size(_); 給m，n賦值 dis = zeros(m,m); 距離矩陣 for i = 1:m 計(jì)算點(diǎn)i和點(diǎn)j之間的歐式距離 for j = i:m tmp =0; for k = 1:n n維循環(huán) tmp = tmp+

5、(_(i,k)-_(j,k).2; end dis(i,j) = sqrt(tmp); dis(j,i) = dis(i,j); end end end 畫出Eps和minpots的曲線 data=load(C:Userssin_Deskdatarings.t_t); m,n=size(data);得到數(shù)據(jù)的大小 _=(1:m) data;將數(shù)據(jù)存到_中，并加上標(biāo)號(hào)1->m Dis=calDistance(_(:,2:n-1);距離矩陣計(jì)算 Dis_4=sort(Dis,2); e=Dis_4(:,4); e=-sort(-e);降序排列 plot(e) a_is(0,100,0,0.5

6、) 5.3確定EPS和MinPts 求出所有點(diǎn)的第5近鄰記為dis_5，并將dis_5按照降序排列，找出Eps值相對(duì)平緩的點(diǎn)作為Eps，并且Minpts取值為5.如下圖5-1.圖5-1（數(shù)據(jù)集rings.t_t）6.算法分析p 本程序采用密度聚類算法（DBSCAN），目的在于過(guò)濾低密度區(qū)域，發(fā)現(xiàn)稠密度樣本點(diǎn)。優(yōu)點(diǎn)：在執(zhí)行時(shí)不需要知道簇的數(shù)目，簇的大小，以及可以對(duì)任意維度的樣本都可以得出良好的結(jié)果。并且對(duì)噪聲有一定的抗干擾能力。缺點(diǎn)：當(dāng)點(diǎn)的距離都比較接近的時(shí)候，無(wú)法執(zhí)行出良好的結(jié)果；當(dāng)數(shù)據(jù)集的密度是可變的時(shí)候，也無(wú)法得出良好的結(jié)果。7.結(jié)果圖 本算法運(yùn)行的結(jié)果如圖7-1和7-2所示：圖7-1（數(shù)

7、據(jù)集rings.t_t）圖7-2（數(shù)據(jù)集ball.t_t）8.附錄代碼 for i=1:m if dealed(i)=0 _Temp=_(i,:); D=dis(i,:); ind=find(D1 length(ind)=MinPts+1 type(_Temp(1,1)=1; class(ind)=number; 直接密度可達(dá)與密度可達(dá) while isempty(ind)鄰域內(nèi)點(diǎn)不為空?qǐng)?zhí)行循環(huán) yTemp=_(ind(1),:); yTemp存第ind（1）個(gè)點(diǎn) dealed(ind(1)=1; ind(1)=; D=dis(yTemp(1,1),:); ind_1=find(D1 class(ind_1)=number; if length(ind_1)>=MinPts+1 type(yTemp(1,1)=1; for j=1:length(ind_1) if dealed(ind_1(j)=0 dealed(ind_1(j)=1; ind=ind ind_1(j); class(ind_1(j)=number; end end else 該點(diǎn)不能擴(kuò)展 type(