数据挖掘中分类方法综述

〔Ｋｅｙｗｏｒｄｓ〕data mining classification soft computing
１ 前 言
数据挖掘源于２０ 世纪 ９０ 年代中期，是一个既年轻又活 跃的研究领域，涉及机器学习、模式识别、统计学、数据库、 知识获取与表达、专家系统、神经网络、模糊数学、遗传算 法等多个领域。分类技术是数据挖掘中最有应用价值的技术 之一，其应用遍及社会各个领域。
〔Ａｂｓｔｒａｃｔ〕As one of the kernel techniques in the data mining, it is necessary to summarize the research status of classification algorithm. Classification algorithms can be divided into classical algorithms and algorithms based on soft computing, primarily including similar function, classification algorithms based on association rule, K-nearest Neighbor, decision tree, Bayes network and classification algorithms based on fuzzy logic, genetic algorithm, neural network and rough sets. By presenting the advantages and disadvantages and the application range of the algorithms mentioned above, it will be helpful for people to improve and select algorithms for applications, and even to develop new ones.
但以上讨论仅限于在两个向量之间，在实际分类过程中， 也会涉及两个类别之间相似程度（距离）的计算，因为这无论在 分类过程中还是评价分类质量时都是必不可少的。在实际应 用中，类别间相似程度的计算函数主要包括最近距离函数、质
＊本文系国家自然科学基金资助项目“用于数据挖掘的神经网络模型及其融合技术研究”（项目编号：６０２７５０２０）课题研究成 果之一。
缺点：①BP神经网络学习算法本身存在一些不足（见下文）；②
在其测算属性权值时，需逐个删除输入节点，但每次删除均 可能需要重新强化BP神经网络训练，故对于高维或大量的样 本，计算量过大。也有人使用最佳变化梯度来求证每个属性 的权重，但对于非线形的KNN算法，尤其当最佳函数存在多 个局部最小值时，线形的梯度调整很难保证方法的收敛性。 2.2 .3 决策树分类算法 决策树是以实例为基础的归纳学习 算法。它是一种从一组无次序、无规则的事例中推理出决策 树形式的分类规则。它采用自顶向下的递归方式，对决策树 内部的节点进行属性值比较，并根据不同属性值来判断该节 点向下的分支。但在建立决策树的过程中需要设置停止增长 条件，以使决策树能在适当的时候停止生长。同时，还要考 虑把决策树修剪到合适的尺寸，并尽量保持决策树的准确度。
〔关键词〕 数据挖掘 分类 软计算 〔分类号〕 TP183
Ａ Ｒｅｖｉｅｗ ｏｎ Ｃｌａｓｓｉｆｉｃａｔｉｏｎ Ａｌｇｏｒｉｔｈｍｓ ｉｎ Ｄａｔａ Ｍｉｎｉｎｇ Ｑｉａｎ Ｘｉａｏｄｏｎｇ School of Electrical Engineering and Automation, Tianjin University,Tianjin 300072
在基于决策树的分类算法中，ID３（C４．５）是较早的决策树 分类算法，其后又出现多种改进算法，其中SLIQ(supervised learning in quest)和 SPRINT(scalable parallelizable induction of decision tree)算法最具代表性。 2 .2 . 3 .1 ID３（C４．５）分类算法 Quinlan提出的ID３学习算法 通过选择窗口来形成决策树，它利用的是信息论中的互信息 或信息增益理论来寻找具有最大信息量属性而建立决策树节 点的方法，并在每个分支子集重复这个过程。该方法的优点 是描述简单、分类速度快、产生的分类规则易于理解。但此 算法抗噪性差，训练正例和反例较难控制。C４．５ 分类算法后 来虽得到改进，但仍存在算法低效问题，故不能进行增量学 习。 2 .3 . 3 .2 SLIQ分类算法［３］ 针对C４．５改进算法而产生的样 本集反复扫描和排序低效问题，SLIQ分类算法运用了预排序 和广度优先两项技术。预排序技术消除了结点数据集排序，广 度优先策略为决策树中每个叶子结点找到了最优分裂标准。 SLIQ算法由于采用了上述两项技术使其能处理比C４．５大得多
收稿日期：2006 － 03 － 25 修回日期：2006－ 07－ 23 本文起止页码：68－ 71，108
６８
图书情报工作
第 ５１ 卷第 ３ 期 ２００７ 年 ３ 月
·基金项目·
心距离函数、平均距离函数等。
2.2 传统数据分类方法
分类技术针对数据集构造分类器，从而对未知类别样本 赋予类别标签。在其学习过程中和无监督的聚类相比，一般 而言，分类技术假定存在具备环境知识和输入输出样本集知 识的老师，但环境及其特性、模型参数等却是未知的。 2 . 2. 1 基于关联规则（CBA: Classification Based on Association Rule）的分类算法 该算法［１］的构造分类器可分为两步：第 一步要发现所有形如xi1∧xi2 ＝> Ci的关联规则，即右侧均为类 别属性值的关联规则；第二步要选择高优先度的规则来覆盖训 练集，即若有多条关联规则的左侧均相同，而右侧为不同的 类时，则选择具有最高置信度的规则作为可能规则。CBA算 法主要是通过发现样本集中的关联规则来构造分类器。关联 规则的发现采用经典算法Apriori［１］，通过迭代检索出数据集中 所有的频繁项集，即支持度不低于用户设定阈值的项集。此 算法的优点是发现的规则相对较全面且分类准确度较高，其
基于人工智能和信息系统，抽象层次上的分类是推理、 学习、决策的关键，是一种基础知识。因而数据分类技术可 视为数据挖掘中的基础和核心技术。其实，该技术在很多数 据挖掘中被广泛使用，比如关联规则挖掘和时间序列挖掘等。 因此，在数据挖掘技术的研究中，分类技术的研究应当处在 首要和优先的地位。目前，数据分类技术主要分为基于传统技 术和基于软计算技术两种。
缺点是：①当潜在频繁２项集规模较大时，算法会受到硬件内 存的制约，导致系统I/O负荷过重；②由于对数据的多次扫描
和JOIN运算所产生潜在频繁项集，Apriori算法的时间代价高 昂。
针对Apriori算法的缺陷，LIG(large items generation)算法 在求解频繁１项集的同时计算相应项的相关区间，以此得到缩 小了的项集的潜在频繁２项集。频繁模式增长（FP）算法放弃利 用潜在频繁项集求解频繁项集的做法，进而提出频率增长算 法。该算法通过扫描数据集得到频繁项的集合以及各项支持 度，并按支持度大小降序排列频繁项目列表，然后通过构造 一个 FP－ 树来进行关联规则挖掘。其优点是：在完备性上，它 不会打破任何模式且包含挖掘所需的全部信息；而在紧密性方 面，它能剔除不相关信息，并不包含非频繁项，故支持度高 的项在 FP－ 树中共享机会也高。该算法比Apriori快一倍，但 当数据集过大时，所构建的FP－ 树仍受内存制约。 2 . 2. 2 K近邻（KNN）分类算法 KNN方法基于类比学习， 是一种非参数的分类技术，它在基于统计的模式识别中非常 有效，并对未知和非正态分布可取得较高的分类准确率，具 有鲁棒性、概念清晰等优点。其基本原理为：KNN 分类算法 搜索样本空间，计算未知类别向量与样本集中每个向量的相 似度值，在样本集中找出K 个最相似的文本向量，分类结果 为相似样本中最多的一类。
·基金项目·
ＬＩＢＲＡＲＹ ＡＮＤ ＩＮＦＯＲＭＡＴＩＯＮ ＳＥＲＶＩＣＥ Vol．５ １ ，No．３， March，２００７
数据挖掘中分类方法综述 ＊
钱晓东 天津大学电气与自动化工程学院 天津 300072
〔摘要〕 对数据挖掘中的核心技术分类算法的内容及其研究现状进行综述。认为分类算法大体可分为传统分类算法和基于软计 算的分类法两类，主要包括相似函数、关联规则分类算法、K近邻分类算法、决策树分类算法、贝叶斯分类算法和基于模糊逻 辑、遗传算法、粗糙集和神经网络的分类算法。通过论述以上算法优缺点和应用范围，研究者对已有算法的改进有所了解，以 便在应用中选择相应的分类算法。
或者修改原型法。这种方法包括建立一个原型和在原始训练 样本集中调整几个有限的数据，其中多数情况下采用神经网
络技术。③多重分类器的结合法。即由几个神经网络组成一
个分类器，其每个神经网络都担当一个１－最近邻分类器的作 用，对其中一个子集进行 １－ 最近邻计算，而这个子集基于 Hart’s方法产生。
各维权重对于相等 BP 神经网络可用于计算各维权值， 此方法虽然利用了神经网络的分类和泛化能力，但存在以下
值相同，即认定各维对于分类的贡献度相同，显然这不符合 实际情况。基于上述缺点，人们也采用了一些改进算法：当样 本数量较大时，为减小计算，可对样本集进行编辑处理，即 从原始样本集中选择最优的参考子集进行KNN计算，以减少 样本的存储量和提高计算效率。截止目前，其中最主要的方
法有［２］：①近邻规则浓缩法。其编辑处理的结果是产生一个样 本集的子集，然后在子集上进行KNN 算法的计算。②产生
但在大样本集和高维样本分类中（如文本分类），KNN方 法的缺陷也得以凸显。首先，KNN 是懒散的分类算法，对于 分类所需的计算均推迟至分类进行，故在其分类器中存储有 大量的样本向量。在未知类别样本需要分类时，在计算所有 存储样本和未知类别样本的距离时，高维样本或大样本集所 需要的时间和空间的复杂度均较高。其次，KNN算法是建立 在 VSM模型上的，其样本距离测度使用欧式距离。若各维权
２wenku.baidu.com传统的数据挖掘分类方法
2.1 数据分类中相似函数的研究
数据分类首先涉及到样本间的相似度判定函数，向量相 似性判定函数可根据向量特征可比性以及是否能满足距离三 角不等式加以区分，而不满足距离三角不等式的向量相似性判 定函数可根据互近邻距离等来判定。
当向量特征是非同质的，简单地使用上述相似性判定函 数是不合适的；而对于不同质的特征，使用不同的相似性判定
函数也是困难的，因为：①不同判定函数之间的综合判定很困 难；②某些向量特征取决于质；③即使取决于特征量，用于相
似性判定函数的离散值或区间值也需进一步研究。对于离散 的向量特征，人们提出了简单匹配系数、Jaccard 系数、Rao 系 数等相似性判定函数，但在实际使用中却存在很多限制，且 这只适用于离散值数量较少的情况。目前，非同质、离散、半 连续半离散以及同质的相似性判定函数的研究成果还比较少。
６９
·基金项目·
ＬＩＢＲＡＲＹ ＡＮＤ ＩＮＦＯＲＭＡＴＩＯＮ ＳＥＲＶＩＣＥ Vol．５ １ ，No．３， March，２００７
的样本集；但由于所需内存较多，这在一定程度上限制了可以 处理的数据集的大小；预排序技术也使算法性能不能随记录数 目进行线性扩展。 2 .2 . 3 .3 SPRINT分类算法［４］ 为了减少驻留于内存的数据 量，SPRINT算法进一步改进了决策树算法的数据结构，去掉 在SLIQ中需要驻留于内存的类别列表，将类别合并到每个属 性列表中。这样，在遍历每个属性列表中寻找当前结点的最 优分裂标准时，不必参照其他信息，使寻找每个结点的最优分 裂标准变得相对简单，但缺点是对非分裂属性的属性列表进 行分裂变得却非常困难，因此，此算法的可扩展性较差。