高维稀疏数据对象——属性的零子空间分析

1、高维稀疏数据对象属性的零子空间分析    关键词高维稀疏数据；零子空间；子空间优化；高维数据预处理 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 引言 在数据挖掘的应用中，有一类数据如：购文档数据、空间数据、时间序列数据、基因序列等，其对象数目可达几百甚至上千，同时拥有成千上万个属性，我们将这类对象、属性数量特别大的数据对象称为高维数据（High Dimension Data，HDD）1。 高维数据与低维

4、数据在许多方面表现出不同的特性，如稀疏性以及“维度效应”现象2等。子空间聚类算法3的提出在一定程度上解决了这一问题，正在成为当前一个研究的热点4-14。 现有的算法大都多数关注的是子空间的获取,而忽略了子空间的优化, 这是不完备的15。 本文提出一种剔除零子空间算法(A Removing Zero-subspace Algorithm Based on Unique Binary Sequence Code， RZABUBS)，实现高维稀疏对象-属性子空间的优化。 2 问题描述 2.1 高维稀疏数据 有一类数据，其对象的数目很多，用来描述对象的属性也很多，但是对于每一个对象来说具有属性值的属性

5、个数占总属性个数的比例很小。例如钢铁企业中，有很多的客户（对象）和很多的产品（属性），各个客户购买的产品一般很少，而且各客户购买的产品种类也有很大不同。 定义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个属性上是稀疏的。实际上从客户购买产

6、品的角度来看，如果yij=1，表明第i个客户购买了第j种产品；如果yij=0，表明第i个客户没有购买第j种产品。 在文献16中，上述问题被称为具有“高维稀疏数据”的问题。 2.2零子空间 由于高维稀疏数据中存在大量的零属性值，则经过数据预处理获得的子空间中存在稀疏子空间，甚至包括属性值全为零的子空间。 定义2（零子空间）全部元素都是零值构成的子空间，我们称之为“零子空间”。 ，零子空间记为： 。 在高维数据挖掘中, 将数据点对数据挖掘的过程中起作用、对最终挖掘结果的产生有贡献的维, 称为非冗余属性，否则就是冗余属性。高维稀疏数据中存在大量的零属性值，故这些具有零属性值的属性是冗余属性，也可以说

7、具有零属性值的属性是冗余属性的一个特例。冗余属性不仅数据挖掘增加算法不必要的开销，而且影响算法处理效果和性能。因此，剔除零子空间是优化稀疏子空间的一种必要途径，对提高子空间质量具有重要意义。 3 RZABUBS算法 本文将基于二进制数代码提出稀疏特征值的计算公式，并根据稀疏特征值的取值情况，判断是否存在零子空间：假设对象-属性空间为m×n维，如果p个对象的稀疏特征值中存在连续q个零值（ ），则存在p×q维的零子空间 。 即：D=count(O1 OR O2 OROR Om) 其中O1, O2 Om分别为对象1,2，m对应稀疏特征值的二进制编码序列，OR 为布尔或运算， co

8、unt(*) 统计运算结果中含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的对象

9、-属性空间为例，运用算法进行剔除零子空间实现优化子空间的实验。经过对象-属性空间分割数据预处理后，得到相应的子空间，如图2。        从图可以看出，30×45的对象-属性空间经过分割技术的数据预处理后，获得的子空间包括两类：一类为零子空间和非零子空间。 本文运用RZABUBS算法，获得D1，D2，D3，D4和D5是零子空间。剔除这些零子空间后，原对象-属性空间由最终可以分解的子空间主要有3个低维子空间，维数分别为：10×13,7×12和11×16，如图3所示。因此，原对

10、象-属性的子空间得到了优化，子空间的质量获得了提高。 5.结束语 高维稀疏数据集在日常生活中占的比重越来越大,对这些数据进行预处理显得尤为重要, 故子空间的研究受到越来越多的关注。本文从稀疏性的角度提出了RZABUBS算法,通过剔除零子空间实现子空间的优化，提高子空间的质 量， 最终提高数据预处理的效果。 参考文献： 1 Jiawei Han, Micheline Kamber. 数据挖掘概念与技术(范明,孟小峰等译) M.北京:机械工业出版社,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 . 北京邮电大学学报, 2007, 30 (3) : 125-127 . 9 王国仁, 黄健美等. 基于最大间隙空间映射的高维数据索引技术J. 软件学报,2007,18(6) :1419-1428 10 李霞,徐树维. 子空间聚类改进算法研究综述J. 计算机仿真.2010，27（5）：174-177 11 任家东, 周玮玮, 何海涛. 高维数据流的自适应子空间聚类算法J. 计算机科学与探索. 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 许倡森. 基于混合网格划分的子空间高维数据聚类算法J. 计算机技术与发展.2010,10(10) 15 许倡森. 基于混合网格划分的子空间高维数据聚类算法J. 计算机技术与发展.2010,20（10）:150-153 16 Chu Y, Chen Y, Yang D, et al. Reducing