基于集成学习的无监督离散化算法

摘要：模式识别与机器学习的一些算法只能处理离散属性值，而在现实生活中的很多数据具有连续的属性值，针对数据离散化的问题提出了一种无监督的方法。首先，使用Kmeans方法将数据集进行划分得到类别信息；然后，应用有监督的离散化方法对划分后的数据离散化，重复上述过程以得到多个离散化的结果，再将这些结果进行集成；最后，将集成得到的最小子区间进行合并，这里根据数据间的邻居关系选择优先合并的维度及相邻区间。其中，通过数据间的近邻关系自动寻求子区间数目，尽可能保持其内在结构关系不变。将离散后的数据应用于聚类算法，如谱聚类算法，并对聚类后的效果进行评价。实验结果表明，该算法聚类精确度比其他4种方法平均提高约33%，表明了该算法的可行性和有效性。通过该算法得到的离散化数据可应用于一些数据挖掘算法，如ID3决策树算法。

关键词：无监督离散化；集成学习；分类数据；相似性；谱聚类

中图分类号： TP391； TP18

文献标志码：A

Abstract： Some algorithms in pattern recognition and machine learning can only deal with discrete attribute values， while in real world many data sets consist of continuous data values. An unsupervised method was proposed according to the question of discretization. First， Kmeans method was employed to partition the data set into multiple subgroups to acquire label information， and then a supervised discretization algorithm was applied to the divided data set. When the process was repeatedly executed， multiple discrete results were obtained. These results were then integrated with an ensemble technique. Finally， the minimum subintervals were merged after priority dimensions and adjacent intervals were determined according to the neighbor relationship of data， where the number of subintervals was automatically estimated by preserving the correlation so that the intrinsic structure of the data set was maintained. The experimental results of applying categorical clustering algorithms such as spectral clustering demonstrate the feasibility and effectiveness of the proposed method. For example， its clustering accuracy improves by about 33% on average than other four methods. Discrete data attained can be used for some data mining algorithm， such as ID3 decision tree algorithm.

Key words： unsupervised discretization； ensemble learning； categorical data； similarity； spectral clustering

0引言

现实世界的数据很多都是呈连续属性，但是大部分机器学习算法（如决策树算法），只适合处理离散属性值。为了能够很好地应用这些算法，需要对连续属性值的数据进行离散化处理，使其转变为离散属性。因此，离散化是一种重要的预处理技术，尤其在频繁项集发现应用中很重要[1]，离散化是指将数值的值域划分为若干区间，将这些区间标号变为离散属性。离散化算法要求能识别连续属性与离散属性的对应关系。对训练样本进行离散化处理，有如下优点：1）离散化可以降低机器学习的复杂度，对ID3学习算法的训练样本进行离散化处理后，其学习率比动态算法提高了，这点在将连续属性转变为离散属性[2]中得到验证。2）可将连续数值划分为可被人类理解的结果，如可将学生成绩分为及格、中等、优秀等。

根据离散化过程中区间的划分可分为自底向上（bottomup）和自顶向下（topdown）方法：前者这个是指代“自底而上”吗？若是的话，只有关于前者的描述，没有对于后者的论述吗？请明确。是将初始的每一个属性值作为一个区间，然后迭代地合并相邻区间，利用停止准则结束离散化，最终将连续属性离散成数目少、有实际意义有代表性的若干个区间；而后者是个相反的过程，将最小与最大的属性值作为一个区间，然后逐步进行划分得到最终的离散结果。有监督算法和无监督离散化算法，可根据数据是否具有类别信息来区分。静态和动态的离散化：前者仅仅考虑单个属性，执行过程独立于学习算法；后者考虑属性之间的联系，并在分类器被建立的同时执行，如ID3、C4.5决策树。单属性和多属性离散化：前者是在离散每一个连续属性时，均以一个独立于其他属性的方式对属性值进行合并或分割；后者还会考虑到属性与属性之间的相关性，如基于主成分分析的无监督关系保持离散化方法[3]。

1相关研究

典型的有监督的算法如ChiMerge[4]，通过测试相邻区间的卡方值来确定是否合并，但要设定参数阈值会产生很多缺陷；改进的Chi2[5]通过数据间的不一致率来作为区间合并的停止准则，但会降低原始数据的可信度，产生分类错误。Yang等[6]首先提出了成比例的k区间离散化方法，通过按比例地修改区间大小和区间数来调整离散化偏差和方差，以适应Naive贝叶斯分类器，该算法是小样本的优化问题，不适合于大数据的处理。基于区间距离的离散化算法[7]需要用户定义区间数目。

针对无标签的数据进行离散化，即无监督的算法，在Dougherty等[8]提出的算法中最简单的为等宽与等频率的算法，虽然都易于实现，但都忽视了数据分布信息，因而区间边界的确定不具有代表性；Kmeans离散化方法，对于数值型的离散化而言，采用欧几里得距离作为区间划分的依据缺乏理论根据。此外，该算法依靠用户来指定区间数目，不能自动确定区间数；保持关系的离散化方法，考虑属性间的相关性通过主成分分析（Principal Component Analysis， PCA）降维的方法来离散，对于高维非线性可分的数据离散效果不佳；基于混合概率模型的无监督离散化方法[9]，将数值属性的值域划分为若干子区间，再通过贝叶斯信息准则自动的寻求子区间数目和划分方法，在离散化过程中针对不同的属性离散化时间可能相差较大。

目前应用最广泛的有：监督算法是类属性关系最大化（ClassAttribute Interdependence Maximization， CAIM）算法[10]，综合考虑类与属性之间的相关性，通过最大化相互依赖性来选择合适的切断点，能很好地保持数据的内在结构，可能会导致划分的区间数目与类数之间过拟合；以及后来提出的基于类属性应变系数（ClassAttribute Contingency Coefficient， CACC）的离散化算法[11]，即类属性相关系数的离散化算法。

无监督离散化方法分为基于树的无监督离散化方法[12]和基于核函数的无监督离散化方法[13]。前者是建立树的模型，切断点的位置选择在左边和右边的对数似然最大化；后者是计算区间中点的得分函数来选择切断点的位置。最后都通过交叉验证的方法自动寻求划分停止的位置，这种自上而下的方法可能导致区间数目过多，丢失的信息也比较多。

4结语

本文提出了一个基于集成学习的无监督离散化方法，其新颖之处有两点：1）利用集成学习的方法创建最小区间；2）根据数据集原始空间与离散空间的邻居相似性进行区间的合并，以尽可能保持数据内在结构。实验表明，所提算法的离散化过程能较好地保持数据集的内在结构，且离散化后的平均区间数较小。

但是本文的方法有一个缺点，即其计算复杂性较高。当Kmeans划分数据集K=N时，Kmeans的计算时间为O（N1.5），CAIM的计算复杂度则为O（N2.5），合并的过程则为O（dN2），所以本文算法的计算复杂度为O（N2.5）。如何降低其计算复杂度是未来需要完成的工作。

参考文献：

[1]SRIKANT R， AGRAWAL R. Mining quantitative association rules in large relational tables [C]// Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data. New York： ACM Press， 1996： 1-12.

[2]CATLETT J. On changing continuous attributes into ordered discrete attributes [C]// Proceedings of the European Working Session on Learning on Machine Learning， LNCS 482. Berlin： Springer， 1991： 164-178.

[3]MEHTA S， PARTHASARATHY S， YANG H. Toward unsupervised correlation preserving discretization [J]. IEEE Transactions on Knowledge and Data Engineering， 2005， 17（9）： 1174-1185.

[4]KERBER R. ChiMerge： discretization of numeric attributes [C]// Proceedings of the Tenth National Conference on Artificial Intelligence. Menlo Park： AAAI Press， 1992： 123-128.

[5]LIU H， SETIONO R. Chi2： feature selection and discretization of numeric attributes [C]// Proceedings of the Seventh IEEE International Conference on Tools with Artificial Intelligence. Washington， DC： IEEE Computer Society， 1995： 388-391.

[6]YANG Y， WEBB G I. Discretization for naiveBayes learning： managing discretization bias and variance [J]. Machine Learning， 2009， 74（1）： 39-74.

[7]RUIZ F J， ANGULO C， AGELL N. IDD： a supervised interval distancebased method for discretization [J]. IEEE Transactions on Knowledge and Data Engineering， 2008， 20（9）： 1230-1238.

[8]DOUGHERTY J， KOHAVI R， SAHAMI M. Supervised and unsupervised discretization of continuous features [C]// Proceedings of the Twelfth International Conference on Machine Learning. San Francisco： Morgan Kaufmann Publishers， 1995： 194-202.

[9]LI G. An unsupervised discretization algorithm based on mixture probabilistic model [J]. Chinese Journal of Computers， 2002， 25（2）： 158-164.（李刚.基于混合概率模型的无监督离散化算法[J].计算机学报，2002，25（2）：158-164.）

[10]KURGAN L A， CIOS K J. CAIM discretization algorithm [J]. IEEE Transactions on Knowledge and Data Engineering， 2004， 16（2）： 145-153.

[11]TSAI C J， LEE C I， YANG W. A discretization algorithm based on classattribute contingency coefficient [J]. Information Sciences， 2008， 178（3）： 714-731.

[12]SCHMIDBERGER G， FRANK E. Unsupervised discretization using treebased density estimation [C]// PKDD 2005： Proceedings of the 9th European Conference on Principles and Practice of Knowledge Discovery in Databases， LNCS 3721. Berlin： Springer， 2005： 240-251.

[13]BIBA M， ESPOSITO F， FERILLI S， et al. Unsupervised discretization using kernel density estimation [C]// Proceedings of the 20th International Joint Conference on Artificial Intelligence. San Francisco： Morgan Kaufmann Publishers， 2007： 697-701.

[14]BORIAH S， CHANDOLA V， KUMAR V. Similarity measures for categorical data： a comparative evaluation [C]// Proceedings of the 8th SIAM International Conference on Data Mining. Philadelphia： SIAM， 2008： 243-254.

[15]ZHANG S， WONG H S， SHEN Y. Generalized adjusted rand indices for cluster ensembles [J]. Pattern Recognition， 2012， 45（6）： 2214-2226.

[16]NG A Y， JORDAN M I， WEISS Y. On spectral clustering： analysis and an algorithm [C]// Advances in Neural Information Processing Systems. Cambridge： MIT Press， 2002： 849-856.

[17]THEODORIDIS S， KOUTROUMBAS K. Pattern recognition [M]. Waltham： Academic Press， 2003.