劉竹松, 陳潔

(廣東工業(yè)大學(xué) 計算機(jī)學(xué)院， 廣東 廣州 510006)

?

考慮數(shù)據(jù)不確定性的非均勻挖掘算法

劉竹松, 陳潔

(廣東工業(yè)大學(xué) 計算機(jī)學(xué)院， 廣東 廣州 510006)

摘要：針對高維大數(shù)據(jù)不確定性的非均勻挖掘問題，提出一種基于不確定頻繁模式樹的模糊邏輯非均勻數(shù)據(jù)挖掘算法.首先，在考慮數(shù)據(jù)不確定性的前提下建立高維數(shù)據(jù)的區(qū)域連接演算(RCC)模型，并基于數(shù)據(jù)集合組元定義分析不確定數(shù)據(jù)集合的模糊距離；然后，采用不確定模式樹對數(shù)據(jù)的非均勻特性進(jìn)行均勻泛化處理，并給出了具體的實現(xiàn)步驟.仿真結(jié)果表明:文中方法有效地提升不確定非均勻數(shù)據(jù)集合在不同支持度情況下的挖掘效率.

關(guān)鍵詞：高維大數(shù)據(jù)； 數(shù)據(jù)挖掘； 模糊邏輯； 不確定頻繁模式樹； 區(qū)域連接演算

數(shù)據(jù)挖掘算法已經(jīng)成為大數(shù)據(jù)領(lǐng)域的熱點(diǎn).通過有效的算法分析，能夠及時有效地發(fā)現(xiàn)海量數(shù)據(jù)的價值信息，增強(qiáng)目標(biāo)預(yù)測的有效性和準(zhǔn)確性[1-2].為了提升數(shù)據(jù)的保密功能，大部分?jǐn)?shù)據(jù)都具有人為的不確定性及集合區(qū)分的非均勻特性，而現(xiàn)有的挖掘算法針對這類數(shù)據(jù)的挖掘效率太低甚至失效[3].2000年，Eliseo等[4]提出采用多層集合分界進(jìn)行高維大數(shù)據(jù)的均勻規(guī)則挖掘.但是，目前不確定非均勻數(shù)據(jù)集合的研究還非常少，特別是高維數(shù)據(jù)的分集及集合大小的選擇問題[5].Shifei等[6]在現(xiàn)有的挖掘思想中引入智能推理的思想，將定性空間推理(qualitative spatial reasoning,QSR)技術(shù)引入到高維數(shù)據(jù)的不確定性挖掘算法.張繼福等[7]實現(xiàn)了一種基于相關(guān)子空間的局部離群數(shù)據(jù)挖掘算法，并有效改善離群程度較大的局部離群數(shù)據(jù)的挖掘效率.基于此，本文提出一種考慮數(shù)據(jù)不確定性的非均勻挖掘算法.

1高維大數(shù)據(jù)模型

1.1高維數(shù)據(jù)的建模

通常針對大數(shù)據(jù)集合建模的主要思想就是將數(shù)據(jù)集合看作空間目標(biāo)進(jìn)行整體建模.針對確定數(shù)據(jù)建模的代表性工作是文獻(xiàn)[8]提出的區(qū)域連接演算(region connection calculus，RCC)理論，該理論通過連接算子C(x,y)先后分析了RCC-5，RCC-8，RCC-15等多種數(shù)據(jù)拓?fù)浣Y(jié)構(gòu).文中在RCC-5模型的基礎(chǔ)上，通過融入模糊邏輯構(gòu)建基元數(shù)據(jù)關(guān)系和不確定模式樹的方法，針對不確定數(shù)據(jù)集合進(jìn)行建模.為了便于分析，采用三個基元進(jìn)行簡化模型分析，其三基元等價模型為

表1　RCC-5模型的對應(yīng)關(guān)系

(1)

式(1)中：各基元數(shù)據(jù)的取值范圍都是{0,1}；具有實際物理意義的基元數(shù)據(jù)有5種.相應(yīng)的RCC-5模型的對應(yīng)關(guān)系如表1所示.

1.2高維數(shù)據(jù)集合模糊距離分析

數(shù)據(jù)的確定通常都是一種理想的假設(shè)，在實際的大數(shù)據(jù)信息中，由于保密和應(yīng)用范圍的需求，通常都會人為地加入不確定信息，以保持?jǐn)?shù)據(jù)集合的唯一性[9].數(shù)據(jù)的不確定性表現(xiàn)在集合分割的特征方面就是區(qū)域邊界的模糊性，在分析研究中通常將這種模糊性稱為近似分割集合.近似分割思想是QSR理論近年來的研究熱點(diǎn)，目前還沒有形成統(tǒng)一的理論框架.

文獻(xiàn)[10-11]分別提出了近似區(qū)域和寬邊界區(qū)域的“蛋黃”模型，陳愛東等[12]提出了一種應(yīng)用高維數(shù)據(jù)的交集擴(kuò)展模型，其主要事項都是針對均勻不確定數(shù)據(jù)的聚類處理.采用模糊邏輯的思想進(jìn)行數(shù)據(jù)不確定關(guān)系的理論建模分析，假設(shè)給定的近似點(diǎn)集為P*=(P,ε),P(a,b)表示給定集合的確定點(diǎn)，ε>0為P的有效延伸區(qū)域，則P*的隸屬度函數(shù)可以表示為

(2)

式(2)中:k(x)=max{min{x,1},0}；d00為基元點(diǎn)集之間的歐式距離.

近似點(diǎn)集構(gòu)成的封閉集合區(qū)域R*=(R,ε)表示為

(3)

式(3)中:R為R*的核，是數(shù)據(jù)分割集合的確定區(qū)域.

同樣，點(diǎn)與分割集合區(qū)域之間的距離函數(shù)表示為

(4)

1.3高維不確定關(guān)系計算

通過前面的分析，該部分主要基于元素的基元進(jìn)行數(shù)據(jù)集合區(qū)域的近似計算分析，近似區(qū)域的總體表示為

(5)

由于這種邏輯數(shù)學(xué)的表達(dá)形式不能直接判斷集合的關(guān)系，文中主要通過集合基元數(shù)據(jù)(STUPLE)進(jìn)行近似區(qū)域的表達(dá)，相互關(guān)系可以表示為

(6)

式(6)中:TAG為RCC-5模型的數(shù)據(jù)核；d1為兩個圓心為R1和R2的圓集合的邊緣距離，其中，正數(shù)為在兩集合之外，負(fù)數(shù)為兩集合之內(nèi)，當(dāng)兩個集合重疊的時候，取集合邊界的最大值；d2是R2相對于R1的距離，其中，最大值分別表示為s1和s2.

(7)

(8)

(9)

在數(shù)據(jù)集合分布較密集的情況下，如果滿足分析條件的最大距離為s1?ε1，s2?ε2,可以將文中模型的三元隸屬度函數(shù)表示為

2仿真與結(jié)果分析

為充分分析文中方法的可行性，對基于確定均勻數(shù)據(jù)和非確定非均勻兩類數(shù)據(jù)庫進(jìn)行仿真分析.仿真采用IntelCore2，CPU為2.4GHz,RAM內(nèi)存為2GB，操作系統(tǒng)為WindowXP，軟件為Matlab2012.實驗選擇了兩組數(shù)據(jù)集合，基于UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫的Adult數(shù)據(jù)[13-14]，該數(shù)據(jù)共48 842條記錄，屬確定均勻分布的數(shù)據(jù)集合，仿真中取前10 000條數(shù)據(jù)記為 D1.另一條數(shù)據(jù)是IBM數(shù)據(jù)集生成器生成的數(shù)據(jù)，該數(shù)據(jù)集總記錄數(shù)據(jù)為100萬條.由于數(shù)據(jù)太長，根據(jù)實驗分析需要，將數(shù)據(jù)集合進(jìn)行了分割處理，僅提取需要的5 000條數(shù)據(jù)進(jìn)行分析，記錄為D2.為定量說明方法的性能，在相同的實驗條件下，選擇了文獻(xiàn)[6-7]的方法進(jìn)行對比分析.

2.1不同支持度情況下的效率分析

針對兩組不同數(shù)據(jù)集合，在支持度從5%降到0.1%的情況下，不同挖掘算法的運(yùn)行時間，如圖1所示.圖1中：t為運(yùn)行時間：η為支持度.由圖1可知：相對于確定、均勻數(shù)據(jù)集合而言，文獻(xiàn)[6-7]的方法在非確定、非均勻數(shù)據(jù)集合上的運(yùn)行時間大幅提升，已經(jīng)無法滿足數(shù)據(jù)挖掘的實時性需求，效率低下；但是文中方法在兩種數(shù)據(jù)集合情況下均保持了較好的挖掘效率，雖然在非確定、非均勻情況下的運(yùn)行時間有所增加，但是仍然處于有效的挖掘效率范圍內(nèi).

(a) D1 (b) D2圖1　不同支持度的運(yùn)行效率比較Fig.1　Running efficiency comparison of different support degree

2.2生成一個頻繁樹的時間消耗分析

為進(jìn)一步定量分析文中挖掘算法在相同條件下的挖掘性能，對比分析兩個不同的數(shù)據(jù)庫進(jìn)行了生成一個頻繁樹需要的時間消耗，仿真結(jié)果如圖2所示.由圖2可知：文中方法針對兩個數(shù)據(jù)庫的運(yùn)行時間消耗都控制在0.08 s以內(nèi)；而文獻(xiàn)[6-7]的方法的運(yùn)行時間均高出文中方法一個數(shù)量級，這一點(diǎn)的主要原因是文中方法采用了模糊邏輯進(jìn)行了模型的建模，在理論上克服了邊界模糊效應(yīng)的影響.

(a) 文獻(xiàn)[6]方法 　　　　　　　　　　(b) 文獻(xiàn)[7]方法　　　　　　　　　　(c) 文中方法圖2　生成一個頻繁樹的時間消耗對比Fig.2　Time consumption comparison of generating a frequent tree

3結(jié)束語

針對高維大數(shù)據(jù)的不確定性非均勻挖掘問題，文中提出了一種基于不確定頻繁模式樹的模糊邏輯非均勻數(shù)據(jù)挖掘算法.在考慮數(shù)據(jù)不確定性的前提下，建立了高維數(shù)據(jù)的RCC模型，并基于數(shù)據(jù)集合組元定義分析了不確定數(shù)據(jù)集合的模糊距離.由于采用模糊邏輯的思想進(jìn)行建模，在理論上消除了數(shù)據(jù)集合的邊緣效應(yīng)，增強(qiáng)了算法的運(yùn)行效率；同時，由于不確定模式樹對數(shù)據(jù)的非均勻特性進(jìn)行均勻泛化處理，進(jìn)一步增強(qiáng)了算法對無序大數(shù)據(jù)的處理能力.最后的仿真結(jié)果表明：文中方法為處理非確定和非均勻大數(shù)據(jù)提供一種可行的思路，

參考文獻(xiàn)：

[1]喻小光,陳維斌,陳榮鑫.一種數(shù)據(jù)規(guī)約的近似挖掘方法的實現(xiàn)[J].華僑大學(xué)學(xué)報(自然科學(xué)版),2008,29(3):370-374.

[2]朱龍.利潤約束的關(guān)聯(lián)規(guī)則挖掘算法[J].華僑大學(xué)學(xué)報(自然科學(xué)版),2015,36(5):522-526.

[3]吳章玲,金培全,岳華麗,等.基于PCM的大數(shù)據(jù)存儲與管理研究[J].計算機(jī)研究與發(fā)展,2015,52(2):343-361.

[4]ELISEO C,FELICE P D.Mining multiple-level spatial association rules for objects with a broad boundary[J].Data and Knowledge Engineering,2000,34(3):251-270.

[5]王珊,王會舉,覃雄派.架構(gòu)大數(shù)據(jù)：挑戰(zhàn)、現(xiàn)狀與展望[J].計算機(jī)學(xué)報,2011,34(10):174-181.

[6]SHIFEI D,FULIN W,JUN Q,et al.Research on data stream clustering algorithms [J].Artificial Intelligence Review,2013,43(4):593-600

[7]張繼福,李永紅,秦嘯,等.基于MapReduce與相關(guān)子空間的局部離群數(shù)據(jù)挖掘算法[J].軟件學(xué)報,2015,26(5):1079-1095.

[8]劉大有,王生生,虞強(qiáng)源.基于定性空間推理的多層空間關(guān)聯(lián)規(guī)則挖掘算法[J].計算機(jī)研究與發(fā)展,2004,41(4):565-570.

[9]JONATHAN A S,ELAINE R F,RODRIGO C B,et al.Data stream clustering: A survey[J].ACM Computing Surveys,2013,46(1):1-13,31.

[10]李潔,高新波,焦李成.一種基于 GA 的混合屬性特征大數(shù)據(jù)集聚類算法[J].電子與信息學(xué)報,2004,26(8):1203-1209.

[11]任家東,王倩,王蒙.一種基于頻繁模式有向無環(huán)圖的數(shù)據(jù)流頻繁模式挖掘算法[J].燕山大學(xué)學(xué)報(自然科學(xué)版),2011,35(2):115-120.

[12]陳愛東,劉國華,費(fèi)凡,等.滿足均勻分布的不確定數(shù)據(jù)關(guān)聯(lián)規(guī)則挖掘算法[J].計算機(jī)研究與發(fā)展,2013,50(增刊1):186-195.

[13]雷向欣,楊智應(yīng),黃少寅,等.XML數(shù)據(jù)流分頁頻繁子樹挖掘研究[J].計算機(jī)研究與發(fā)展,2012,49(9):1926-1936.

[14]孫力娟,陳小東,韓崇,等.一種新的數(shù)據(jù)流模糊聚類方法[J].電子與信息學(xué)報,2015,37(7):1620-1625.

(責(zé)任編輯： 陳志賢英文審校： 吳逢鐵)

Non-Uniform Mining Algorithm for Considering Data Uncertainty

LIU Zhusong， CHEN Jie

(School of Computer Science and Technology， Guangdong University of Technology, Guangzhou 510006, China)

Abstract：In order to solve high-dimensional large data uncertainty and non-uniform mining problems, this paper proposed a new kind of non-uniform data mining algorithm based on the fuzzy logic and uncertain frequent pattern tree. Firstly, the high-dimensional region connection calculus (RCC) data model is established under the premise of considering the data uncertainty. The uncertain fuzzy distance of data sets is defined and analyzed based on the data sets elements. Secondly, the non-uniform data is generalized by the uncertain frequent pattern tree, and the specific implementation steps is given. Simulation results show that the proposed method effectively improved the mining efficiency of the uncertain heterogeneous data sets in different support conditions.

Keywords：high dimensional data; data mining; fuzzy logic; uncertain frequent pattern tree； region connection calculus

中圖分類號：TP 311.13

文獻(xiàn)標(biāo)志碼：A

基金項目：國家自然科學(xué)基金資助項目(61572144)； 廣東省科技計劃項目(2013B090200006); 廣東省現(xiàn)代信息服務(wù)業(yè)發(fā)展專項基金資助項目(GDEID2011IS022)

通信作者：劉竹松(1979-)，男，副教授，博士，主要從事云計算、大數(shù)據(jù)的研究.E-mail:liuzs@gdut.edu.cn.

收稿日期：2016-03-18

doi:10.11830/ISSN.1000-5013.2016.03.0308

文章編號：1000-5013(2016)03-0308-04