数据挖掘分类算法研究综述
程建华
(九江学院信息科学学院软件教研室九江 332005 )
摘要：随着数据库应用的不断深化，数据库的规模急剧膨胀，数据挖掘已成为当今研究的热点。特别是其中的分类问题，由于其使用的广泛性，现已引起了越来越多的关注。对数据挖掘中的核心技术分类算法的内容及其研究现状进行综述。认为分类算法大体可分为传统分类算法和基于软计算的分类法两类。通过论述以上算法优缺点和应用范围，研究者对已有算法的改进有所了解，以便在应用中选择相应的分类算法。
关键词：数据挖掘；分类；软计算；算法
Review of Classification Algorithms in Data Mining
CHENG Jianhua
(Department of Computer Science,Jiujiang University, Jiujiang 332005, China)
ABSTRACT: With the application of database deepening and the size of database expanding quickly, Da
ta Mining has recently become the hotspot. Classification, the problem among them especially because of its extensive usage, has acquired more and more concerns presently. 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. 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..
KEYWORDS: data mining；classification；soft computing；algorithm
1引言
1989年8月，在第11届国际人工智能联合会议的专题研讨会上，首次提出基于数据库的知识发现(KDD，Knowledge DiscoveryDatabase)技术[1]。该技术涉及机器学习、模式识别、统计学、智能数据库、知识获取、专家系统、数据可视化和高性能计算等领域，技术难度较大，一时难以应付信息爆炸的实际需求。到了1995年，在美国计算机年会(ACM)上，提出了数据挖掘[2](DM，Data Mining)的概念，由于数据挖掘是KDD过程中最为关键的步骤，在实践应用中对数据挖掘和KDD 这2个术语往往不加以区分。
基于人工智能和信息系统，抽象层次上的分类是推理、学习、决策的关键，是一种基础知识。因而数据分类技术可视为数据挖掘中的基础和核心技术。其实，该技术在很多数据挖掘中被广泛使用，比如关联规则挖掘和时间序列挖掘等。因此，在数据挖掘技术的研究中，分类技术的研究应当处在首要和优先的地位。目前，数据分类技术主要分为基于传统技术和基于软计算技术两种。
2传统的数据挖掘分类方法
2.1 数据分类中相似函数的研究
数据分类首先涉及到样本间的相似度判定函数，向量相似性判定函数可根据向量特征可比性以及是否能满足距离三角不等式加以区分，而不满足距离三角不等式的向量相似性判定函数可根据互近邻距离等来判定。当向量特征是非同质的，简单地使用上述相似性判定函数是不合适的；而对于不同质的特征，使用不同的相似
性判定函数也是困难的，因为：①不同判定函数之间的综合判定很困难；②某些向量特征取决于质；③即使取决于特征量，用于相似性判定函数的离散值或区间值也需进一步研究。
对于离散的向量特征，人们提出了简单匹配系数、Jaccard系数、Rao系数等相似性判定函数，但在实际使用中却存在很多限制，且这只适用于离散值数量较少的情况。目前，非
字符常量合法
作者简介：程建华（1982-），女，汉族，江西九江，研究生，主要研究方向为数据挖掘、信息安全。
同质、离散、半连续半离散以及同质的相似性判定函数的研究成果还比较少。但以上讨论仅限于在两个向量之间，在实际分类过程中，也会涉及两个类别之间相似程度(距离)的计算，因为这无论在分类过程中还是评价分类质量时都是必不可少的。在实际应用中，类别间相似程度的计算函数主要包括最近距离函数、质心距离函数、平均距离函数等。
2.2传统数据分类方法
分类技术针对数据集构造分类器，从而对未知类别样本赋予类别标签。在其学习过程中和无监督的聚类相比，一般而言，分类技术假定存在具备环境知识和输入输出样本集知识的老师，但环境及其特性、模型参数等却是未知的。
2.2.1基于关联规则(CBA： Classification Based on Association Rule)的分类算法
该算法的构造分类器可分为两步：第一步要发现所有形如xi1∧xi2 => Ci的关联规则，即右侧均为类别属性值的关联规则；第二步要选择高优先度的规则来覆盖训练集，即若有多条关联规则的左侧均相同，而右侧为不同的类时，则选择具有最高置信度的规则作为可能规则。CBA算法主要是通过发现样本集中的关联规则来
构造分类器。关联规则的发现采用经典算法Apriori，通过迭代检索出数据集中所有的频繁项集，即支持度不低于用户设定阈值的项集。
此算法的优点是发现的规则相对较全面且分类准确度较高，其缺点是：①当潜在频繁2项集规模较大时，算法会受到硬件内存的制约，导致系统I/O负荷过重；②由于对数据的多次扫描和JOIN运算所产生潜在频繁项集，Apriori算法的时间代价高昂。针对Apriori算法的缺陷，LIG(large items generation)算法在求解频繁1项集的同时计算相应项的相关区间，以此得到缩小了的项集的潜在频繁2项集。
频繁模式增长(FP)算法放弃利用潜在频繁项集求解频繁项集的做法，进而提出频率增长算法。该算法通过扫描数据集得到频繁项的集合以及各项支持度，并按支持度大小降序排列频繁项目列表，然后通过构造一个FP树来进行关联规则挖掘。其优点是：在完备性上，它不会打破任何模式且包含挖掘所需的全部信息；而在紧密性方面，它能剔除不相关信息，并不包含非频繁项，故支持度高的项在FP 树中共享机会也高。该算法比Apriori快一倍，但当数据集过大时，所构建的FP 树仍受内存制约。
2.2.2判定树的归纳分类
判定树是一个类似流程图的树结构，其中每个内部节点表示在一个属性上的测试，每个分支代表一个测试输出，而每个树叶节点代表类或类分布。树的最顶层节点是根节点。由判定树可以很容易得到“IFTHEN”形式的分类规则。方法是沿着由根节点到树叶节点的路径，路径上的每个属性-值对形成“IF”
部分的一个合取项，树叶节点包含类预测，形成“THEN”部分。一条路径创建一个规则。
判定树归纳的基本算法是贪心算法，它是自顶向下递归的各个击破方式构造判定树。其中一种著名的判定树归纳算法是建立在推理系统和概念学习系统基础上的ID3算法，如下所示。
(1)算法：由给定训练数据产生判定树。
(2)输入：训练样本samples，由离散值属性表示；候选属性的集合attribute_list。
(3)输出：一棵判定树。
(4)方法：
①创建节点N；
②ifsamples都在同一个类Cthen
③返回N作为叶节点，以类C标记；
④ifattribut_list为空then
⑤返回N作为叶节点，标记samples中普通的类；
(5)选择attribute_list中具有最高信息增益的属性test_attribute；
(6)标记节点N为test_attribute
for each test_attribute中的已知值ai//划分samples
由节点N长出一个条件为test_attribute=ai的分枝；
(7)设si是samples中test_attribute=ai的样本的集合；
(8)if  si为空then 加上一个树叶，标记为samples中最普通的类；
Else 加上一个由Genetate-decision-tree(si，attribute-list-test-attribute)返回的节点。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。