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

[摘要]針對(duì)高維稀疏數(shù)據(jù)對(duì)象-屬性子空間的優(yōu)化問題，本文從稀疏性的角度提出了RZABUBS算法，通過剔除零子空間實(shí)現(xiàn)子空間的優(yōu)化，并通過實(shí)驗(yàn)研究證明了該算法的有效性。

[關(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， Nanchang 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 demonstrate 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í)間序列數(shù)據(jù)、基因序列等，其對(duì)象數(shù)目可達(dá)幾百甚至上千，同時(shí)擁有成千上萬個(gè)屬性，我們將這類對(duì)象、屬性數(shù)量特別大的數(shù)據(jù)對(duì)象稱為高維數(shù)據(jù)（High Dimension Data，HDD）[1]。

高維數(shù)據(jù)與低維數(shù)據(jù)在許多方面表現(xiàn)出不同的特性，如稀疏性以及“維度效應(yīng)”現(xiàn)象[2]等。子空間聚類算法[3]的提出在一定程度上解決了這一問題，正在成為當(dāng)前一個(gè)研究的熱點(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)高維稀疏對(duì)象-屬性子空間的優(yōu)化。

2 問題描述

2.1 高維稀疏數(shù)據(jù)

有一類數(shù)據(jù)，其對(duì)象的數(shù)目很多，用來描述對(duì)象的屬性也很多，但是對(duì)于每一個(gè)對(duì)象來說具有屬性值的屬性個(gè)數(shù)占總屬性個(gè)數(shù)的比例很小。例如鋼鐵企業(yè)中，有很多的客戶（對(duì)象）和很多的產(chǎn)品（屬性），各個(gè)客戶購買的產(chǎn)品一般很少，而且各客戶購買的產(chǎn)品種類也有很大不同。

定義1（稀疏特征）：假設(shè)有n個(gè)對(duì)象，描述第i個(gè)對(duì)象的m個(gè)屬性值分別對(duì)應(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}表明了各個(gè)對(duì)象在個(gè)屬性上的稀疏情況，稱為第i個(gè)對(duì)象在第j個(gè)屬性上的稀疏特征。如果yij=1，表明第i個(gè)對(duì)象在第j個(gè)屬性上是非稀疏的；如果yij=0，則表明第i個(gè)對(duì)象在第j個(gè)屬性上是稀疏的。實(shí)際上從客戶購買產(chǎn)品的角度來看，如果yij=1，表明第i個(gè)客戶購買了第j種產(chǎn)品；如果yij=0，表明第i個(gè)客戶沒有購買第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)對(duì)數(shù)據(jù)挖掘的過程中起作用、對(duì)最終挖掘結(jié)果的產(chǎn)生有貢獻(xiàn)的維， 稱為非冗余屬性，否則就是冗余屬性。高維稀疏數(shù)據(jù)中存在大量的零屬性值，故這些具有零屬性值的屬性是冗余屬性，也可以說具有零屬性值的屬性是冗余屬性的一個(gè)特例。冗余屬性不僅數(shù)據(jù)挖掘增加算法不必要的開銷，而且影響算法處理效果和性能。因此，剔除零子空間是優(yōu)化稀疏子空間的一種必要途徑，對(duì)提高子空間質(zhì)量具有重要意義。

3 RZABUBS算法

本文將基于二進(jìn)制數(shù)代碼提出稀疏特征值的計(jì)算公式，并根據(jù)稀疏特征值的取值情況，判斷是否存在零子空間：假設(shè)對(duì)象-屬性空間為m×n維，如果p個(gè)對(duì)象的稀疏特征值中存在連續(xù)q個(gè)零值（ ），則存在p×q維的零子空間 。

即：D=count(O1 OR O2 OR…OR Om)

其中O1， O2… Om分別為對(duì)象1，2，…m對(duì)應(yīng)稀疏特征值的二進(jìn)制編碼序列，OR 為布爾或運(yùn)算， count(*) 統(tǒng)計(jì)運(yùn)算結(jié)果中含0的總個(gè)數(shù)。

若 ，則對(duì)象a和對(duì)象b構(gòu)成的空間中存在如表1的零子空間 。

例如：表2是6個(gè)對(duì)象，8個(gè)屬性構(gòu)成的稀疏對(duì)象-屬性空間。

則對(duì)象O4和O5的二進(jìn)制代碼為：O4=11111000， O5=10011000，

D=count(O4OR O5)= count (( 11111000) OR(10011000))= count ( 11111000)=3

故對(duì)象O4和O5中存在3個(gè)連續(xù)零：A6， A7 和A8 ，因此，存在一個(gè)2×3的零子空間 ，如表3所

4 算法應(yīng)用

圖1是高維稀疏數(shù)據(jù)：30個(gè)對(duì)象45個(gè)屬性取值的情況，下面就以這30×45的對(duì)象-屬性空間為例，運(yùn)用算法進(jìn)行剔除零子空間實(shí)現(xiàn)優(yōu)化子空間的實(shí)驗(yàn)。經(jīng)過對(duì)象-屬性空間分割數(shù)據(jù)預(yù)處理后，得到相應(yīng)的子空間，如圖2。

從圖可以看出，30×45的對(duì)象-屬性空間經(jīng)過分割技術(shù)的數(shù)據(jù)預(yù)處理后，獲得的子空間包括兩類：一類為零子空間和非零子空間。

本文運(yùn)用RZABUBS算法，獲得D1，D2，D3，D4和D5是零子空間。剔除這些零子空間后，原對(duì)象-屬性空間由最終可以分解的子空間主要有3個(gè)低維子空間，維數(shù)分別為：10×13，7×12和11×16，如圖3所示。因此，原對(duì)象-屬性的子空間得到了優(yōu)化，子空間的質(zhì)量獲得了提高。

5.結(jié)束語

高維稀疏數(shù)據(jù)集在日常生活中占的比重越來越大，對(duì)這些數(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 research[J]. International 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 categorization[C]//Proceedings of the ACM 14th Conference on Information and Knowledge Management， 2005: 469#8722;476.

[4]AGRAWAL R， GEHRKE 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 Algorithms 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 Conference 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， 4(9):859-865

[12]G.J.Gan，J.H.Wu， A convergence theorem for the fuzzy subspace clustering(FSC) algorithm，PatternRecognition41(2008)1939–1947.

[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)1026–1041.

[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 redundancy in subspace clustering[J]. IEEE Transactions on Knowledge and Data Engineering， 2009， 21(10): 1432#8722;1446.

[17]武森. 高屬性維稀疏聚類[D].北京科技大學(xué)，2002

作者簡(jiǎn)介：

祝琴：1978年生，江西臨川人，講師，北京科技大學(xué)管理科學(xué)與工程2007級(jí)博士研究生。主要研究方向：數(shù)據(jù)挖掘，管理優(yōu)化，計(jì)算機(jī)控制。