顧洪博，張繼懷

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

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

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

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

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

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

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

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

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

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

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

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

簇中心ci的計算公式為

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

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

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

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

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

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

3 實驗及應(yīng)用

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

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

表1 ARI與最大移動距離的關(guān)系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算法首先要對數(shù)據(jù)不確定區(qū)域進行離散化，則需要時間較長和聚類過程較大;PDBSCAN算法通過R樹索引和概率閥值索引預(yù)先對不滿足要求的對象進行剔除，因此提高了聚類過程的效率。但PDBSCAN算法簡便性較高于FDBSCAN算法。兩種算法需要計算概率核心對象、概率密度可達和概率密度連續(xù)等數(shù)值。但前者是與0.5進行比較，后者是用戶根據(jù)自己的聚類來設(shè)置閥值，故實驗結(jié)果會與閥值有關(guān)。

3.2 基于劃分的聚類實驗

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

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

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

3.3 在教學管理實際中的應(yīng)用

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

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

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

4 結(jié)束語

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

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

[2]楊小兵.聚類分析中若干關(guān)鍵技術(shù)的研究[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]許華杰，李國徽，楊 兵，等.基于密度的不確定性數(shù)據(jù)概率聚類[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，F(xiàn)REW 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.