考慮數據不確定性的非均勻挖掘算法

劉竹松, 陳潔

(廣東工業大學 計算機學院， 廣東 廣州 510006)

?

考慮數據不確定性的非均勻挖掘算法

劉竹松, 陳潔

(廣東工業大學 計算機學院， 廣東 廣州 510006)

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

關鍵詞：高維大數據； 數據挖掘； 模糊邏輯； 不確定頻繁模式樹； 區域連接演算

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

1高維大數據模型

1.1高維數據的建模

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

表1　RCC-5模型的對應關系

(1)

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

1.2高維數據集合模糊距離分析

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

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

(2)

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

近似點集構成的封閉集合區域R*=(R,ε)表示為

(3)

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

同樣，點與分割集合區域之間的距離函數表示為

(4)

1.3高維不確定關系計算

通過前面的分析，該部分主要基于元素的基元進行數據集合區域的近似計算分析，近似區域的總體表示為

(5)

由于這種邏輯數學的表達形式不能直接判斷集合的關系，文中主要通過集合基元數據(STUPLE)進行近似區域的表達，相互關系可以表示為

(6)

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

(7)

(8)

(9)

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

2仿真與結果分析

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

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

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

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

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

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

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

3結束語

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

參考文獻：

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

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

[3]吳章玲,金培全,岳華麗,等.基于PCM的大數據存儲與管理研究[J].計算機研究與發展,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]王珊,王會舉,覃雄派.架構大數據：挑戰、現狀與展望[J].計算機學報,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與相關子空間的局部離群數據挖掘算法[J].軟件學報,2015,26(5):1079-1095.

[8]劉大有,王生生,虞強源.基于定性空間推理的多層空間關聯規則挖掘算法[J].計算機研究與發展,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 的混合屬性特征大數據集聚類算法[J].電子與信息學報,2004,26(8):1203-1209.

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

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

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

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

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

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

文獻標志碼：A

基金項目：國家自然科學基金資助項目(61572144)； 廣東省科技計劃項目(2013B090200006); 廣東省現代信息服務業發展專項基金資助項目(GDEID2011IS022)

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

收稿日期：2016-03-18

doi:10.11830/ISSN.1000-5013.2016.03.0308

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