不確定性數據的聚類分析研究及應用

顧洪博，張繼懷

(1.東北石油大學計算機與信息技術學院，黑龍江大慶163318;2.大慶市讓胡路區政府，黑龍江大慶163712)

近年來，隨著數據采集、處理技術深入，不確定性數據受到越來越多的重視。諸如經濟、軍事、金融等領域的應用中，數據的不確定性普遍存在且至關重要。傳統的數據管理技術卻無法有效管理不確定性數據，研發實用的不確定性數據管理技術是當今熱點。不確定性數據來源[1]存在原始數據不準確;使用粗粒度數據集合，查詢結果存在不確定性;隱私保護;缺失值。

聚類是按照某個特定標準把一個數據分割成不同的類或簇，使得類內相似性盡可能的大，同時類間的差異性也盡可能的大。也就是說，聚類后同一類別的數據盡可能的聚集在一起，而不同的數據盡量分離。聚類分析是進行數據分析、數據挖掘、模式識別等的重要研究內容之一。現有的聚類算法大致有[2]劃分、密度、層次法等。

1 基于密度的不確定性聚類分析

基于密度的算法從數據對象的分布密度出發，把密度足夠大的區域連接起來，從而可以發現任意形狀的類。此類算法除了可以發現任意形狀的類，還能夠有效去除噪聲。常見的基于密度的聚類算法有DBSCAN、OPTICS。在計算對象的距離時因為不確定性對象有概率屬性，可能會影響對象間的距離。因此提出距離密度函數P(o，o')表示元組o和o＇間的距離密度函數，則o和o＇間的距離在(a，b)之間的概率和距離分布函數 P(a

由于DBSCAN聚類方法具有適用于各種形狀簇、對噪聲和離群點不敏感等優良特性，Kriegel提出FDBSCAN算法[3]。該算法在對對象的不確定區間進行離散化抽樣計算后，再計算得到的核心對象概率和密度可達概率，若核心對象概率＞0.5，則該對象是核心對象，否則不是核心對象;若密度可達概率＞0.5，則是可達密度區。該算法能對任意形狀的不確定性數據類聚類，并且不易受噪聲干擾。但由于對移動對象的離散化抽樣，使該算法的計算量較大，該算法需要用戶確定輸入參數，如ε，p。一般用戶對參數的設置不夠專業，并且該算法對參數值較敏感，參數值的小變化會導致大差異的聚類結果。

同年，Kriegel又提出了 FOPTICS 算法[4]。該算法首先要計算核心距離和可達距離。這是對FDBSCAN的擴展。許華杰提出采用不確定性數據索引技術、基于密度的不確定性數據概率聚類方法—PDBSCAN[5]。首先重新定義了對象的(ε，ρ)鄰居，記為

式中ε－距離閥值;p－概率閥值;P(dis(oj，oi)≤ε≥p－oi和oj之間的距離小于ε的概率大于p。

該算法的特點:(1)對概率核心對象和概率密度可達的計算是利用兩個不確定性對象之間的距離的最小值和最大值作為限定范圍，并考慮不確定性在該范圍上的概率分布。(2)算法在判斷概率核心對象和概率密度可達時允許用戶設置概率閥值p;(3)通過R樹和概率閥值索引PTI提高計算效率。但算法中概率閥值p的選取對聚類結果有很大影響。另外，MBR的x－bound構造過程會受p的影響，對MBR的壓縮就越精細，裁剪效果就更好。但是，相應地會增加R樹節點保存xbound信息的存儲代價。

2 基于劃分的不確定性聚類分析

在確定性數據挖掘中，劃分算法中最常用的是k－means算法。2005年，文獻[6]提出基于k－means算法不確定性數據聚類分析 －UK－means算法。基本思想與k－means相似:各數據點將被距離最近的簇吸收。考慮在聚類過程中的不確定性，提出的目標函數是基于平方誤差和的期望值最小的聚類算法E(SSE)—expected(sum of squared errors)。目標函數計算公式是

式中||.||－數據對象xi到簇中心ci的度量距離;f(xi)－數據對象xi的概率密度函數(pdf，probability density function)。

簇中心ci的計算公式為

作者認為UK－means算法和傳統的K－means算法的最大差別是對算法中距離和簇的計算上。提出了一個基于移動對象的ED計算方法。在移動對象從(a，b)到(c，d)，質心為(p，q)。則

Ngai等在UK －means算法［7］中將 ED 表示成

式中fi(x)－不確定性數據對象x的pdf;d(x，pci)－x與質心pi間的距離。

為了進行聚類，就要計算每一個數據對象的ED，計算量相當龐大，因此提出將數據點可能出現的區域用最小邊界矩形(MBR)描述，通過MMD(min－max－dist，最小最大距離)設計剪枝策略:若 MinDistij＞，則 ED(oi，pi)不用計算，否則 ED(oi，pi)需要計算，其中 MinDistij是到簇質心pi的最小距離=min，ED(oi，pi))。此方法提高了計算效率。為了進一步計算，作者提出了4種方法來對范圍進行估計，分別是 Ucs，Upre，Lcs，Lpre，這4種方法可以單獨使用，也可以結合使用。但未給出具體的ED的計算函數或公式。

Cormode對前面的期望值進行實際計算[8]，提出采用一個函數來計算不確定的點到任意一個中心的距離的期望值，然后再運用傳統的聚類方法進行計算。

基于劃分的聚類分析算法，對于一個給定的n個數據對象的數據集，采用目標函數最小化的策略，通過把數據分成k個組，每個組為一個簇。可以看出，這種聚類算法適用于發現非凸面形狀的簇，或者大小差別很大的簇。但它對于噪音和孤立點數據是敏感的。并且，對于初始聚類中心的選擇會影響這類算法的執行效果。

3 實驗及應用

3.1 基于密度的聚類分析實驗

實驗采用數據集來自美國地理信息基準數據集 SEQUOIA 2000[9]，p=0.8，比較的性能指標是聚類的準確度和效率。為了檢驗算法的效率，設對象的最大移動距離d=50 m，采用PDBSCAN和FDBSCAN聚類算法分別對具有不同移動對象數的數據集進行聚類。聚類相似度指標是Adjusted Rand Index(ARI)[10]，ARI 的值越大，說明兩個聚類結果越相似，基于密度的聚類過程中ARI的值如表1所示。

表1 ARI與最大移動距離的關系Tab.1 The connection between adjusted rand index and the max－distance of mobile object

從表1中可看出，(1)PDBSCAN聚類算法的ARI高于FDBSCAN聚類算法。ARI的值與移動距離成反比。反之，當聚類中距離越小則移動對象的相似度越大，故ARI越大。(2)PDBSCAN算法的效率高于FDBSCAN算法。主要因為FDBSCAN算法首先要對數據不確定區域進行離散化，則需要時間較長和聚類過程較大;PDBSCAN算法通過R樹索引和概率閥值索引預先對不滿足要求的對象進行剔除，因此提高了聚類過程的效率。但PDBSCAN算法簡便性較高于FDBSCAN算法。兩種算法需要計算概率核心對象、概率密度可達和概率密度連續等數值。但前者是與0.5進行比較，后者是用戶根據自己的聚類來設置閥值，故實驗結果會與閥值有關。

3.2 基于劃分的聚類實驗

基于劃分的聚類方法與基于密度的聚類算法不需要比較。在一個100×200D區域使用基于劃分的聚類方法，n=1 000，k=20，目標函數平方誤差和＜10－6。聚類相似度指標是ARI。算法采用的是文獻[6]的算法。

表2 ARI與劃分距離的關系Tab.2 The connection between adjusted rand index and the partition－based distance

從表2中可以看出，在不確定性數據中，ARI值與移動對象的移動距離有關。當對象間的距離越大，則聚類相似度就越小;反之，對象間的距離越小，則聚類相似度就越大。

3.3 在教學管理實際中的應用

在教學管理過程中，為準確掌握在校學生的成績狀況，常用問卷、測試、作業、老師或專家點評等方法。從這些方法整理出的數據是不完整的、模糊的、隨機的、大量的，這里可以稱為不確定性數據。教務管理者要從這些數據中挖掘有用的信息和知識，直觀表征學生學習的總體狀況，為教學和教學管理提供可靠依據。一般，以大學英語為例，數據來源于學生各個學期大學英語課堂表現10次、作業5次、模擬考試3次、期末考試成績和各次參加大學英語四、六級的成績。本文采用基于劃分的不確定性數據聚類分析對教務管理中的數據進行分析，保證教學管理的準確性。此次實驗中n=1 000，聚類簇數k=5，學生各次的成績的變化我們成為移動距離，目標函數平方誤差和p＜10－6，聚類相似度指標是 ARI。

表3 ARI與移動距離的關系Tab.3 The connection between adjusted rand index and the mobile distance－based

從表3中可以看出，在不確定性數據中，ARI的值與學生成績的移動距離有關。當學生成績的移動距離越大，則聚類相似度就越小;反之，學生成績的移動距離越小，則聚類相似度就越大。并把算法在教學管理實際中的應用。

4 結束語

本文給出基于不確定性數據的聚類算法，分別就基于劃分的和基于密度的聚類算法給出目前基本思想、優缺點，并就基于劃分的和密度的算法進行對比實驗，在教學管理實際中進行應用，可以為教學管理提供有力幫助。

[1]周傲英，金澈清，王國仁，等.不確定性數據管理技術研究綜述[J].計算機學報.2009，32(1):1 －16.

[2]楊小兵.聚類分析中若干關鍵技術的研究[D].杭州:浙江大學計算機學院.2005.

[3]KRIEGEL H P，PFEIFLE M.Density－based clustering of uncertain data[C]//.Proceedings of the 11th ACM SIGKDD International Conference on Knowledge Discovery in Data Mining.Chicago，2005:672－677

[4] KRIEGEL H P，PFEIFLE M.Hierarchical density －based clustering of uncertain data[C]//.Proceedings of 5th International Conference on Data Mining.Houston，2005:689－692.

[5]許華杰，李國徽，楊 兵，等.基于密度的不確定性數據概率聚類[J].計算機科學，2009，36(5):68－72.

[6]M CHAU R.CHENG B.KAO B，et al.Uncertain data mining:An example in clustering location data[C]//.In Pacific Asia Conferenceon Knowledge Discovery and Data Mining，2005:199 －204.

[7]NGAI W K，KAO B，CHUI C K，et al.Efficient clustering of uncertain data[C]//.Proceedings of the 6th International Conference on Data Mining.Hong Kong，2006:436－445.

[8] CORMODE G，MCGREGOR A.Approximation algorithms for clustering uncertain data[C]//.Proceedings of the 27th ACM SIGMOD－SIGACT－SIGART Symposium on Principles of Database Systems.Vancouver，2008:191－200.

[9]STONEBRAKER M，FREW J，GARDELS K，et al.The SEQUOIA 2000 Storage Benchmark[C]//.The 1993 ACM SIGMOD International Conference on Management of Data.Washington，1993:56 －98.

[10]YEUNG K，RUZZO W.An empirical study on principal componen analysis for clustering gene expression data[J].Bioinformatics，2001，17(9):763 －774.