高維稀疏數(shù)據(jù)對象——屬性的零子空間分析

1、高維稀疏數(shù)據(jù)對象屬性的零子空間分析    關(guān)鍵詞高維稀疏數(shù)據(jù)；零子空間；子空間優(yōu)化；高維數(shù)據(jù)預(yù)處理 Zero-Subspace of High Dimensional Sparse Data Object-Attribute Zhu Qin 1,2 ,Gao Xuedong 1,Wu Sen 1,Dai Aiming1 (1. School of Economics and Management, University of Science and Technology Beijing, 10083 2. School of Science, Nanch

2、ang University, 330031) Abstract：As far as optimization subspace of High dimensional sparse data object-attribute is concerned, from the point of sparseness RZABUBS algorithm is proposed to achieve subspace optimization by removing the zero subspace in the paper, and the experimental studies demonst

3、rate that the effectiveness of the proposed algorithm. Keywords: High dimensional sparse data, Zero-subspace, Subspace optimization, Preprocessing high dimension data 1 引言 在數(shù)據(jù)挖掘的應(yīng)用中，有一類數(shù)據(jù)如：購文檔數(shù)據(jù)、空間數(shù)據(jù)、時間序列數(shù)據(jù)、基因序列等，其對象數(shù)目可達(dá)幾百甚至上千，同時擁有成千上萬個屬性，我們將這類對象、屬性數(shù)量特別大的數(shù)據(jù)對象稱為高維數(shù)據(jù)（High Dimension Data，HDD）1。 高維數(shù)據(jù)與低維

4、數(shù)據(jù)在許多方面表現(xiàn)出不同的特性，如稀疏性以及“維度效應(yīng)”現(xiàn)象2等。子空間聚類算法3的提出在一定程度上解決了這一問題，正在成為當(dāng)前一個研究的熱點(diǎn)4-14。 現(xiàn)有的算法大都多數(shù)關(guān)注的是子空間的獲取,而忽略了子空間的優(yōu)化, 這是不完備的15。 本文提出一種剔除零子空間算法(A Removing Zero-subspace Algorithm Based on Unique Binary Sequence Code， RZABUBS)，實(shí)現(xiàn)高維稀疏對象-屬性子空間的優(yōu)化。 2 問題描述 2.1 高維稀疏數(shù)據(jù) 有一類數(shù)據(jù)，其對象的數(shù)目很多，用來描述對象的屬性也很多，但是對于每一個對象來說具有屬性值的屬性

5、個數(shù)占總屬性個數(shù)的比例很小。例如鋼鐵企業(yè)中，有很多的客戶（對象）和很多的產(chǎn)品（屬性），各個客戶購買的產(chǎn)品一般很少，而且各客戶購買的產(chǎn)品種類也有很大不同。 定義1（稀疏特征）：假設(shè)有n個對象，描述第i個對象的m個屬性值分別對應(yīng)于區(qū)間變量值xi1，xi2，xi m，將其轉(zhuǎn)換為二態(tài)變量并表示為yi1，yi2，yi m，轉(zhuǎn)換方法為： 其中 1，2，n； 1，2，m。yij， 1，2，n； 1，2，m表明了各個對象在個屬性上的稀疏情況，稱為第i個對象在第j個屬性上的稀疏特征。如果yij=1，表明第i個對象在第j個屬性上是非稀疏的；如果yij=0，則表明第i個對象在第j個屬性上是稀疏的。實(shí)際上從客戶購買產(chǎn)

6、品的角度來看，如果yij=1，表明第i個客戶購買了第j種產(chǎn)品；如果yij=0，表明第i個客戶沒有購買第j種產(chǎn)品。 在文獻(xiàn)16中，上述問題被稱為具有“高維稀疏數(shù)據(jù)”的問題。 2.2零子空間 由于高維稀疏數(shù)據(jù)中存在大量的零屬性值，則經(jīng)過數(shù)據(jù)預(yù)處理獲得的子空間中存在稀疏子空間，甚至包括屬性值全為零的子空間。 定義2（零子空間）全部元素都是零值構(gòu)成的子空間，我們稱之為“零子空間”。 ，零子空間記為： 。 在高維數(shù)據(jù)挖掘中, 將數(shù)據(jù)點(diǎn)對數(shù)據(jù)挖掘的過程中起作用、對最終挖掘結(jié)果的產(chǎn)生有貢獻(xiàn)的維, 稱為非冗余屬性，否則就是冗余屬性。高維稀疏數(shù)據(jù)中存在大量的零屬性值，故這些具有零屬性值的屬性是冗余屬性，也可以說

7、具有零屬性值的屬性是冗余屬性的一個特例。冗余屬性不僅數(shù)據(jù)挖掘增加算法不必要的開銷，而且影響算法處理效果和性能。因此，剔除零子空間是優(yōu)化稀疏子空間的一種必要途徑，對提高子空間質(zhì)量具有重要意義。 3 RZABUBS算法 本文將基于二進(jìn)制數(shù)代碼提出稀疏特征值的計(jì)算公式，并根據(jù)稀疏特征值的取值情況，判斷是否存在零子空間：假設(shè)對象-屬性空間為m×n維，如果p個對象的稀疏特征值中存在連續(xù)q個零值（ ），則存在p×q維的零子空間 。 即：D=count(O1 OR O2 OROR Om) 其中O1, O2 Om分別為對象1,2，m對應(yīng)稀疏特征值的二進(jìn)制編碼序列，OR 為布爾或運(yùn)算， co

8、unt(*) 統(tǒng)計(jì)運(yùn)算結(jié)果中含0的總個數(shù)。 若 ，則對象a和對象b構(gòu)成的空間中存在如表1的零子空間 。 例如：表2是6個對象，8個屬性構(gòu)成的稀疏對象-屬性空間。 則對象O4和O5的二進(jìn)制代碼為：O4=11111000, O5=10011000, D=count(O4OR O5)= count ( 11111000) OR(10011000)= count ( 11111000)=3 故對象O4和O5中存在3個連續(xù)零：A6, A7 和A8 ，因此，存在一個2×3的零子空間 ，如表3所 4 算法應(yīng)用 圖1是高維稀疏數(shù)據(jù)：30個對象45個屬性取值的情況，下面就以這30×45的對象

9、-屬性空間為例，運(yùn)用算法進(jìn)行剔除零子空間實(shí)現(xiàn)優(yōu)化子空間的實(shí)驗(yàn)。經(jīng)過對象-屬性空間分割數(shù)據(jù)預(yù)處理后，得到相應(yīng)的子空間，如圖2。        從圖可以看出，30×45的對象-屬性空間經(jīng)過分割技術(shù)的數(shù)據(jù)預(yù)處理后，獲得的子空間包括兩類：一類為零子空間和非零子空間。 本文運(yùn)用RZABUBS算法，獲得D1，D2，D3，D4和D5是零子空間。剔除這些零子空間后，原對象-屬性空間由最終可以分解的子空間主要有3個低維子空間，維數(shù)分別為：10×13,7×12和11×16，如圖3所示。因此，原對

10、象-屬性的子空間得到了優(yōu)化，子空間的質(zhì)量獲得了提高。 5.結(jié)束語 高維稀疏數(shù)據(jù)集在日常生活中占的比重越來越大,對這些數(shù)據(jù)進(jìn)行預(yù)處理顯得尤為重要, 故子空間的研究受到越來越多的關(guān)注。本文從稀疏性的角度提出了RZABUBS算法,通過剔除零子空間實(shí)現(xiàn)子空間的優(yōu)化，提高子空間的質(zhì) 量， 最終提高數(shù)據(jù)預(yù)處理的效果。 參考文獻(xiàn)： 1 Jiawei Han, Micheline Kamber. 數(shù)據(jù)挖掘概念與技術(shù)(范明,孟小峰等譯) M.北京:機(jī)械工業(yè)出版社,2001 2 Yang Q, Wu X. 10 challenging problems in data mining researchJ. Inte

11、rnational Journal of Information Technology and Decision Making, 2006, 5(4): 597 #8722;604. 3 Tan S, Cheng X, Ghanem M, et al. A novel refinement approach for text categorizationC/Proceedings of the ACM 14th Conference on Information and Knowledge Management, 2005: 469 #8722;476. 4 AGRAWAL R, GEHRKE

12、 J , GUNOPULOSD, et al . Automatic Subspace Clustering of High Dimensional Data for Data Mining Applications C / /A shutosh Tiwary . Proceedings of ACM SIG MOD International Conference on management of data, Seattle: ACM Press, 1998: 942 105 . 5 AGGARWAL CC, PROCOP I UC C, WOLF J L, et al . Fast Alg

13、orithms for 6 Projected Clustering C / / Proceedings of ACM SIG MOD International Conference on Management of Data, Philadelphia: ACM Press, 1999: 61272 . 7 AGG ARWAL CC, Y U P S . Finding Generalized Projected Clusters in High Dimensional Space C / /Proceedings of ACM SIG MOD International Conferen

14、ce on Management of Data, Dallas : ACM Press, 2000: 702 81 . 8 牛琨, 張舒博, 陳俊亮. 采用屬性聚類的高維子空間聚類算法 J . 北京郵電大學(xué)學(xué)報(bào), 2007, 30 (3) : 125-127 . 9 王國仁, 黃健美等. 基于最大間隙空間映射的高維數(shù)據(jù)索引技術(shù)J. 軟件學(xué)報(bào),2007,18(6) :1419-1428 10 李霞,徐樹維. 子空間聚類改進(jìn)算法研究綜述J. 計(jì)算機(jī)仿真.2010，27（5）：174-177 11 任家東, 周瑋瑋, 何海濤. 高維數(shù)據(jù)流的自適應(yīng)子空間聚類算法J. 計(jì)算機(jī)科學(xué)與探索. 2010,

15、4(9):859-865 12 G.J.Gan,J.H.Wu, A convergence theorem for the fuzzy subspace clustering(FSC) algorithm,PatternRecognition41(2008)19391947. 13 L.P.Jing, M.K.Ng, Z.X.Huang, An entropy weighting k-means algorithm for Subspace clustering of high-dimensional sparse data, IEEETrans. Knowl. Data Eng. 19(8)(2007)10261041. 14 許倡森. 基于混合網(wǎng)格劃分的子空間高維數(shù)據(jù)聚類算法J. 計(jì)算機(jī)技術(shù)與發(fā)展.2010,10(10) 15 許倡森. 基于混合網(wǎng)格劃分的子空間高維數(shù)據(jù)聚類算法J. 計(jì)算機(jī)技術(shù)與發(fā)展.2010,20（10）:150-153 16 Chu Y, Chen Y, Yang D, et al. Reducing