基于離群因子的不確定數(shù)據(jù)生成算法

劉 鋼, 唐東凱, 王紅梅, 胡 明

(1. 長(zhǎng)春工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院, 長(zhǎng)春 130012； 2. 長(zhǎng)春工程學(xué)院 計(jì)算機(jī)技術(shù)與工程學(xué)院, 長(zhǎng)春 130012)

在對(duì)不確定數(shù)據(jù)進(jìn)行分析、融合與挖掘前, 首先要獲得不確定數(shù)據(jù). 目前, 現(xiàn)有的不確定數(shù)據(jù)主要從兩方面生成不確定數(shù)據(jù)集： 1) 從模擬數(shù)據(jù)集出發(fā), 由于沒(méi)有真實(shí)數(shù)據(jù)集, 所以先人工產(chǎn)生確定的模擬數(shù)據(jù)集, 再采用相應(yīng)的轉(zhuǎn)化策略生成不確定數(shù)據(jù)； 2) 從真實(shí)數(shù)據(jù)集出發(fā), 如UCI機(jī)器學(xué)習(xí)數(shù)據(jù)集, 根據(jù)生成算法得到不確定數(shù)據(jù)集. 對(duì)于第一種方式, Chau等[1]首先在100×100的二維空間中隨機(jī)生成一系列點(diǎn), 然后對(duì)每個(gè)點(diǎn)選擇一個(gè)不確定模型產(chǎn)生不確定性數(shù)據(jù); 文獻(xiàn)[2-4]在此基礎(chǔ)上增加了一個(gè)大小隨機(jī)且位置固定的矩形MBR(minimum bounding rectangle), 然后將不確定對(duì)象均勻分布在MBR內(nèi), 并將MBR內(nèi)的每個(gè)樣本點(diǎn)隨機(jī)產(chǎn)生一個(gè)概率值, 使概率值之和為1. 對(duì)于第二種方式, 金萍等[5]先在UCI數(shù)據(jù)集Glass,Iris,Wine的每一維上設(shè)置一個(gè)擾動(dòng)區(qū)間, 然后使用擾動(dòng)因子β(0<β<1)控制每個(gè)數(shù)據(jù)對(duì)象對(duì)應(yīng)的MBR大小; 文獻(xiàn)[6-7]在確定數(shù)據(jù)集上添加了一個(gè)不確定數(shù)據(jù)生成策略, 為每個(gè)數(shù)據(jù)源中的樣本數(shù)據(jù)定義了一個(gè)概率密度函數(shù)fi, 使每個(gè)樣本對(duì)象由一組樣本點(diǎn)表示, 每個(gè)樣本點(diǎn)都對(duì)應(yīng)一個(gè)概率值, 且概率之和為1; 文獻(xiàn)[8-10]使用不同的分布函數(shù)作為概率密度函數(shù)生成不確定數(shù)據(jù).

目前不確定數(shù)據(jù)集的生成方法主要存在兩方面的不足： 1) 幾乎所有的不確定數(shù)據(jù)生成算法都未考慮原始數(shù)據(jù)集的數(shù)據(jù)分布特征, 如數(shù)據(jù)集中存在離群點(diǎn), 離群點(diǎn)的存在會(huì)影響最后的挖掘結(jié)果； 2) 在上述生成方法中, 存在擾動(dòng)因子β(0<β<1), 且其值在整個(gè)算法過(guò)程中固定不變, 不能很好地反映數(shù)據(jù)的分布特征. 為了解決目前不確定數(shù)據(jù)集生成方法存在的不足, 本文通過(guò)分析不確定數(shù)據(jù)的模型, 針對(duì)屬性級(jí)不確定數(shù)據(jù), 先通過(guò)引入局部離群點(diǎn)檢測(cè)算法計(jì)算每個(gè)對(duì)象的離群因子, 然后使用離群因子的值產(chǎn)生擾動(dòng)因子, 自動(dòng)控制MBR的大小, 提出了AC-UDGen(attribute level continuous uncertain data set generation algorithm)算法. 實(shí)驗(yàn)結(jié)果表明, AC-UDGen算法生成的不確定數(shù)據(jù)集在聚類時(shí)具有更好的聚類效果.

1 不確定數(shù)據(jù)模型

不確定數(shù)據(jù)模型的表示方式有多種, 較常見(jiàn)的是概率分布模型[11-12]. 概率分布模型由一個(gè)[0,1]間的概率值及確定的元組屬性值表示. 在實(shí)際應(yīng)用中, 將不確定性數(shù)據(jù)分為存在級(jí)不確定性(也稱元組不確定性)和屬性級(jí)不確定性(也稱值不確定性)兩種.

1) 存在級(jí)不確定性. 一個(gè)事件在每次測(cè)試中是否發(fā)生都以一定的可能性存在, 而這個(gè)可能性的大小即為對(duì)應(yīng)該事件發(fā)生的概率, 存在級(jí)不確定性是指一個(gè)數(shù)據(jù)對(duì)象存在與否用一個(gè)概率值的大小表示. 例如, 數(shù)據(jù)庫(kù)中有兩個(gè)不確定對(duì)象A和B, 其中A存在的概率為65%, 而B(niǎo)存在的概率為70%.A和B之間可能是相互獨(dú)立也可能存在依賴關(guān)系.

2) 屬性級(jí)不確定性. 數(shù)據(jù)對(duì)象是確定存在的, 但其屬性值具有不確定性. 一般采用概率值或概率密度函數(shù)表示屬性的不確定性[13]. 例如, 在位置服務(wù)中, 數(shù)據(jù)對(duì)象屬性A存在的情況是：i位置概率35%,k位置概率53%,j位置概率12%, 可見(jiàn)屬性A的值是不確定的, 但其所有可能值的概率之和為1.

2 AC-UDGen算法

針對(duì)屬性級(jí)不確定數(shù)據(jù), 王建榮[14]進(jìn)一步將屬性級(jí)不確定性數(shù)據(jù)分為屬性級(jí)離散不確定性和屬性級(jí)連續(xù)不確定性數(shù)據(jù). 本文主要考慮屬性級(jí)連續(xù)不確定性數(shù)據(jù), 定義為： 在m維空間m中, 給定不確定數(shù)據(jù)集O={o1,o2,…,on}和概率密度函數(shù)fi:m→, 如果將不確定數(shù)據(jù)對(duì)象ou的屬性Ai值記為ou[Ai], 用概率密度函數(shù)fi表示, 且滿足

則屬性Ai稱為不確定連續(xù)屬性.

由定義可知, 連續(xù)屬性級(jí)不確定數(shù)據(jù)的概率密度函數(shù)滿足一定的分布, 如均勻分布、高斯分布等. 針對(duì)屬性級(jí)連續(xù)不確定數(shù)據(jù), 目前的生成算法[1-10]都未考慮到原始數(shù)據(jù)的分布特征, 如離群點(diǎn)等. 按目前算法進(jìn)行轉(zhuǎn)化時(shí), 不確定數(shù)據(jù)集的離群點(diǎn)數(shù)量會(huì)相應(yīng)增加, 從而對(duì)不確定數(shù)據(jù)的挖掘帶來(lái)困擾; 此外, 在不確定數(shù)據(jù)生成過(guò)程中引入的擾動(dòng)因子是固定不變的, 不能很好地體現(xiàn)數(shù)據(jù)的分布特征, 因此, 本文提出一種AC-UDGen算法, 該算法分為4步: 1) 在輸入的確定數(shù)據(jù)集上運(yùn)行基于密度的局部離群點(diǎn)檢測(cè)-LOF算法[15], 計(jì)算出每個(gè)點(diǎn)的離群因子； 2) 由離群因子的大小判斷出該點(diǎn)周圍的密度大小, 并根據(jù)離群因子產(chǎn)生擾動(dòng)因子； 3) 將擾動(dòng)因子作為參數(shù), 計(jì)算MBR值的大??； 4) 輸出不確定數(shù)據(jù)集. AC-UDGen算法流程如圖1所示.

圖1 AC-UDGen算法流程Fig.1 Flow chart of AC-UDGen algorithm

2.1 計(jì)算離群因子

離群因子是指數(shù)據(jù)集中每個(gè)對(duì)象的偏離程度, 根據(jù)每個(gè)對(duì)象的偏離程度可確定該對(duì)象是否為離群點(diǎn). 實(shí)質(zhì)上一個(gè)數(shù)據(jù)對(duì)象的偏離程度正是數(shù)據(jù)對(duì)象分布的表達(dá), 偏離程度越高說(shuō)明該對(duì)象周圍數(shù)據(jù)對(duì)象越少, 就最可能是離群點(diǎn); 而偏離程度越低, 則該數(shù)據(jù)對(duì)象分布在較集中的局部區(qū)域中, 就不會(huì)是離群點(diǎn). 本文采用LOF算法計(jì)算離群因子, 設(shè)D表示數(shù)據(jù)集,o,p分別為數(shù)據(jù)集D中的對(duì)象,k為正整數(shù), 則離群因子的計(jì)算過(guò)程可分為3步, 下面以對(duì)象p為例進(jìn)行說(shuō)明.

1) 構(gòu)建對(duì)象p的第k距離鄰域. 對(duì)象p的第k距離鄰域是指小于等于對(duì)象p最近的第k距離內(nèi)的所有對(duì)象組成的集合. 實(shí)際上該集合反映了數(shù)據(jù)對(duì)象的偏離程度. 如果該集合較大, 說(shuō)明該對(duì)象的第k距離鄰域較大, 則它的偏離程度就較大; 反之, 若集合較小, 則偏離程度就小. 其計(jì)算公式為

Nk(p)={q∈D{p}|d(p,q)≤k-dis(p)},

(1)

其中:d(p,q)表示數(shù)據(jù)對(duì)象p和數(shù)據(jù)對(duì)象q之間的歐氏距離；k-dis(p)表示對(duì)象p的第k近的距離,k為正整數(shù).

2) 計(jì)算對(duì)象p的局部可達(dá)密度. 對(duì)象p的局部可達(dá)密度是指對(duì)象p的Nk(p)內(nèi)所有對(duì)象平均可達(dá)密度的倒數(shù), 計(jì)算公式為

(2)

如果至少有k個(gè)對(duì)像和p有相同的坐標(biāo)值, 卻是不同的數(shù)據(jù)對(duì)象, 則式(2)的分母將趨近于0, 而對(duì)象p的局部可達(dá)密度將趨于∞; 相反, 如果數(shù)據(jù)對(duì)象p距離聚類簇較遠(yuǎn), 則其Nk(p)領(lǐng)域內(nèi)所有對(duì)象的可達(dá)距離之和就會(huì)較大, 相應(yīng)的lrdk(p)值則較小.

3) 計(jì)算對(duì)象p的離群因子. 結(jié)合式(1)和式(2)計(jì)算p的離群因子, 計(jì)算公式為

(3)

由式(3)可知, LOFk(p)的大小反映了數(shù)據(jù)對(duì)象p的第k距離范圍內(nèi)空間點(diǎn)的平均分布密度, 易見(jiàn), 若p的局部可達(dá)密度越小,p的Nk(p)內(nèi)對(duì)象可達(dá)密度越大, 則對(duì)象p的LOF值越大. 即一個(gè)對(duì)象的LOF值越大, 則該對(duì)象是離群點(diǎn)的概率越大.

由式(1)～(3)可知, 離群因子的值反映了一個(gè)數(shù)據(jù)對(duì)象與其他對(duì)象間的分布關(guān)系, 并可根據(jù)其值的大小刪除異常點(diǎn), 因此, 本文使用LOF的值經(jīng)過(guò)適當(dāng)處理作為不確定數(shù)據(jù)生成算法的參數(shù).

2.2 計(jì)算擾動(dòng)因子

結(jié)合離群因子確定β(0<β<1)的值. 在離群因子計(jì)算過(guò)程中, 如果一個(gè)對(duì)象的LOF值越大, 則其離群概率越大, 周圍的密度就較小, 落在其周圍的數(shù)據(jù)對(duì)象就較稀疏, 在AC-UDGen算法中, 其MBR值較大; 相反, 若一個(gè)對(duì)象的LOF值越小, 則該對(duì)象周圍區(qū)域就有更多的數(shù)據(jù)對(duì)象, 即落在其周圍的對(duì)象較密集, 在AC-UDGen算法中, 其MBR值較小. 所以, 本文使用下列公式計(jì)算擾動(dòng)因子的值：

(4)

其中:βi表示第i個(gè)元組的擾動(dòng)因子; LOFi表示每個(gè)對(duì)象的離群因子.

2.3 計(jì)算MBR值的大小

在原始數(shù)據(jù)集上, 先計(jì)算出每個(gè)數(shù)據(jù)對(duì)象的離群因子, 然后計(jì)算出每個(gè)對(duì)象的擾動(dòng)因子β, 最后在數(shù)據(jù)對(duì)象的每一維上設(shè)置一個(gè)擾動(dòng)區(qū)間,Ih=β×max_length, max_length表示所有對(duì)象在該維上的最大距離, 并使用擾動(dòng)因子β控制每個(gè)數(shù)據(jù)對(duì)象對(duì)應(yīng)的MBR值, 在每個(gè)MBR中隨機(jī)分布服從同一分布的固定數(shù)目的數(shù)據(jù)對(duì)象.

2.4 算法描述

AU-UDGen算法.

輸入: 確定數(shù)據(jù)集D,S(每條原始記錄所生成的不確定對(duì)象的個(gè)數(shù));

輸出: 不確定數(shù)據(jù)集U.

1) 在D上運(yùn)行LOF算法, 根據(jù)式(3)計(jì)算出每個(gè)數(shù)據(jù)對(duì)象的離群因子LOFi;

2) 根據(jù)LOFi及式(4), 計(jì)算出每個(gè)對(duì)象的擾動(dòng)因子;

3) ① 對(duì)于數(shù)據(jù)集的每一維j;

② 對(duì)于數(shù)據(jù)集的每個(gè)對(duì)象i;

4) ① 對(duì)于每個(gè)數(shù)據(jù)對(duì)象i;

② repeat;

③ 對(duì)于每一維j;

④ 根據(jù)該維確定的值, 隨機(jī)生成滿足某個(gè)分布的不確定值Uij;

⑥ until每個(gè)數(shù)據(jù)對(duì)象都生成S條記錄；

5) 輸出不確定數(shù)據(jù)集U.

3 實(shí)驗(yàn)結(jié)果分析

本文使用Python語(yǔ)言實(shí)現(xiàn)所提算法及涉及的相關(guān)算法, 版本為Python2.7.0. 運(yùn)行環(huán)境為： Intel(R) Core(TM) i5-3470 CPU, 3.20 GHz, 8.00 GB內(nèi)存, 操作系統(tǒng)為Windows8.1系統(tǒng), 64位.

實(shí)驗(yàn)分為3部分: 第一部分驗(yàn)證AC-UDGen算法的準(zhǔn)確率； 第二部分驗(yàn)證不同概率密度函數(shù)對(duì)聚類結(jié)果的影響； 第三部分驗(yàn)證AC-UDGen算法的時(shí)間效率. 實(shí)驗(yàn)整體框架如圖2所示. 由圖2可見(jiàn), 算法共分為5個(gè)過(guò)程, 由1)輸入確定數(shù)據(jù)集, 由2)運(yùn)行本文算法, 將其變?yōu)?)中不確定數(shù)據(jù)集, 然后再統(tǒng)一使用4)中UK-means聚類算法進(jìn)行聚類, 對(duì)結(jié)果使用5)中的評(píng)價(jià)標(biāo)準(zhǔn), 分別從準(zhǔn)確率和時(shí)間兩個(gè)維度驗(yàn)證本文算法的有效性.

圖2 實(shí)驗(yàn)整體框架Fig.2 Overall framework of experiment

1) 選取UCI機(jī)器學(xué)習(xí)數(shù)據(jù)集中的4種數(shù)據(jù)集作為原始確定數(shù)據(jù)集, 數(shù)據(jù)集屬性列于表1.

2) 對(duì)確定數(shù)據(jù)集, 運(yùn)行本文提出的AC-UDGen算法, 將其變?yōu)椴淮_定數(shù)據(jù);

3) 得到不確定數(shù)據(jù)集;

4) 在不確定數(shù)據(jù)集上統(tǒng)一使用文獻(xiàn)[3]提出的不確定聚類算法UK-means進(jìn)行聚類；

(5)

表1 UCI實(shí)驗(yàn)數(shù)據(jù)集

F-measure針對(duì)的只是聚類結(jié)果, 而內(nèi)部評(píng)價(jià)標(biāo)準(zhǔn)考慮到了聚類過(guò)程, 類內(nèi)距表示聚類簇之間的緊密度, 類間距表示聚類簇間的分離程度. 類內(nèi)距的計(jì)算公式為

(6)

類間距的計(jì)算公式為

(7)

其中, D(o,o′)表示數(shù)據(jù)對(duì)象o和o′的期望距離.

令Q(C)=inter(C)-intra(C)作為內(nèi)部評(píng)價(jià)標(biāo)準(zhǔn),intra(C)越小,inter(C)越大, 則聚類質(zhì)量Q(C)越好. 由于intra(C)和inter(C)的值在[0,1]內(nèi), 則Q的范圍是[-1,1].

3.1 驗(yàn)證AC-UDGen算法的準(zhǔn)確率

采用文獻(xiàn)[6]和文獻(xiàn)[8]提出的不確定數(shù)據(jù)生成算法, 分別記為ABRAC算法和UK-medoids算法作為對(duì)比算法. 涉及的參數(shù)設(shè)S=100(S表示每個(gè)MBR內(nèi)的樣本數(shù)),β=0.5. 對(duì)比算法只取其不確定生成算法, 聚類過(guò)程統(tǒng)一使用UK-means算法進(jìn)行聚類. 概率密度函數(shù)采用uniform,normal,exponential,Laplace 4種分布. 在4種數(shù)據(jù)集上分別進(jìn)行10次獨(dú)立實(shí)驗(yàn), 記錄每次的實(shí)驗(yàn)結(jié)果, 并求出均值進(jìn)行對(duì)比, 使用F-measure作為評(píng)價(jià)標(biāo)準(zhǔn).

在不確定數(shù)據(jù)生成過(guò)程中, ABRAC算法首先在原始數(shù)據(jù)集的每一維上設(shè)置一個(gè)擾動(dòng)區(qū)間Ih=0.1×max_length, 其中max_length表示所有點(diǎn)在該維上的最大距離, 然后使用擾動(dòng)因子β(0<β<1)控制每個(gè)數(shù)據(jù)對(duì)象對(duì)應(yīng)的MBR值大小, 且每個(gè)MBR內(nèi)服從同一分布.

從上述兩種算法的生成過(guò)程可見(jiàn), 在整個(gè)聚類過(guò)程中,β一旦選中就不再改變, 即β是固定不變的(UK-medoids中隨機(jī)選擇后也不再改變), 也即每個(gè)不確定數(shù)據(jù)對(duì)象的分布區(qū)域是確定的, 并未反映出數(shù)據(jù)對(duì)象周圍密度空間的分布情況, 如數(shù)據(jù)對(duì)象分布較密集, 則MBR的值也應(yīng)該變小, 但由于β不變,Ih就不變, 導(dǎo)致MBR值也不變. 反之, 如果數(shù)據(jù)對(duì)象分布較稀疏, MBR值應(yīng)該變大, 但由于β, MBR值不變. 所以β固定無(wú)法反應(yīng)數(shù)據(jù)對(duì)象的分布特征. 而在AC-UDGen算法中, 首先對(duì)每個(gè)數(shù)據(jù)對(duì)象計(jì)算出其離群因子, 離群因子大表示數(shù)據(jù)整體分布稀疏,β也會(huì)變大, MBR值變大. 離群因子小, 表示密度大, 數(shù)據(jù)分布密集,β會(huì)變小, MBR值也變小, 更貼合數(shù)據(jù)的實(shí)際分布情況, 從而減少聚類的迭代次數(shù), 提高運(yùn)行效率. 圖3為3種不同算法在不同分布上的F-measure值比較. 由圖3可見(jiàn), AC-UDGen算法的F-measure值, 除了在圖3(B)中的Wine數(shù)據(jù)集上與UK-medoids算法的F-measure值相同外, 在其他情況下AC-UDGen算法均優(yōu)于ABRAC和UK-medoids算法.

圖3 3種不同算法在不同分布上的F-measure值比較Fig.3 Comparison of F-measure values of three different algorithms on different distributions

圖4 3種不同算法在不同分布上的Q值比較Fig.4 Comparison of Q values of three different algorithms on different distributions

F-measure是外部評(píng)價(jià)標(biāo)準(zhǔn), 下面從內(nèi)部評(píng)價(jià)標(biāo)準(zhǔn)出發(fā), 比較各算法的Q值, 運(yùn)行10次, 取均值, 結(jié)果如圖4所示. 由圖4可見(jiàn), 在Wine數(shù)據(jù)集上, 采用uniform作為概率密度函數(shù)時(shí), AC-UDGen算法的Q值低于UK-medoids算法, 但在其他情況下顯然高于另外兩種算法. 綜合F-measure和Q值兩種評(píng)價(jià)標(biāo)準(zhǔn), 可知在多數(shù)情況下, AC-UDGen算法的聚類效果都優(yōu)于其他兩種對(duì)比算法, 因此本文提出的算法是有效的.

3.2 不同概率密度函數(shù)對(duì)結(jié)果的影響

上述實(shí)驗(yàn)結(jié)果表明, 不同概率密度函數(shù)會(huì)對(duì)聚類結(jié)果產(chǎn)生不同的影響. 下面選用normal, uniform,exponential,Laplace 4種分布進(jìn)行實(shí)驗(yàn)驗(yàn)證, 在同一數(shù)據(jù)集上, 采用不同的概率密度函數(shù), 分別運(yùn)行10次, 結(jié)果如圖5所示. 由圖5可見(jiàn), 在Iris數(shù)據(jù)集上, 采用uniform分布時(shí)結(jié)果波動(dòng)較大, Laplace分布不適合Wine和Glass數(shù)據(jù)集, 而exponential分布也不適合于Glass和Ecoli數(shù)據(jù)集. 可見(jiàn), 同一數(shù)據(jù)集采用不同分布時(shí), 聚類結(jié)果不同； 在分布相同時(shí), 數(shù)據(jù)集不同, 聚類結(jié)果也不同. 因此, 在生成不確定數(shù)據(jù)集時(shí), 應(yīng)對(duì)具體數(shù)據(jù)具體分析, 采用合適的概率密度函數(shù).

圖5 不同數(shù)據(jù)集不同分布的聚類結(jié)果Fig.5 Clustering results of different data sets with different distributions

3.3 驗(yàn)證AC-UDGen算法的時(shí)間效率

圖6 3種算法的運(yùn)行時(shí)間對(duì)比Fig.6 Comparison of running time of three algorithms

圖6為3種算法的運(yùn)行時(shí)間對(duì)比. 由圖6可見(jiàn), AC-UDGen算法的執(zhí)行時(shí)間比其他兩種方法長(zhǎng), 且對(duì)于3種算法隨著實(shí)驗(yàn)數(shù)據(jù)集的規(guī)模增大, 執(zhí)行時(shí)間也隨著延長(zhǎng). 雖然AC-UDGen算法有較高的時(shí)間代價(jià), 但在可接受的范圍內(nèi), 獲得了較好的聚類結(jié)果.

綜上所述, 本文提出了一種屬性級(jí)連續(xù)不確定數(shù)據(jù)生成算法AC-UDGen, 通過(guò)引入離群點(diǎn)檢測(cè)算法, 計(jì)算每個(gè)數(shù)據(jù)對(duì)象的離群因子, 并將離群因子作為控制數(shù)據(jù)分布范圍的參數(shù)產(chǎn)生擾動(dòng)因子, 降低了離群點(diǎn)對(duì)聚類結(jié)果的影響, 使每個(gè)數(shù)據(jù)對(duì)象MBR的值均可根據(jù)自身的分布特征自適應(yīng)的變化, 可用于產(chǎn)生滿足任何已知分布的不確定數(shù)據(jù)對(duì)象. 通過(guò)實(shí)驗(yàn)對(duì)比AC-UDGen算法與其他算法生成數(shù)據(jù)集上的準(zhǔn)確率、聚類精度和執(zhí)行時(shí)間, 也驗(yàn)證了選擇不同的概率密度函數(shù)對(duì)聚類結(jié)果會(huì)有不同的影響, AC-UDGen算法可較好地彌補(bǔ)傳統(tǒng)算法的不足, 在可接受的時(shí)間內(nèi)取得了較好的聚類精度.