第埠熟
微机发展
压叩
数据挖掘中分类算法的研究及其应用罗海蛟‘刘显长沙交通学院计算机工程系湖南长沙深圳大学广东深圳
摘要分类算法是数据挖掘中的最重要的技术之一作者对具有代表性的分类算法进行了分析和比较并应用分类方法在居民出行数据中挖掘出一些公交乘客规则讨论了数据挖掘方法在公交乘客预测中应用的前景和实效
关健词数据挖掘分类决策树决策支持
中图分类号二玛文献标识码文章
编号
一一
张,川
川昭
一庆加段郎冶飞飞祖郎
以欣汕丫犯
印而眼
阳
刀班巴仁
月
〕
司】心沁讹场姗邓钾刁映司
”歇召
叮悯七
玩
引言数据挖掘也可以称为数据库中的知识发现是从大量数据中提取出可信新颖有效并能被人理解的模式的高级处理过程作者在给出数据挖掘基本概念的基础上着重讨论了数据挖掘中分类方法的一些算法并
将其应用于对城市居民出行数据的分析利用分类规则力图发现居民出行数据中公交乘客的一些规则为公交预
测优化决策提供依据
问题的科学核技术人工智能目标非常高除需要复杂算
法外还需要特定的系统但仅仅利用人工智能中一些已经成熟的算法和技术
基本概念
数据挖掘川川堪是一个交叉学科领域受多个学科的影响包括数据库系统统计学机器学习可
视化和信息科学等数据挖掘实质上是一种决策支持过
程其主要技术手段是统计方法包括数理统计方法多元
统计方法计量经济学和时间序列分析方法等此外运筹学人工神经网络和专家系统技术的发展也为数据挖
掘提供了新的思路它的主要特点是能高度自动分析企业原有的数据归纳推理从中挖掘出潜在的模式预测客户的行为帮助决策者作出正确的决策技术基础是
统计学与人工智能人工智能是以自动机为手段通过模拟人类宏观外显的思维行为从而高效率地解决现实世界
收稿日期
一一巧
作者简介罗海蛟一男江西人硕士研究方向为软件工程
数据挖掘中分类算法概述分类是数据挖掘中的一个重要课题分类的目的是学会一个分类函数或分类模型也常常称作分类器该模型能把数据库中的数据项映射到给定类别中的某一个
分类可用于提取描述重要数据类的模型或预测未来的数据趋势分类可描述如下输人数据或称训练集是一条条的数据库记录川〕组成的每一条记录包含若干条属性
组成一个特征向量训练集的每条记录还有一个特定的类标签睽玩与之对应该类标签是系
统的输人通常是以往的一些经验数据一个具体样本的形式可为样本向量,,,…,在这里,表示字段值。表示类别
分类的目的是分析输人数据通过在训练集中的数据表现出来的特性为每一个类找到一种准确的描述或者模型这种描述常常用谓词表示由此生成的类描述用来对未来的测试数据进行分类尽管这些未来的测试数据的类标签是未知的我们仍可以由此预测这些新数据所属的类注意是预测而不能肯定我们也可以由此对数
据中的每一个类有更好的理解也就是说我们获得了对年月
罗海蛟等数据挖掘中分类算法的研究及其应用
这个类的知
识
有三种分类器评价或比较尺度预测准确度预测准确度是用得最多的一种比较
尺
度特别是对于预测型分类任务目前公认的方法是番分层交叉验证法计算复杂度计算复杂度依赖于具体的实现细节和硬件环境在数据挖掘中由于操作对象是巨量的数据库因此空间和时间的复杂度问题将是非常重要的一个环节模型描述的简洁度对于描述型的分类任务模型描述越简洁越受欢迎例如采用规则表示的分类器构造法就更有用大部分分类算法是内存驻留算法最
近出现了一些可
伸缩的分类技术能够处理大量的驻留在磁盘的数据分类技术有很多如决策树贝叶斯网络神经网络遗传算法一最临近分类等等本文重点是详细讨论了决策树中相关算法人工神经网络人工神经网络是大量的简单神经元按一定规则连接构成的网络系统它能够模拟人大脑的结构和功能采用某种学习算法从训练样本中学习并将获取的知识存储在网络各单元之间的连接权中连接权值是一个分布式矩阵结构神经网络的学习体现在神经网络权值的逐步计算包括反复迭代或累加上主要有三种神经网络模型前向神经网络后向神经网络自组织网络在数据挖掘领域主要采用前向神经网络提取分类规则从神经网络中采掘规则主要有以下两种倾向①网络结构分解的规则提取它以神经网络隐层节点和输出层节点为研究对象把整个网络分解为许多单层子网的组合这样研究较简单的子网便于从中挖掘知识的算法和飞的算法是有代表性的方法但此类方法的缺点是通用性差且当网络比较复杂时算法的复杂性高容易产生组合爆炸问题②由神经网络的非线性映射关系提取规则这种方法直接从网络输人和输出层入手不考虑网络的隐层结构避免了基于结构分解的规则提取算法的不足段等人的相似权值法以及在此基础上的罗算法将网络输入扩展到连续值取值是其中典型的两种算法但是神经网络规则提取还存在诸多问题如进一步降低算法的复杂度提高所提取规则的可理解性及算法的适用性等需要进一步的研究遗传算法遗传算法是模拟生物进化过程的全局优化方法将较劣的初始解通过一组遗传算子繁殖—即选择交叉—即重组变异—即突变在求解空间按一定的随机规则迭代搜索直到求得问题的最优解遗传算法具有的隐含并行性易于和其它模型结合等性质使得它涉足于数据挖掘领域表现在以下几个方面①用它和算法结合训练神经网络然后从网络提取规则②分类系统的设计目前研究重点是一些基本设计方法如编码方式信任分配函数的设计以及遗传算法的改进上遗传算法用于数据挖掘存在的问题是算法较复杂还有收敛于局部极小的过早收敛等难题未得到解决决策树分类算法决策树技术访是用于分类和预测的主要技术决策树学习是以实例为基础的归纳学习算法它着眼于从一组无次序无规则的事例中推理除决策树表示形式的分类规则它采用自顶向下的递归方式在决策树的内部节点进行属性值的比较并根据不同属性判断从该节点向下的分支在决策树的叶节点得到结论所以从根到叶节点就对应着一条合取规则整棵树就对应着一组析取表达式规则其有很多实现算法下面作一阐述算法司提出的著名的学习算法它通过选择窗
口来形成决策树是利用信息论中的互信息信息增益寻
找数据库中具有最大信息量的属性字段建立决策树的一个节点再根据该属性字段的不同取值建立树的分支在每个分支子集中重复建立树的下层节点和分支过程这种方法的优点是描述简单分类速度快特别适合大规模的数据处理但】算法是借用信息论中的互信息作为
单一属性能力的度量试图减少树的平均深度忽略了叶
子数目的研究其启发式函数并不是最优的存在的主要问题有①互信息的计算依赖于属性取值的数目较多的特
征而属性取值较多的属性不一定最优②是非递增学习算法③抗噪性差训练例子中正例和反例较难控制改进算法有等算法以及口银引进可调
错误率
一
司二概
念算法等
算法在决策树的构造过程中采用了预排序和广度优先技术在一般决策树中使用信息量作为评价节点分裂质量的参数算法中使用垃指标代替信息量对数据集包含个类的数据集定义为一艺勿
乌是中第类数据的频率越小
砚
越大区别于一般的决策树采用二分查找树结构
对每个节点都需要先计算最佳分裂方案然后执行分裂对于数值型连续字段一。分裂的形式二,
所以可以先对数值型字段排序假设排序后
的结果为,,…因为分裂只会发生在两个节点
之间所以有一种可能性通常取中点,‘,忍
作为分裂点从小到大依次取不同的画取
指标最大川最小的一个就是分裂点因
为每个节点都需要排序所以操作的代价极大降低排序微机发展第卷成本成为一个重要问题算法对排序有很好的解决方案对于离散型字段以设为的所有可能的值分裂测试将要取遍的所有子集寻找当分裂成和一两块时的指标取到垃最小的时候就是最佳分裂方法显然这是一个对集合的所有子集进行遍历的过程共需要计算”次代价也
是很大的算法对此也有一定程度的优化
算法能够处理比以所能处理的大得多
的训练集因此在一定程度上具有良好的随记录个数
和
属
性个数增长的可扩展性然而它仍然存在如下缺点①由于需要将类别列表存放于内存而类别列表的长度与训练集的长度是相同的这就一定程度上限制了可以处理的数据集的大小②由于采用了预排序技术而排序算法的复杂度本身并不是与记录个数成线性关系因此使得算法不可能达到随记录数目增长的线性可扩展性为户口类型第二个测试属性为职业第三个测试属性为年龄根据决策树各层分类结果及乘坐公交出行人数所占比重我们可以发现暂住人口公交出行比例远大于常住人口第二个测试属性职业也是符合现实情况职业不同收入较低及个体经营者公交出行比重较大其它类似不作赘述如果有统计局的人口详细信息根据决策树图我们可以得出公交预测数据为宏观交通规划提供辅助决策依据总结数据挖掘中分类和预测是重要的部分之一分类算法有很多近来出现了很多新的改进算法基于粗糙集的并行决策树算法基于贝叶斯的算法等分类方法
不
只是用于交通预测在政府经济计划辅助决策保险业银行股票交易等领域也大有作为可以为管理人员决策人员控制投资风险提供有力的决策支持
数据挖掘分类技术在公交预测
的应用
上面讨论的各类算法各有优缺点很难找到一个可以满足各方面需求的分类算法因此在具体工作中必须根据数据类型特点及数据集大小选择合适算法在某市的交通规划预测项目中采用数据挖掘的决策树分类方法应用于该市居民的日出行数据得出居民日出行数据中公交乘客预测决策树图为今后居民公交出行预测提供了坚实的数据基础为优化决策提供了依据
经过连续数据的离散化我们采用的训练集记录包含
属性为编号年龄户口类型职业公交出行与否由于
记录数不是特别大故可采用内存驻留类的算法这儿采
用。算法得到决策树其中每个测试属性由算法自动
选取根据在根节点训练集记录总数
为其中乘坐公车的为所占百分比为该决策树得到的第一个选取的分类的测试属性
参考文献
【块冶川
肠
咖」肠堪】访巧心搜
一【」人盯而拓而〔冶拓【」阳罗皿
冶艰
飞
【」弋
凡段叨叮即过
议肠
川,堪
【〕阴
即
段【〕刘红岩挖掘中的数据分类算法综述【〕清华大学学报自然科学版仁藤田宏一基础信息论〔〕魏鸿骏陈尚勤译北京
国
防工业出版社
【郑纬民黄刚数据挖掘纵览〔入〕」清华大学计算
机系见冷代菊印如一位
州卜卜卜卜叫卜卜斗卜卜卜一卜卜卜州卜州卜州卜十州卜州卜叫卜卜卜礴卜州卜一十十州卜州卜卜州卜诵卜一卜一诵」卜卜叫卜十卜一卜卜月叫卜州卜卜
上接第
页
用实现智能模块并用语言实现通信接
口将虚拟仪器和智能模块装于同一机器或通过网络连接的不同机器上
这对于实时性要求较高的虚拟仪器应在其智能行为上有所取舍首先满足其基本的功能和要求
结束语通过在虚拟仪器中集成技术大大地扩展了虚拟
仪器的功能使其更具有象人一样的推理思维的能力在智能模块中还可切换其知识库映像使虚拟仪器象多
面
手一样完成各种信号测试与处理任务但是应看到人
工智能推理技术尚存在推理效率不高实时性差等
缺点
参考文献【〕刘君华现代检测技术与测试系统设计〕西安西安交通大学出版社
【王永庆人工智能原理与方法〔〕西安西安交通大学出版社【张风均肠力开发人门与进阶〔〕北京北京航空航天大学出版社〔」印鉴刘星成汤庸专家系统原理与编程【」北京机械工业出版社