高維稀疏數據對象——屬性的零子空間分析

[摘要]針對高維稀疏數據對象-屬性子空間的優化問題，本文從稀疏性的角度提出了RZABUBS算法，通過剔除零子空間實現子空間的優化，并通過實驗研究證明了該算法的有效性。

[關鍵詞]高維稀疏數據；零子空間；子空間優化；高維數據預處理

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 引言

在數據挖掘的應用中，有一類數據如：購文檔數據、空間數據、時間序列數據、基因序列等，其對象數目可達幾百甚至上千，同時擁有成千上萬個屬性，我們將這類對象、屬性數量特別大的數據對象稱為高維數據（High Dimension Data，HDD）[1]。

高維數據與低維數據在許多方面表現出不同的特性，如稀疏性以及“維度效應”現象[2]等。子空間聚類算法[3]的提出在一定程度上解決了這一問題，正在成為當前一個研究的熱點[4-14]。

現有的算法大都多數關注的是子空間的獲取，而忽略了子空間的優化， 這是不完備的[15]。

本文提出一種剔除零子空間算法(A Removing Zero-subspace Algorithm Based on Unique Binary Sequence Code， RZABUBS)，實現高維稀疏對象-屬性子空間的優化。

2 問題描述

2.1 高維稀疏數據

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

定義1（稀疏特征）：假設有n個對象，描述第i個對象的m個屬性值分別對應于區間變量值xi1，xi2，…，xi m，將其轉換為二態變量并表示為yi1，yi2，…，yi m，轉換方法為：

其中 {1，2，…，n}； {1，2，…，m}。yij， {1，2，…，n}； {1，2，…，m}表明了各個對象在個屬性上的稀疏情況，稱為第i個對象在第j個屬性上的稀疏特征。如果yij=1，表明第i個對象在第j個屬性上是非稀疏的；如果yij=0，則表明第i個對象在第j個屬性上是稀疏的。實際上從客戶購買產品的角度來看，如果yij=1，表明第i個客戶購買了第j種產品；如果yij=0，表明第i個客戶沒有購買第j種產品。

在文獻[16]中，上述問題被稱為具有“高維稀疏數據”的問題。

2.2零子空間

由于高維稀疏數據中存在大量的零屬性值，則經過數據預處理獲得的子空間中存在稀疏子空間，甚至包括屬性值全為零的子空間。

定義2（零子空間）全部元素都是零值構成的子空間，我們稱之為“零子空間”。 ，零子空間記為： 。

在高維數據挖掘中， 將數據點對數據挖掘的過程中起作用、對最終挖掘結果的產生有貢獻的維， 稱為非冗余屬性，否則就是冗余屬性。高維稀疏數據中存在大量的零屬性值，故這些具有零屬性值的屬性是冗余屬性，也可以說具有零屬性值的屬性是冗余屬性的一個特例。冗余屬性不僅數據挖掘增加算法不必要的開銷，而且影響算法處理效果和性能。因此，剔除零子空間是優化稀疏子空間的一種必要途徑，對提高子空間質量具有重要意義。

3 RZABUBS算法

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

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

其中O1， O2… Om分別為對象1，2，…m對應稀疏特征值的二進制編碼序列，OR 為布爾或運算， count(*) 統計運算結果中含0的總個數。

若 ，則對象a和對象b構成的空間中存在如表1的零子空間 。

例如：表2是6個對象，8個屬性構成的稀疏對象-屬性空間。

則對象O4和O5的二進制代碼為：O4=11111000， O5=10011000，

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

故對象O4和O5中存在3個連續零：A6， A7 和A8 ，因此，存在一個2×3的零子空間 ，如表3所

4 算法應用

圖1是高維稀疏數據：30個對象45個屬性取值的情況，下面就以這30×45的對象-屬性空間為例，運用算法進行剔除零子空間實現優化子空間的實驗。經過對象-屬性空間分割數據預處理后，得到相應的子空間，如圖2。

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

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

5.結束語

高維稀疏數據集在日常生活中占的比重越來越大，對這些數據進行預處理顯得尤為重要， 故子空間的研究受到越來越多的關注。本文從稀疏性的角度提出了RZABUBS算法，通過剔除零子空間實現子空間的優化，提高子空間的質

量， 最終提高數據預處理的效果。

參考文獻：

[1]Jiawei Han， Micheline Kamber. 數據挖掘概念與技術(范明，孟小峰等譯) [M].北京:機械工業出版社，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 ]. 北京郵電大學學報， 2007， 30 (3) : 125-127 .

[9]王國仁， 黃健美等. 基于最大間隙空間映射的高維數據索引技術[J]. 軟件學報，2007，18(6) :1419-1428

[10]李霞，徐樹維. 子空間聚類改進算法研究綜述[J]. 計算機仿真.2010，27（5）：174-177

[11]任家東， 周瑋瑋， 何海濤. 高維數據流的自適應子空間聚類算法[J]. 計算機科學與探索. 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]許倡森. 基于混合網格劃分的子空間高維數據聚類算法[J]. 計算機技術與發展.2010，10(10)

[15]許倡森. 基于混合網格劃分的子空間高維數據聚類算法[J]. 計算機技術與發展.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].北京科技大學，2002

作者簡介：

祝琴：1978年生，江西臨川人，講師，北京科技大學管理科學與工程2007級博士研究生。主要研究方向：數據挖掘，管理優化，計算機控制。