移動型數據與靜態型數據的混合聚類算法

何云斌, 董 恒, 萬 靜

(哈爾濱理工大學 計算機科學與技術學院, 哈爾濱 150080)

0 引 言

聚類分析是數據挖掘與機器學習中十分重要的一個研究領域，是在沒有先驗知識的情況下對數據進行分類，并以此分析數據的特點。經典聚類算法K-means算法[1]，簡單高效、適用范圍廣，但是對聚類中心較為敏感，只能識別出球形簇。后來，科研工作者提出基于密度的聚類算法，克服了K-means的缺點，比如Huang等[2]提出了一種基于網格和基于密度的混合聚類算法GRPDBSCAN，該算法可以有效處理噪聲點，且運算速率較高，自動生成鄰域參數(ε,MinPts)。文[3]針對DPC算法在尋找聚類中心的過程時，計算復雜度高，無法在大規模數據集中應用的問題，提出基于網格篩選的SDPC算法。文[4]提出兩步操作的改進K-means算法，將算法在MapReduce模型上進行實現。

這些聚類算法是針對靜態型數據的聚類分析，在對靜態型數據進行處理時，可以產生比較良好的聚類效果，但是對于移動型數據卻難以奏效。這主要因為移動型數據具有移動特性，因此對于移動型數據的聚類處理，傳統聚類算法處理效果較差，研究人員轉向對移動型數據的聚類研究。

Kalnis[5]基于連續快照模型，提出了Moving Cluster模式，通過使用空間聚類算法對每張時間快照上的移動數據進行聚類處理，然后通過對比連續時間快照上簇之間Jaccard系數是否超過給定閾值，以判斷移動數據是否組成Moving Cluster模式。在Moving Cluster基礎上，科研工作者進行了改進，提出了Convoy[6]模式，并進一步提出了Swarm[7]模式。文[8]提出在開始先對快照上的移動對象進行聚類，然后在已有的聚類簇上使用KDS[9](動態數據結構)進行維護和修改。文[10]也是以連續快照模型，將DBSCAN算法改進并應用到移動對象上面，并提出基于時空圖的移動對象聚集檢索算法。文[11]提出一種并行算法RDD-Gathering來發現大規模軌跡數據中的聚集模式。文[12]提出了一種新型的群體模式，稱為進化群體，它模擬在不斷變化的流動軌跡中密度連通群集內一起行進的移動物體的異常群體事件。

在經過大量的文獻查詢和分析，發現目前已有針對混合數據類型的聚類算法中，經典的k-prototypes聚類算法,雖然針對同時具有數值屬性和分類屬性的混合數據簡單高效,但是算法易受初始聚類中心影響[13]。文[14]針對兼具數值屬性與分類屬性的不完備混合數據，提出三種完備化處理方法，并采用k-prototypes算法進行聚類處理。文[15]也是針對同時具有數值屬性和分類屬性的混合數據聚類，提出了基于信息熵的混合數據屬性加權聚類算法。文[16]針對k-prototypes算法無法自動識別簇數以及無法發現任意形狀的簇的問題,提出一種針對混合型數據的新方法。雖然這些研究是針對混合數據屬性，但是并非從數據的狀態混合出發，因此針對包含靜態型數據與移動型數據的混合聚類問題也無法有效處理。本文針對包含靜態型數據與移動型數據的混合數據的聚類問題，進行討論和分析并給出相應的聚類算法。

本文的主要貢獻：針對目前沒有包含移動型數據與靜態型數據的混合數據聚類問題的算法，本文根據已有的處理靜態型數據的聚類算法和移動型數據的聚類算法的優缺點，基于“分而治之”的思想，提出針對混合數據的聚類算法。在具體方法上則提出將處理移動型數據的連續快照模型結合處理靜態型數據的密度化處理方法，以時間為主線，對混合數據進行聚類分析。

1 相關概念與定義

給定歐式空間中，移動數據集M={m1,m2,…,mp}，靜態數據集S={s1,s2,…,sq}，基于以上概念，進一步給出如下定義。

定義1(時間快照) 設混合對象數據庫是ODB={M,S}，與它相對應的時間數據庫TDB，時間快照Pi={(ai,ti)|ai∈ODB,ti∈TDB}，其中Pi是對應時間ti的時間快照，是時間快照集合P的子集。

定義2(移動對象聚類[10]) 令集合ci={m1,m2,…,mp}是對應于每一個時間i(1≤i≤k)的移動對象集合，對于兩個給定的閾值nc和kc，當滿足以下條件時，ci是一個移動對象聚類：

1)ci中的成員數量size(ci)≥nc;

2)ci存在一段時間，即生存時間time(ci)≥kc;

3)ci包含的任意兩個移動對象mk和mr的距離不大于δ，可以表示為dist(mk,mr)≤δ，其中，?mk,mr∈M。

2 算法描述

目前已有的聚類算法研究都是圍繞單一數據類型的聚類問題展開，對于包含移動型數據與靜態型數據的混合數據聚類問題，則沒有相應的討論和研究，下面首先從單個的移動型數據與靜態型數據集的聚類問題開始分析。

2.1 一個移動型數據與靜態型數據集的聚類算法

問題描述：若在給定歐式空間中，有一個隨機移動的移動型數據m和位置隨機分布的靜態型數據集S構成的混合數據H，如何對混合數據H進行聚類處理，本節進行討論和分析，并給出相應的聚類算法。

混合數據最大的特點就是不同的數據類型交織在一起，如果直接對其進行聚類處理，則會比較困難。因此提出應用“分而治之”的思想，將不同的數據分開處理，然后再合并處理。在本文中就是先將靜態型數據與移動型數據分開進行聚類處理，然后再進行合并聚類處理。

為了便于對混合數據進行聚類分析，采用時間快照的方法，因為時間快照可以完整將數據間的相對位置和移動物體的歷史移動軌跡記錄下來。為了能對記錄下來的數據類型進行區分，以便于后續分析，在采集時間快照時，對不同的數據類型進行標記，以作區分。聚類的準確性和精確度可以通過縮短時間快照的間隔時間進行提高。

對于靜態型數據集內隨機分布的靜態型數據，為了能夠發現任意形狀的靜態簇，提高聚類效果，本文選擇基于密度的DBSCAN[2]算法。由于靜態型數據的位置不再發生變化，因此只需進行一次聚類處理即可，對靜態型數據處理完畢之后，可以得到一組靜態簇SC。然后對移動數據進行處理分析，由于本節研究的問題只涉及一個移動型數據，因此從單個移動型數據與靜態型數據集的聚類問題就轉變成一個移動型數據歸屬哪個靜態簇的問題。

在每張時間快照下移動數據的位置都是不一樣的，因而對移動數據與靜態數據之間的相似度判斷不能簡單應用處理靜態數據之間相似度關系的方法進行處理。而是基于“共現”思想，采用定義3的Housdorff距離作為移動型數據與靜態簇之間的相似性度量標準并且結合時間屬性，根據判斷規則1綜合判斷移動型數據歸屬于哪個靜態簇。

判斷規則1給定一個移動數據m，對靜態數據集聚類處理過后的靜態簇集合SC={sc1,sc2,…,sck}，距離閾值δ，時間閾值kt，當移動數據m與?sc∈SC滿足以下條件時，則移動數據m∈sc，否則移動數據m為離群點。

1)在靜態簇集合SC中有一個靜態簇sc與移動數據m的距離不大于δ，表示為distH(sc,m)≤δ，其中?sc∈SC；

2)若滿足條件1)中移動數據m和靜態簇sc的持續時間不小于時間閾值kt，則將移動數據m歸屬于靜態簇sc。

判斷規則1中的時間閾值由人工設置，閾值設置的過長或過短都會導致錯誤的判斷，比如閾值取整個時間范圍的值，那么只有從開始到結束，在距離上一直相近的數據才能劃分為一類，那就失去了聚類分析的意義。假如閾值取為單位時間，每個單位時間內，距離相近都被劃分一類，不符合對混合數據聚類的劃分規則。

圖1 單移動數據與靜態數據集聚類示意圖Fig.1 Schematic diagram of single mobile data and static data set clustering

下面給出包含一個移動型數據與靜態型數據集的混合數據聚類的示例。如圖1所示，給定混合數據H，H包含有靜態型數據集S和一個移動型數據m，時間閾值設置為3，此處時間閾值為人工設定。首先對靜態型數據集S進行聚類處理后得到靜態簇集合SC={sc1,sc2}，然后對每張時間快照進行掃描，移動型數據m與各個靜態簇之間應用Housdorff距離進行相似性度量，圖中虛線代表了移動數據與靜態簇之間的距離小于距離閾值，并且持續時間不小于3個時間快照，因此在t3時刻，用實線將靜態簇sc1與移動數據圈在了一起，移動數據被劃分入了靜態簇sc1。

基于以上討論和分析以及判斷規則1,現在給出SMPSP(一個移動型數據與靜態型數據集)算法的主要思想：首先對靜態型數據集應用DBSCAN算法，對應算法第3～4步，當得到靜態簇SC={sc1,sc2,…,sck}之后，掃描每張時間快照，獲得每張時間快照上所有數據的位置分布和數據的類型，使用Housdorff距離度量移動型數據m與每個靜態簇sc之間的距離，若出現某個靜態簇sc與移動型數據m之間的距離小于給定距離閾值δ時，將其記錄下來，對應算法6～16步。然后重復上述步驟處理接下來的時間快照，并記錄下移動型數據與已有靜態簇之間的距離distH(sc,m)，并根據判斷規則1，對應算法的第7～11步，進行判斷移動型數據m與靜態簇sc之間的關系。

算法1 SMPSP

輸入：移動型數據m，靜態型數據集S={s1,s2,…,sz}，距離閾值δ，時間閾值kt，鄰域參數(ε,MinPts)，時間快照的張數p

輸出：聚類結果hc

//tmp的結構為(簇；簇出現次數,初值為0)

1.tmp←?

2.hc←? //最終結果簇集合

3.SC←? //靜態簇集合

4.SC←DBSCAN(S,ε,MinPts)

5.fori:=1top//從頭至尾遍歷時間快照

6. forj:=1tok// 遍歷每個靜態簇

//判斷靜態簇與移動型數據m是否滿足距離

//閾值的限制和與上一張時間快照內的靜態

//簇是否相同

7. if(distH(scj,m)≤δand

previous(tmp·sc)==scj) then

8.tmp←(scj,times+1)

9. if(tmp·times≥kt) then

10.hc←hc(i,(scj,m))

11.hc←hc(i,(SCscj))

12. end if

13. end if

14. else

15.tmp←?

16.hc←hc(i,SC)

17.end for

18.end for

19.returnhc

算法時間復雜度分析：根據文[18]得到步驟4調用DBSCAN算法的時間復雜度為O(z2)，z為靜態點的個數，步驟5～16之間為判斷移動型數據m的歸屬問題，只有一個for循環，因此步驟6～16的時間復雜度取決于靜態簇的個數k(k?z)，在整個算法中，還有步驟3的一個for循環遍歷整個時間快照。綜上所述，算法1的總時間復雜度為O(z2+pk))。

2.2 移動數據集與靜態數據集的聚類算法

當移動型數據不再單一時，包含一個移動型數據與靜態型數據集的混合數據聚類問題也就變成了包含移動型數據集與靜態型數據集的混合數據聚類問題，具體可描述為：給定一組包含移動型數據集M={m1,m2,…,my}，靜態數據集S={s1,s2,…,sz}的混合數據H，對混合數據H進行聚類分析。

由于移動型數據的增多，聚類問題復雜化，在整個聚類思想上依然與一個移動型數據與靜態型數據集一樣，采取“分而治之”的思想，但是在后續具體的聚類處理方法上有所不同。首先，針對移動型數據與靜態型數據同時存在的問題，采取對不同類型的數據進行標記的方法，以便后續的聚類處理。對于混合數據中的靜態數據集，采用基于密度的DBSCAN聚類算法，理由與2.1節中相同，在此不再贅述，通過對靜態型數據集的聚類處理，可以獲得一組靜態簇SC。對于混合數據中的移動數據集，不再采取對一個一個移動型數據和所有的靜態簇進行相似性度量，然后把一個一個移動型數據劃分到不同簇中的模式，因為在大量的移動型數據下，這么做計算量實在過于龐大，而且各種情況比較復雜，不便處理。本文提出下述方法，首先采取定義2的移動聚類方法對移動型數據集進行處理，獲得一組移動簇MC，然后通過對靜態簇與移動簇進行相似性判斷，進而獲得聚類劃分。

至此，在整個針對包含移動數據集與靜態數據集的混合數據的聚類問題處理中，我們得到了一組靜態簇和一組移動簇。因為移動簇由移動數據組成，因此移動簇必然也是隨著時間而進行移動的。所以在簇的層面上，移動簇與移動簇，移動簇與靜態簇之間發生聚集也是很有可能的。從移動數據集與靜態數據集的聚類問題轉變成了簇與簇的聚集問題，具體可描述為：給定歐式空間中，移動簇集合MC={mc1,mc2,…,mck}，靜態簇集合SC={sc1,sc2,…,scl} ，距離閾值δ，時間閾值kt，若滿足判斷規則2，則稱兩個簇發生了聚集。

判斷規則21)兩個簇之間的距離不大于距離閾值δ，即distH(mca,scd)≤δordistH(mca,mcb)≤δ，其中?mca,mcb∈MC，?scd∈SC。

2)滿足條件一的兩個簇的存在時間不小于時間閾值kt，即time(mca,mcb)≥ktortime(mca,scd)≥kt，其中?mca,mcb∈MC，?scd∈SC。

如圖2所示，設置時間閾值為3，在t1～t66張時間快照中，有3個移動型數據在t1～t3的3張時間快照中，距離相近，在t3時刻，這3個移動型數據組成了1個移動簇，虛線圈變成了實線圈，而在t4～t6時，移動簇與靜態簇sc2距離相近，并且持續時間一直到t6，所以在t6時刻，移動簇與靜態簇sc2，聚集成1個新簇。

基于以上討論和分析，給出算法MMPSP的主要思想：首先對靜態型數據集S應用DBSCAN算法，得到靜態簇，然后對每張時間快照上的移動型數據集M應用定義2的移動聚類方法，得到移動簇，對應算法的第8步。使用存儲結構HTMP用于存儲移動簇與靜態簇，存儲結構MTMP存儲移動簇與移動簇的出現聚集次數的情況，聚集次數的初始值為0。應用判斷規則2對移動簇與靜態簇之間的關系判斷，并將結果存儲到hc中，對應算法的第9～22步。再對移動簇與移動簇之間的關系做判斷，并將結果存儲到hc中，對應算法的第23～35步，最后返回聚類結果hc。

圖2 移動數據集與靜態數據集的聚類示意圖Fig.2 Clustering diagram of mobile datasets and static datasets

算法2 MMPSP

輸入：移動數據集M={m1,m2,…,my}，靜態數據集S={s1,s2,…,sz}，距離閾值δ，時間閾值kt，鄰域參數(ε,MinPts)，時間快照的張數p

輸出：聚類結果hc

1.MC←? //移動簇集合

2.HTMP←?

3.MTMP←?

4.hc←? //最終結果簇集合

5.SC←? //靜態簇集合

6.SC←DBSCAN(S,ε,MinPts)

7.fori:=1top//遍歷每張時間快照

//定義2

8.MC←moveCluster(δ,kt,M)

9. fora:=1 toSC.length

10. forb:=1 toMC.length

//判斷兩個簇距離和前一張時間快照內是否

//為這兩個簇

11. if(distH(sca,mcb)≤δand

previous(sc,mc)==(sca,mcb)) then

12.HTMP←

htmp((sca,mcb),times+1)

13. elseHTMP←

htmp((sca,mcb),0)

14. end for

15. end for

//篩選出HTMP中符合判斷規則2的簇

16.forj:=1 toHTMP.length

17. if(htmpj.times≥kt) then

18.hc←hc(i,(htmpj.(mc,sc))

19.hc←hc(i,(MChtmpj.mc))

20.hc←hc(i,(SChtmpj.sc)

21. end if

22.end for

23.fora:=1 toMC.length

24. forb:=1 toMC.length

//pervious()表示與上一張時間快照的數據

25. if(distH(mca,mcb)≤δand

previous(sc,mc)==(sca,mcb)) then

26.MTMP←

mtmp((mca,mcb),times+1)

27. elseMTMP←

mtmp((mca,mcb),0)

28. end for

29. end for

//篩選MTMP中符合判斷規則2的簇

30. forj:=1 toMTMP.length

31. if(mtmpj.times≥kt) then

32.hc←hc(i,mtmpj(mc1,mc2)

33.hc←hc(i,(MCmtmpj.(mc1,mc2))

34. end if

35.end for

36.end for

37.returnhc

算法時間復雜度分析：在第7步調用DBSCAN算法，根據文[18]可知，時間復雜度為O(z2)，z表示靜態型數據的個數，在利用定義2對移動型數據集的聚類問題上，根據文[10]應用的針對移動型數據的改進DBSCAN算法，時間復雜度也為O(y2)，y表示移動點的個數，在后續應用判斷規則2對簇之間的關系進行判斷時，用到了雙層for循環遍歷，因此時間復雜度度也為O(kl+k2)，其中k表示的是形成移動簇的個數，l表示的是形成的靜態簇的個數。最后加上遍歷整個時間快照。因此，總時間復雜度為O(z2+p(y2+kl+k2))。

3 實驗結果與分析

本文研究的是包含靜態型數據與移動型數據的混合聚類問題，將這些數據抽象在二維空間下進行研究，使用Housdorff距離度量數據之間的相似度，并結合“共現”思想，判斷是否相似而劃分為一類。

本文的數據是指包含移動型數據與靜態型數據的混合數據，目前已有的處理混合數據研究，是針對數值型數據和分類型數據的混合數據，而沒有針對數據狀態的混合，即對靜態型和移動型數據的混合。因此本文的對比實驗算法選擇了處理靜態型數據的SDPC[3]聚類算法和處理移動數據的TAD[19]聚類算法，作為對比算法進行對比實驗。

在對一個聚類算法進行評價時，通常會從F-meature指標和Silhouette指標進行評價，它們的取值范圍均為[0,1]，并且越接近1，說明效果越好。本文從F值指標與S值指標以及運行效率等方面評價算法聚類效果。

實驗的數據集采用真實的GPS軌跡數據(http://www.ccf.org.cn/sites/ccf/dashuju.jsp?contentId=2756825351305#大賽賽題)，選擇的是2012年11月1日北京市12 408輛出租車的GPS數據，每條數據包含了車輛標識、緯度、經度、海拔等信息，對于時間快照的粒度，本文設置為1 min，選取經緯度信息進行試驗。由于該數據集收集的僅為移動物體的信息，為了能夠實現對混合數據的處理，需要對數據集進行一些處理，生成靜態型數據，其過程如下：1)讀取數據集中的移動型數據的信息；2)隨機選取一些移動型數據；3)篩選出這些移動型數據的經緯度屬性信息；4)將這些剛開始移動時的經緯度信息作為其整個聚類過程的經緯度信息，不再發生變化，以代表靜態型數據。將這樣處理過后的數據作為實驗所用的混合數據。

此外，為對比算法性能，構造一組人工模擬數據集。人工模擬數據集的構造過程如下：1)在二維空間[0,l]×[0,l]，隨機生成一組ns個靜態數據；2)在二維空間中隨機添加nm個移動數據，并記錄下這時的二維空間中數據的位置分布，然后刪除移動數據；3)重復步驟2)n次，以模仿移動數據的移動狀態和采集n次時間快照數據。

經過以上步驟，在二維空間[0,l]×[0,l]中構造一個包含nsnm個混合數據集。

首先使用真實數據集進行實驗，將數據集中的出租車抽象為二維數據點，隨機選擇在數量上相等的移動型數據與靜態型數據，作為混合數據集，其中靜態型數據從移動數據轉化而來。實驗參數設置為：鄰域參數ε設置為100 m，MinPts=5，時間閾值kt=5 min，距離閾值δ=1 000 m。從真實數據集中隨機選取5組出租車24h的運行時間快照，這5組數據分別是2 000,4 000,6 000,8 000,10 000，其中每組數據由50%的移動型數據和50%的靜態型數據組成。然后各算法運行100次，取各算法的最短運行時間和最好的F指標值以及S指標值，如圖3、表1、表2所示。

圖3 運行時間對比圖Fig.3 Comparison of running time

從各算法的運行時間對比中，本文所提算法MMPSP算法和其他算法相比，運行時間要高于SDPC算法與TAD算法，但沒有高出很多。原因是MMPSP算法在識別數據的聚類方面，需要先分別對靜態型數據和移動型數據進行聚類處理形成聚類簇，然后再判斷形成移動簇與靜態簇，是否形成混合簇。通過觀察表1的F指標值數據對比表與表2的S指標值數據對比表，得出本文所提算法要好于只處理一種狀態類型的聚類算法，因為在本文的混合數據中移動數據與靜態數據各占一半，而SDPC算法與TAD算法只能識別出其中一半類型的數據，另一半類型數據無法進行識別和聚類處理，所以聚類效果較差，得到的各個指標值低于本文所提算法。

表1 真實數據集F指標值對比表Tab.1 Comparison of real dataset F indicator values

表2 真實數據集S指標值對比表Tab.2 Comparison of real dataset S indicator values

再使用人工模擬生成仿真混合數據集進行實驗，仿真混合數據包含1 000張時間快照的數據，一共有5組數據，每組有1 000，2 000，3 000，4 000，5 000的數據量，并且移動型數據與靜態型數據各占50%，測試仿真混合數據與真實數據集對聚類效果的評價標準相同，也是從F指標與S指標等方面進行實驗對比。從圖4的仿真數據運行時間對比圖，可以得出與真實數據相似的結論，即本文所提算法運行時間要略高于對比實驗算法。從表3的F指標值對比表和表4的S指標值對比表，也可以看出本文所提算法相對于只能處理一種數據類型的算法，聚類效果要好一些。

圖4 人工仿真數據運行時間對比圖Fig.4 Simulation data running time comparison chart

表3 仿真數據F指標值對比表Tab.3 Comparison of simulation data F indicator values

表4 仿真數據S指標值對比表Tab.4 Comparison of simulation data S indicator values

在前述實驗中，顯示出了本文所提MMPSP算法比只能處理單一類型數據的算法，在處理混合數據時取得的聚類效果要好。在實驗開始處已經提到目前還沒有針對混合數據進行聚類處理的研究，為了進一步證明MMPSP算法的合理性和有效性，本文提出一個新的可以處理混合數據的實驗算法RG算法進行對比實驗，該算法由一個處理靜態數據的算法RNN-DBSCAN[20]算法和一個處理移動數據的算法GR+[10]構成。在實驗過程中，每張時間快照內的靜態型數據使用RDD-DBSCAN算法處理，移動型數據則使用GR+方法進行處理。

此外，為更好的衡量聚類效果，增加一個聚類評價指標，即聚類精度Accuracy。

在真實數據集上進行實驗，實驗參數設置與之前相同。選取5組數據進行對比實驗，實驗數據信息與前述的真實數據實驗數據信息相同，為避免冗余，不再贅述。將這5組數據分別進行多次實驗，取MMPSP算法與RG算法的最好聚類結果進行比較。為更加清晰地對比實驗結果，將各指標值列于同一個表格中，如表5～8所示。表5～8展示了MMPSP算法與RG算法在不同的數據量下F指標值，S指標值和聚類精度Acc的對比結果。通過觀察可以發現，隨著數據的增多，本文所提MMPSP算法與RG算法不論是在F值、S值以及聚類精度Acc值方面都基本趨于穩定。在F值方面，MMPSP算法穩定在71%～74%，RG算法則穩定在70%～73%，具體到每組數據時，MMPSP算法均高于RG算法。S值方面，MMPSP算法大致穩定在67.9%～70.0%，RG算法則大致穩定在65.1%～68.0%，在每組數據對比下，MMPSP算法要高于RG算法。在Acc值上也呈現出與F值和S值相同的情況。結合表8的時間可知，雖然本文所提MMPSP算法時間消耗上要略高于RG算法，這是因為MMPSP算法需要處理不同類型數據之間的關系，所以導致時間消耗略有升高。雖然時間上消耗要多一些，但是在聚類效果上好于RG算法。

表5 真實數據集F指標對比Tab.5 Comparison of real dataset indicator

表6 真實數據集S指標對比Tab.6 Comparison of real dataset S indicator

表7 真實數據集多組數據各指標對比Tab.7 Comparison of real dataset Acc indicator

表8 真實數據集耗時(秒)對比Tab.8 Comparison of real dataset time(s) indicator

綜上所述，本文所提MMPSP算法與只能處理單一數據類型的SDPC算法與TAD算法進行了多組實驗對比，顯示出了MMPSP算法可以有效針對混合數據進行處理。為進一步證明本文所提算法的合理性和有效性，提出了對比實驗算法RG算法。此外，增加新的聚類評價指標聚類精度Acc值，多方面衡量聚類效果，實驗結果表明，本文所提算法對混合數據的聚類處理具有良好的效果。

4 結 語

現有的聚類算法對單一數據類型的數據進行聚類處理可以得到良好的聚類效果和準確率，對混合數據類型的聚類效果則較差。本文通過對包含移動型數據與靜態型數據的混合數據的分析和討論，提出MMPSP算法，并通過實驗證明其處理混合數據的聚類時具有良好的效果。但時間復雜度略高，下一步將從尋求既可以有效記錄數據信息，又不會導致時間復雜度升高進行優化。