关于我们
在线留言
联系我们
首页  论文指导  教育论文  医学论文  英语论文  经济论文  管理论文  计算机论文  艺术论文  财会论文  理工论文
   
  您现在的位置:忠信论文网首页 > 论文指导 > 本工作室创作论文作品案例

浅析组合数据预处理在遗传算法中的应用

来源:诚信论文网     更新时间:2008-10-03      文字:[    ]
                  
                     浅析组合数据预处理在遗传算法中的应用
                                   摘   要
现实中的数据极易受噪声数据、空缺数据和不一致数据的侵扰。在数据挖掘之前利用数据处理技术进行数据处理,可以显著地提高挖掘模式的总体质量和减少实际挖掘所需要的时间。本文给出了一种基于遗传算法的组合数据清理方法,以学生成绩作为试验对象进行了分析和研究,试验结果证明有效地去除了数据中的噪声,纠正了数据中不一致。
关键词:数据挖掘 数据预处理 遗传算法
 
           Data Preprocessing Algorithm Based on Genetic Algorithm
 
                                  Abstract
 
Real world datas are incomplete ,noisy and inconsistent. Datas need to be preprocessed to be more cleaning and integrated before data mining .This paper presents a data preprocessing algorithm based on Genetic Algorithm. A model applied in students grade research is set up and gets valid results.
 
Key Word: data mining  data preprocessing  Genetic Algorithm

1引言

现实世界中的数据极易受噪声数据、空缺数据和不一致数据的侵扰,通常具有杂乱性、冗余性、不完整性 。数据清理[1]指消除噪声和不一致数据。常用的清理方法是根据不同的数据背景采用如平均、分类、聚类、预测、相关性分析[2]等方法,对真实值进行估计,但比较通用的算法目前还没有。
对于同一数据进行处理,可以用多种方法,每种方法都有各自的优点和缺陷,为了有效的利用各种模型的优点,回避其缺点,将不同的方法进行组合,只要选好权重便可以得到较好的处理结果。实践证明,任何一个独立模型,哪怕是效果不佳的模型,只要它含有独立的系统信息,当与一个较好的方法进行组合后同样可以改善结果精度,增强模型的可靠性。本文介绍的是一种相对通用的算法,它综合利用各种单一算法的估计结果,然后加权平均,其中最优权的确定利用遗传算法[3]。建立了组合模型,以学生成绩为例进行试验分析和研究。

2组合模型的建立

对于噪声数据,我们处理办法是先删除再修补。我们只针对一个缺失数据进行修补,大量的数据缺失可以采用循环的办法解决。

2.1求解组合模型最优权系数的遗传算法

求解组合模型最优权值的遗传算法[4]如下:
适应度函数的定义:
采用此目标函数的倒数 的最大值。
采用下标子集T的二进制编码方案。从[O, 1]中随机选取T个点Xj, Xj (j=1,2,..., T)为一个染色体,T为群体规模,取值一般从10到160之间[5]
交叉概率控制着交叉操作被使用的频度。一般取0.25到1.00之间。变异在遗传算法中属于辅助性的搜索操作,通常取变异概率为0.001左右。
本文采用排序选择机制。首先依据各个个体的适应度大小进行排序,适应度最大的安排在第一号,最小的安排在第n号(设群体规模等于n)然后基于所排序号按某种规则进行选择,排在前面的个体有较多被选择的机会。本文采用如下算法描述的线性函数选择方案,其中,偏置bias对选择强度有影响,当bias=2.0时,第一号个体被选择的次数大致等于正中间个体被选择次数的两倍。

……

……

……

……

图1为遗传算法的流程图,具体步骤如下:
1、初始化
确定群体规模T,误差精度dalta,交叉概率Pc,变异概率Pm确定编码规则。
2、选取初始解
从[0,1]中随机选取T个点XjXj (j =1,2,..., T)为一个染色体,T为群体规模,它对应一个n×m位二进制编码,由T个染色体构成匹配集P1,并分别计算适应度函数F(Xj),转第三步
3、判别收敛条件
若 ,FmaxF(Xj) (j=1,2,…,TXj P1)中的最大值:
4、迭代:
    
计算每一代个体的生存概率,,然后根据上述排序选择函数Linear()设计选择策略,个体生存概率大则被选择的概率也大。交叉是根据交叉概率P交换两个个体之间对应的分量。变异是在交叉完成后,根据变异概率Pm改变个体二进制串上某一位。通过选择、交叉、变异逐步将适应度高的个体放入匹配集P2中,直 为止。
然后更新P1 ,P1      转第三步。
5、输出满足精度要求最大适应值F(X)和最优权向量X=(Xl,...,X.),用以上遗传算法求出最优权值后,利用模型 可以得到最优修补值。

2.2试验模型

表1给出的资料是本校电信学院某班2005~2006学年度第一学期的成绩中的样本数据,利用我们给出的算法将其补齐。
表1 学生成绩表

学号
高数
物理
计算机基础
英语
0605980101
88
89
94
80
0605980102
87
82
96
75
0605980103
78
85
90
77
0605980104
90
89
93
83
0605980105
70
78
75
60
0605980106
60
89
76
55
0605980107
79
67
79
79
0605980108
90
97
95
83
0605980109
88
90
89
60
0605980110
50
67
70
62

算法1: 按行(记录)求平均值:计算空缺值所在记录的非空缺值得平均值。得到的预测值是y1=77。
算法2: 用贝叶斯分类法:首先把成绩分为及格和不及格两种形式,我们希望分类的未知样本是“coursel=“及格”,course2=“及格”,course3=“不及格”。然后按贝叶斯分类法把course4分为及格和不及格两类,最后,根据空缺值所在的类的属性的平均值推测出。得出的预测值是y2=79。
算法3: 按行求线性回归:用“最小二乘法”求出回归方程,得出的预测值是y3=45。
算法4: 按列求线性回归:算法同3,不过所用的数据是空缺值所在列的非空缺值的数据,得出的预测值是y4=84。
算法5: 聚类算法(采用k-means算法):流程如下:
1、随机地选择2个对象(此处要将这些数据聚为两个类:成绩高与成绩低),每个对象初始地代表一个簇的平均值或中心
2、 repeat
3、根据簇中对象的平均值,将每个对象(重新)附给最类似的簇
4、更新簇的平均值,即计算每个簇中对象的平均值
5、until不再发生变化。
根据上述算法预测出y5=78。
表2 算法比较

算法
估计值
误差值
1
77
14
2
79
12
3
45
56
4
84
7
5
78
11
组合算法
95
4

2.3试验结果分析

综合上述5种算法对比分析如下:
算法1最简单,运算速度最快,但估计值不准算法2和算法5较准确地估计出了空缺值,他们分别利用了分类和聚类的算法算法3和4在数据集存在发展趋势时,估计值较准确,不然偏差较大组合算法利用遗传算法加权平均,得到最佳估计值Y=95,真实值Y=91,但它的不足之处是速度较慢。

3 结论

本文研究的是数据挖掘中的数据清理技术。针对现实生活中数据的不完整和不一致性,提出了一种基于遗传算法的组合数据清理方法,以便去掉数据中的噪声,实现数据的完整。通过理论分析和建立组合模型并以学生成绩作为试验对象进行研究和分析,试验结果证明了该算法的可行性和有效性。
 

参考文献

[1] M. A. Hernandez, S. J. Stolfo. Real-world is Dirty:Data Cleaning and The
Merge/Purge Problem.Data Mining and Knowledge Discovery.1998,2(4):131一133.
[2] Han Jiawei, kamber Micheline,数据挖掘概念与技术.范明,孟小峰译.北京,机械工业出版社,2001: 70-95.
[3] 王小平,曹立明.遗传算法一理论应用与软件.西安:西安交大出版社,2002
[4] 柳莺,赵艳红.数据仓库技术研究和应用探讨.计算机应用,2001,21 (2) :46-48.
[5] 陈国良,王煦法,庄镇泉等遗传算法及其应用一北京:人民邮电出版社,1999:159-163.

 

 


返回上一页  关闭窗口  打印页面   
 
  热点论文
·部分科技期刊
·如何写出一篇优秀的文章
·24小时服务
·刊物涵盖范围全
·工作室活动
·部分医药期刊
·实力雄厚团队
·河北省与山东省经济差异的比
·部分经济期刊
·论文指导注意点
  推荐论文
·材料在脉冲X射线辐照下热-力
·弯曲运行带式输送机转弯设计
·激波与固体火箭发动机装药裂
·炸药爆轰及水下爆炸的SPH数值
·渐开线圆柱齿轮接触分析和修
·湿陷性黄土地基处理试验及路
·软土地基热水力耦合本构模型
·基于ALE方法求解流固耦合问题
·刚性球斜冲击下延性靶动态响
·钛合金环壳零件冲压成形数值

 
 

  

 

24小时咨询热线:13515125107 李老师   Email:025past@163.com  客服QQ:82612722

Powered by www.025pass.cn

忠信论文网专注论文与设计,24小时竭诚为您服务

Copyright©2002 www.025pass.cn Inc.

 All rights reserved. 忠信论文网 版权所有

 

 

 

110举报不良网站

CNNIC认证顶级域名

 

ICANN认证顶级域名

360绿色网站

不良网站举报