基于张开角测度的数据约简*

李　晨， 王亚茹， 岳士弘

(天津大学 电气与自动化工程学院，天津 300072)

基于张开角测度的数据约简*

李晨， 王亚茹， 岳士弘

(天津大学 电气与自动化工程学院，天津 300072)

摘要:数据约简是包括数据压缩、数据调整和特征提取在内的数据挖掘技术中的重要课题，但已有的数据约简方法主要聚焦在特征或者维度的约简，而针对样本个数的约简方法，往往是针对具体的数据集开发，缺乏一般性。 针对数据集中数据分布的一般特征，定义一种新的基于张开角的测度。该测度能够区分数据集中核心对象和边界对象分布的本质区别，实现数据集中以核心对象为中心的数据压缩。通过对UCI公共测试平台上20个具有不同特征的典型样本集进行数据约简和测试，结果表明:约简能够有效地提取数据集中的核心目标；通过对约简前后数据集采用经典K均值算法聚类，发现约简后数据集中聚类正确率明显高于约简前数据集。

关键词:数据约简； 方向角； 聚类分析

0引言

数据约简是在保持分类和决策能力的前提下，对数据中不相关或者不重要的信息进行去除。冗余的数据不仅浪费存储空间，而且影响分类的精确性和决策的正确性。数据约简包括特征约简和样本数约简。已有的关于特征约简的研究成果已经很丰富也很深入，如神经网络、粗集、主成分分析等[1～3]。目前有关数据约简的方法主要集中在对样本属性的约简上即特征约简,而对数据集中总的样本个数的约简方法，则主要是对特定数据集进行，方法较少且缺乏一般性。 当前，随着信息量呈现出爆炸性的增长，对海量数据使用数据约简是不可避免的，目前见诸于报道的包括抽样和综合两种途径[4,5]。一种抽样方法是将样本分成若干子集，然后分别对这些子集进行学习，对学习结果进行重新组合；另一种方法是对样本进行分组，然后反复选取那些能够提高学习效果的例子加进来[6]。综合的方法试图产生适合内存大小的数据，然后对这些数据进行访问。综合的数据可以由统计得来[7,8]，也可以由压缩技术得到[9]。抽样和综合可以互为补充，将两者结合起来使用。

抽样是最常用的一种减少样本数的方法。通过对数据样本的精选，不仅减少了数据的处理量，还节省了系统资源，并且通过对数据的筛选，使其反映的规律性更加凸显。但由于通常情况下样本集中样本的分布并不可知，故抽样的代表性难以保证。

对海量数据进行数据约简并不是对其进行简单的比例缩放。传统方法是发现数据库中所反映的每一个模型，它们是局部的模式或反模式(异常)。目前，数据约简的研究关心约简效率比关心约简后泛化能力要多得多。实际上，泛化的合理性和抽取样本的代表性才是机器学习的核心，围绕该问题的工作十分有意义[10]。

本文提出一种新的基于张开角的测度，从数据集样本的分布特征出发，区分核心目标和边界目标，通过渐进的迭代优化运算,删除相互之间类别信息模糊的无用数据，而这些目标对应着数据集中样本分布的边界点。实验结果表明：采用本文提出的方法能够在大幅度缩减原始训练集规模的同时保持原分类问题的识别精度。事实上，通过使用经典的K均值算法聚类到约简前和约简后的数据集，约简后的数据集中的聚类正确率明显高于约简前的数据集，这表明本文提出的方法能够有效地提取数据集中的代表点保留数据集中有用的信息消除噪声目标的干扰[11,12]。

1基于张开角测度的数据约简

本节首先提出一个基于张开角测度的数据约简方法，这个方法基于如下观察。图1显示一个包含12个点的数据集中数据的分布,其中,图1(a)是原始的数据集; 图1(b)～(d) 分别相应于边界点、中间点和核心点的分布及张开角示意。 从这些点的几何位置上比较，大致可以分为外侧的边界点(A,C,H,E,F,G)、中间点(B,L,J,H)和核心点(K,I)。

图1　一个类中不同点的分布与张开角Fig 1　Distribution and open-angle of different points in a class

边界点与其它点的一个显著区别是，如果从任何一个考察的边界点与内部最近的若干点做连线，则这些连线逐对之间的平均张开角要远小于其它中间点和核心点的张开角。实际上，对于每个点选择离其最近的4个点做连线，则边界点A,C,H,E,F,G的平均张开角值为67.5°、中间点B,L,J,H为112.3°和核心点K,I为120.4°。一个点离开群聚点越远，它的平均张开角越小。另一方面，一个点在当前不是边界点，但是在一个边界点被去除后却可能变成边界点，从而与其它边界点可以进行比较。如图1中的B点，在去除A点后变成边界点。因此，当约简迭代且渐进地进行时，每次约简的都是一个最靠近边界的点。

一般设X={x1,x2,…,xn} 是一个d维空间中包含n个数据向量(模式)集合，任取X中第i个向量xi,设xi1,xi2,…,xi2d是2d个顺时针排列的距离其最近的向量，则从xi出发与xi1,xi2,…,xi2d相连构成(2d-1)个向量的张开角(xi,xi1),(xi1,xi2),…,(xi(2d-1),xi(2d))，则定义xi的平均张开角测度如下为

i=1,…,n

(1)

式中Angle( )为一对从xi出发的一对连接向量之间的夹角; |xsxi|相应的连接长度；因此，m(xi)的设计基于边界点的两个特征：较大的张开角和较长的与近邻点的连接距离。较长的连接距离意味着该点附件其它点分布稀疏，或者说密度较小。另一方面，根据前面的分析,本文提出的方法不是进行一次性约简，而是使用一个迭代的约简过程，按照一定约简比例逐个删除样本实现原始数据集的约简。具体实现过程如下：

1)输入d维空间数据点集X={x1x2,…,xn};

2) 计算X中逐对点之间的距离构成一个新的数据集D(X);

3)记X=X1∪X2;

4)开始

让X1=∅(空集)且X2=X;

5)重复

对于任意xi∈X在D(X)中找出连接该点长度最小的2d距离；

6)根据式(1)计算xi∈X的平均张开角;

7)根据张开角排序所有X中的点;

8)去除张开角最小的向量;

9)去除该去除向量对应的连接距离;

10)重新计算这些相关向量的张开角;

11)返回步骤(7);

12)在达到一个约简比后输出结果。

以一个包含80个点的数据集为例来说明数据约简过程。图2显示了这80个数据点在二维坐标系下的分布情况，其中,x轴表示点的横坐标，y轴表示点的纵坐标。本文后续约简图中的坐标表示与图2相同。当约简比分别设定为30 %,50 %,80 %时，图3显示了30 %,50 %,80 %目标被约简后的数据集，其中,实心点表示被保留的点，而空心圆圈表示被约简的点。从图中可以看出，随着迭代的进行，约简过程始终沿着边界进行，各个类的几何中心由于与相邻点的距离保持较大，因此始终被保留,同时每次去除都是一个边界点。

图2　测试的数据集Fig 2　Test data set

(a) 30 %的点约简

(b) 50 %的点约简

(c) 80 %的点约简图3　点约简后的数据集Fig 3　Data sets after points reduction

2实验

1)实验环境:本节实验结果运行在以下条件下:Matlab@6.5,3.2 GHz CPU,512M RAM 和Window 7 系统。

2)测试数据集:使用UCI数据集中 23 个带有不同特征的数据集进行约简并进行效果分析，23个数据集的主要特征如表1所示。这些数据集中正确的类标号是先验给出的。可以用于检测任何一个测试的分类或聚类算法的正确性和有效性。

3)聚类算法:聚类实施算法是在Weka2.3软件平台上完成的。在该平台上使用经典的K均值算法实施聚类，正确的类数k都是作为先验的信息预先输入。

4)效果评价:这里的正确率是聚类后的标号与先验的标号作对比得到的，而约简后的正确率是根据最近邻原则，在约简后的样本集中确定好聚类原型后，再将被约简的样本按照距离最近的聚类原型赋予类的标号。而运行时间是在Matlab中使用“tic”和“toc”两个函数统计计算得出的。

表1　23个UCI中测试数据集分布

这些选择的数据集都带有大量噪声和杂讯，这将严重影响聚类或分类的正确率。本文使用提出的数据约简方法对数据集进行约简，分别在不同的比例下约简后的数据集使用K均值算法进行聚类分析，其正确率如表格3所示。表2显示:在23个数据集中共有20个数据集分类的正确率在数据约简后有显著提高。而正确率未能上升的数据集中，实际上，类的形状分布是任意的，无法用K均值算法正确聚类[13]。

图4、图5、分别显示了数据集IRIS约简过程中的约简效果，这里,数据集的样本被投影到第1个和第2个维度所组成的二维空间中。图4为原始的数据集，图5表示30 %,50 %和60 %目标被约简后的数据集，图中实心点表示被保留的点，而空心圆圈表示被约简的点。

从图中可以看出，IRIS数据集中的原先样本在这两个维度上可分性较差，但是在实施数据约简后，类与类之间的距离变大，可分性明显增加；事实上，在其它特征或特征组合上，这些数据集中也有类似的结论[14]。

表2　23个UCI测试数据集约简聚类效果

但从时间上看，数据约简需要反复计算各个点的领域，相当于在K均值算法中实施了预处理，若约简比例超过50 %，总的运算时间可以减少。这是由于K均值算法的计算复杂度是O(ktn),k是输入的类数，t是迭代次数，而n是总样本个数。数据约简实际上减小了样本数n，但是增加了预处理时间并且是逐次进行的。

图4　Iris数据集Fig 4　Data set of Iris

(a) Iris中30 %的点约简

(b) Iris中50 %的点约简

(c) Iris中60 %的点约简图5　Iris中的点约简Fig 5　Reduction of points of Iris

3结论

本文研究了任意数据集中基于数据个数的数据约简，分析了不同样本的分布特征，据此提出一个具有一般性的新的测度。以K均值算法为例，实验表明:本文提出测度的效率明显提高，其中基于部分特征的 K均值算法分类正确率提高26 %～28 %，基于全部样本的情况下正确率提高 8～12 %,证明本文提出算法是实用和有效的[15]。

本文方法的主要不足在于时间效率的耗费，由于要计算逐对点的距离，因此,数据集的约简时间要高于已有的基于抽样的方法，为此，进一步的研究需要在保留该算法优势的基础上改进计算效率。

参考文献:

[1]叶施仁.海量数据约简与分类研究[D].北京：中国科学院计算技术研究所,2001.

[2]Sanguinetti G.Dimensionality reduction of clustered data set-s[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2008,30(3):535-540.

[3]Bochanski J J,Hennawi J F,Simcoe R A,et al.MASE:A new data reduction pipeline for the magellan echellette spectro-graph[J].Publications of the Astronomical Society of the Pacific,2009,121(886):1409-1418.

[4]Wacker L,Christl M,Synal H A.Bats:A new tool for AMS data reduction[J].Nuclear Instruments and Methods in Physics Research Section B:Beam Interactions with Materials and Atoms,2010,268(7):976-979.

[5]Jain A K.Data clustering:50 years beyond K-means[J].Pattern Recognition Letters,2010,31(8):651-666.

[6]Cool R J,Moustakas J,Blanton M R,et al.The prism multi-object survey (PRIMUS).II.data reduction and red-shift fitting[J].The Astrophysical Journal,2013,767(2):118.

[7]BatchelorBG.Patternrecognition:Ideasinpractice[M].NewYork：SpringerScience&BusinessMedia,2012.

[8]黄治国,王端.基于粗糙集的数据约简方法研究[J].计算机工程与设计,2009 (18):4284-4286.

[9]邓少波,关素洁,黎敏,等.属性与属性值合一的数据约简算法[J].模式识别与人工智能,2009 (2):195-201.

[10]Machinelearning:Anartificialintelligenceapproach[M].NewYork：SpringerScience&BusinessMedia,2013.

[11] 张学工.模式识别[M].北京：清华大学出版社,2010.

[12] 高新波.模糊聚类分析及其应用[M].西安：西安电子科技大学出版社,2004.

[13] 谢春丽,刘永阔.概念格理论属性约简算法研究[J].传感器与微系统,2012,31(3):116-118.

[14]ZhangZ,ZhangJ,XueH.ImprovedK-meansclusteringalgori-thm[C]∥CongressonImageandSignalProcessing,Cherbourg-Octeville,CISP’08,IEEE,2008:169-172.

[15] 李洁,高新波,焦李成.基于特征加权的模糊聚类新算法[J].电子学报,2006,34(1):89-92.

Data reduction based on open-angle measurement*

LI Chen， WANG Ya-ru， YUE Shi-hong

(School of Electrical Engineering and Automation,Tianjin University,Tianjin 300072,China)

Abstract:Data reduction has been an important issue of data mining including data compression,data adjustment,feature extraction,and so on,however,existing methods of data reduction mainly focus on reduction of features and dimensions,methods of reduction to the number of samples always limit to specific data sets which lack of generality.Aiming at general feature of data distribution in data sets,define a new kind of measurement based on opening angle.This measurement can distinguish essential difference of distribution between kernel objects and boundary objects,and realize data compression which takes kernel objects as center for data sets.By data reduction and test on 20 typical simple sets which have different features on UCI public test platform,the result demonstrates the proposed method can extract kernel objects in data sets effectively; by using the typical k-means algorithm to cluster the data sets before data reduction,cluster accuracy of reduced data sets is apparently higher than that of original data sets.

Key words:data reduction; direction angle; cluster analysis

DOI:10.13873/J.1000—9787(2016)04—0025—04

收稿日期：2015—07—28

*基金项目：国家自然科学基金资助项目(61174014)

中图分类号:TP 391.4

文献标识码:A

文章编号:1000—9787(2016)04—0025—04

作者简介:

李晨(1991-)，男，山西运城人，硕士研究生，主要研究领域为模式识别。

岳士弘，通讯作者，E-mail:shyue1999@tju.edu.cn。