论文部分内容阅读
摘要：随着数据挖掘技术的兴起，各种应用于关联规则挖掘的算法也逐渐被关注。在数据库中除了能对数据的进行录入、查询、统计等简单功能应用，也能帮助用户发现大量数据中存在的各种有用的信息以及数据之间的关联性，帮助用户分析出其中有价值的信息，从而实现其中的商业价值。关联规则是数据挖掘领域的一个重要研究分支，其经典算法-Aprior算法被广泛采用，本文针对Aprior算法的局限性，将遗传算法应用在关联规则数据挖掘中进行分析并以某高校新生入学调查表中数据为例，挖掘出学校的环境、就业情况、校园社团活动、食堂用餐标准等因素与学生生源地情况及学生中学水平之间的相关联系，可以帮助高校在招生咨询和宣传中有所侧重，对不同地区的学生采取不同的宣传方式和宣传内容，来进一步扩大学校的招生规模。
关键词：遗传算法；数据挖掘；关联规则；招生宣传
中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2015）15-0181-02
Abstract： With the rise of data mining technology， various applied to association rule mining algorithms have gradually been concerned. In addition to the data in the database will be entry， query， statistics and other simple functional applications， but also to help users find the relevance of the presence of large amounts of data in a variety of useful information and data between， to help users analyze the valuable information， in order to achieve one of the commercial value. Association rules is an important research branch of data mining， which is the classical algorithm -Aprior algorithms are widely used， the limitations of this article for Aprior algorithm， genetic algorithm in association rule data mining for analysis and survey of a university freshmen the data， for example， to dig out the relevant contact the school environment， employment， campus community activities， canteen standards and other factors with students and student high school students to the situation between the level that can be focused on helping college admissions consulting and publicity for students in different regions to take a different form of publicity and promotional content， to further expand the enrollment of the school.
Key words： Genetic Algorithms；Data Mining；Association Rule；Admissions publicity
1 引言
1.1 数据挖掘
数据挖掘技术一般是指从海量数据中自动搜索隐藏于其中的有着特殊关联性的信息的过程。主要有数据准备、规律寻找和规律表示3个步骤。数据挖掘的任务有关联规则分析、分类分析、聚类分析、异常分析、特异群组分析以及演变分析等。其中的关联规则分析具有很多商业价值，被广泛的研究和应用。
1.2 关联规则
关联规则是数据库中存在的一类重要的可被发现的知识。如果两个或多个变量的取值之间存在某些规律性，就称为关联。关联分为简单关联、时序关联和因果关联。关联规则分析的目的是找出数据库中隐藏的关联性。人们有时并不知道数据库中数据的关联函数，因此关联分析生成的规则带有一定可信度。关联规则挖掘发现海量数据中属性之间有趣的关联或一定规律。
1.3 遗传算法
遗传算法是计算数学中用于解决最佳化的一种进化算法。进化算法最初是能过研究了进化生物学中的一些现象而发展起来的，这些现象包括了遗传、突变、自然选择以及杂交等。遗传算法一般用一种计算机模拟来实现。对于某个最优化问题，一定数量个体的抽象表示（称为染色体）的种群向更优的个体进化。
2 基于遗传算法的关联规则挖掘
2.1 学生入学调查数据进行遗传算法的编码方法
行遗传算法编码是应用遗传算法时要解决的主要问题，也是设计遗传算法的一个关键步骤。编码方法选择影响到交叉算子、变异算子等遗传算子的运算方法，在很大程度上决定了遗传进化的效率。时至今日人们已经提出了许多种不同的编码方法。本文采用实数数组的编码方案，因为其具备不仅简单、通用、鲁棒性强，适于并行分布处理等之外还方便了遗传算子的操作。在采用数组编码后的交叉、变异等操作实际上就成了对数组中数据进行操作，在本文中，我们把学生调查情况全部读入数据库，对一些属性进行合并，并适当对一些属性进行删除，重新建立了一个学生基本信息与学生调查信息数据库，如下表所示： 由于采用的是实数数组编码，其中一条规则就是一条实数编码串，又分为两个部分：规则的属性部分和规则类别，比如1131240=>122，所以我们要将属性值也用数值型来表示。例如如下几个表。
学生所在中学性质，分为两种情况，普通高中，职业高中，分别为其编码0，1。同时将分数等级等其它特征进行编码，在这里不一一列表。
结论属性表为分就业情况、校园环境、食堂消费水平、专业设置、校园文化五个表，表3为就业率注重情况表。
经过分析，编号和年龄属性与我们发现的关联知识没有关系，而性别属性也与我们发现的关联知识相关度不大，因此我们省略不用。
2.2 遗传算法的运行参数设定
遗传算法参数包括种群规模M、变量个数L、交叉概率Pc、变异概率Pm以及运算的终止进化代数T。参数的设定对算法的运行性能有着很大的影响，所以取值一定要认真。
2.2.1 种群规模M
种群规模M表示数据群体中所含调查个体的全部数量。其取值一定要适当，当数值太小时，遗传算法的运算速度提高了，但反映不出群体的多样式，也推理不出有价值的结论，造成遗传算法的早熟；而当M的取值太大时，遗传算法的运行效率会相应降低。所以，我们要综合这两个方面来考虑M的取值。本例中选取初始群体的规模为100.
2.2.2 变量个数L
变量个数与所用的编码方法有关。本文采用的实数数组的编码方案，变量个数等于数据库中相关字段的数量。根据分析，我们设定变量个数L为10。
2.2.3 变异概率P1
变异概率决定了物种的多样性。如果取值过大，有可能很多比较好的模式被破坏，使遗传算法的性能于随机搜索算法的性能类似；若取值过小，则变异操作产生新个体抑制遗传算法早熟现象的能力会较差。本例中， P1取为0.04。
2.2.4 交叉概率P2
交叉概率的选取一般为较大的值。可是如果过大，就会破坏群体中的优良模式。若取值过小，产生新个体的速度就会变慢。在本例中我们取值0.8。
2.2.5 终止代数 T
终止代数T是指表示遗传算法运行结束条件的一个参数，它表示算法要进行到满足指定进化代数后就停止，并将当前群体中产生的最佳个体作为最优结论进行输出。在本例中，我们所要得到的是一个满足给定阈值的规则集合，而并不是求最优解，所以终止代数是经过几代运算后，当没有小于给定阈值的规则产生时，系统运行就停止。
2.3 用遗传算法提取关联规则
算法如下：
Step1：初始化
（1） 随机产生一个初始种群P={A1，A2，…..An}；
（2） 输入用户给定的支持度S，可信度C，兴趣度I；
Step2：进行选择
（1） 计算目前种群P中的个体适应度：f（A）=S/S；
（2） 根据f（A）对个体进行筛选：若大于1，则保留个体进行产生下一代，否则删除个体，并计算出保留下的个体数M；
Step3：若M Step4：对交配池T和后代O进行初始化。
Step5：将当前种群中的所有个体都复制到交配池中；
Step6：随机从T中选择个体A’和A’’，按照概率Pc进行交叉；
Step7：在当前种群P中选择M个个体按照概率Pc进行变异；
Step8：判断是否终止条件；
Step9：利用置信度和兴趣度进行规则的提取。
3 发现的规则
根据以上的算法，我们在新生信息和调查信息数据库中发现部分有价值的关联规则如下：
规则1：学生生源地为县级及以下地区、普通高中毕业，并且分数中等的学生，非常注重学校的专业水平和就业水平对校园文化和学校环境感兴趣情况一般。
规则2：学生生源地为一级城市、职业高中，并且分数较低的同学，非常注重学生的环境和校园文化对专业水平比较重视对专升本情况感兴趣一般。
规则3：学生生普通高中毕业，分数较高，非常注重专升本情况及学校的专业水平对就业水平比较感兴趣，对校园文化感兴趣情况一般。
以上对好多规则进行了省略，总之，此挖掘算法在大专院校对外招生宣传侧重方向上起了很大的作用，挖掘出了学生生源地、毕业院校、成绩等级等因素与所关心学校的各种情况之间的潜在关联。
4 结束语
本文对遗传算法在关联规则提取方面的应用进行了初步的分析，还有许多问题需要进一步地去学习和探讨。文中所采用的掘算法主要考虑了两个称作支持度和可信度的阈值，但近来的研究表明： 在现实应用中只考虑这两个阈值是不够的，可能会产生错误的规则。在高校中，基本关联规则的挖掘算法还可以应用在学生心理分析、贫困生选取等其他方面， 都会具有很好的实用价值.
参考文献：
[1] 薛慧君.基于遗传算法的关联规则数据挖掘的应用研究[D].天津：天津大学，2006，06
[2] 许珂 刘希玉.基于遗传算法的关联规则挖掘方法及应用[J].重庆工学院学报，2007年，7：132-133
[3] 肖冬荣. 基于遗传算法的关联规则数据挖掘[J].通信技术，2010（1）：205-207
[4] 何小东 刘卫国，数据挖掘中关联规则挖掘算法比较研究[J]，计算机工程与设计，2005，5（5）：1265-1268.
关键词：遗传算法；数据挖掘；关联规则；招生宣传
中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2015）15-0181-02
Abstract： With the rise of data mining technology， various applied to association rule mining algorithms have gradually been concerned. In addition to the data in the database will be entry， query， statistics and other simple functional applications， but also to help users find the relevance of the presence of large amounts of data in a variety of useful information and data between， to help users analyze the valuable information， in order to achieve one of the commercial value. Association rules is an important research branch of data mining， which is the classical algorithm -Aprior algorithms are widely used， the limitations of this article for Aprior algorithm， genetic algorithm in association rule data mining for analysis and survey of a university freshmen the data， for example， to dig out the relevant contact the school environment， employment， campus community activities， canteen standards and other factors with students and student high school students to the situation between the level that can be focused on helping college admissions consulting and publicity for students in different regions to take a different form of publicity and promotional content， to further expand the enrollment of the school.
Key words： Genetic Algorithms；Data Mining；Association Rule；Admissions publicity
1 引言
1.1 数据挖掘
数据挖掘技术一般是指从海量数据中自动搜索隐藏于其中的有着特殊关联性的信息的过程。主要有数据准备、规律寻找和规律表示3个步骤。数据挖掘的任务有关联规则分析、分类分析、聚类分析、异常分析、特异群组分析以及演变分析等。其中的关联规则分析具有很多商业价值，被广泛的研究和应用。
1.2 关联规则
关联规则是数据库中存在的一类重要的可被发现的知识。如果两个或多个变量的取值之间存在某些规律性，就称为关联。关联分为简单关联、时序关联和因果关联。关联规则分析的目的是找出数据库中隐藏的关联性。人们有时并不知道数据库中数据的关联函数，因此关联分析生成的规则带有一定可信度。关联规则挖掘发现海量数据中属性之间有趣的关联或一定规律。
1.3 遗传算法
遗传算法是计算数学中用于解决最佳化的一种进化算法。进化算法最初是能过研究了进化生物学中的一些现象而发展起来的，这些现象包括了遗传、突变、自然选择以及杂交等。遗传算法一般用一种计算机模拟来实现。对于某个最优化问题，一定数量个体的抽象表示（称为染色体）的种群向更优的个体进化。
2 基于遗传算法的关联规则挖掘
2.1 学生入学调查数据进行遗传算法的编码方法
行遗传算法编码是应用遗传算法时要解决的主要问题，也是设计遗传算法的一个关键步骤。编码方法选择影响到交叉算子、变异算子等遗传算子的运算方法，在很大程度上决定了遗传进化的效率。时至今日人们已经提出了许多种不同的编码方法。本文采用实数数组的编码方案，因为其具备不仅简单、通用、鲁棒性强，适于并行分布处理等之外还方便了遗传算子的操作。在采用数组编码后的交叉、变异等操作实际上就成了对数组中数据进行操作，在本文中，我们把学生调查情况全部读入数据库，对一些属性进行合并，并适当对一些属性进行删除，重新建立了一个学生基本信息与学生调查信息数据库，如下表所示： 由于采用的是实数数组编码，其中一条规则就是一条实数编码串，又分为两个部分：规则的属性部分和规则类别，比如1131240=>122，所以我们要将属性值也用数值型来表示。例如如下几个表。
学生所在中学性质，分为两种情况，普通高中，职业高中，分别为其编码0，1。同时将分数等级等其它特征进行编码，在这里不一一列表。
结论属性表为分就业情况、校园环境、食堂消费水平、专业设置、校园文化五个表，表3为就业率注重情况表。
经过分析，编号和年龄属性与我们发现的关联知识没有关系，而性别属性也与我们发现的关联知识相关度不大，因此我们省略不用。
2.2 遗传算法的运行参数设定
遗传算法参数包括种群规模M、变量个数L、交叉概率Pc、变异概率Pm以及运算的终止进化代数T。参数的设定对算法的运行性能有着很大的影响，所以取值一定要认真。
2.2.1 种群规模M
种群规模M表示数据群体中所含调查个体的全部数量。其取值一定要适当，当数值太小时，遗传算法的运算速度提高了，但反映不出群体的多样式，也推理不出有价值的结论，造成遗传算法的早熟；而当M的取值太大时，遗传算法的运行效率会相应降低。所以，我们要综合这两个方面来考虑M的取值。本例中选取初始群体的规模为100.
2.2.2 变量个数L
变量个数与所用的编码方法有关。本文采用的实数数组的编码方案，变量个数等于数据库中相关字段的数量。根据分析，我们设定变量个数L为10。
2.2.3 变异概率P1
变异概率决定了物种的多样性。如果取值过大，有可能很多比较好的模式被破坏，使遗传算法的性能于随机搜索算法的性能类似；若取值过小，则变异操作产生新个体抑制遗传算法早熟现象的能力会较差。本例中， P1取为0.04。
2.2.4 交叉概率P2
交叉概率的选取一般为较大的值。可是如果过大，就会破坏群体中的优良模式。若取值过小，产生新个体的速度就会变慢。在本例中我们取值0.8。
2.2.5 终止代数 T
终止代数T是指表示遗传算法运行结束条件的一个参数，它表示算法要进行到满足指定进化代数后就停止，并将当前群体中产生的最佳个体作为最优结论进行输出。在本例中，我们所要得到的是一个满足给定阈值的规则集合，而并不是求最优解，所以终止代数是经过几代运算后，当没有小于给定阈值的规则产生时，系统运行就停止。
2.3 用遗传算法提取关联规则
算法如下：
Step1：初始化
（1） 随机产生一个初始种群P={A1，A2，…..An}；
（2） 输入用户给定的支持度S，可信度C，兴趣度I；
Step2：进行选择
（1） 计算目前种群P中的个体适应度：f（A）=S/S；
（2） 根据f（A）对个体进行筛选：若大于1，则保留个体进行产生下一代，否则删除个体，并计算出保留下的个体数M；
Step3：若M
Step5：将当前种群中的所有个体都复制到交配池中；
Step6：随机从T中选择个体A’和A’’，按照概率Pc进行交叉；
Step7：在当前种群P中选择M个个体按照概率Pc进行变异；
Step8：判断是否终止条件；
Step9：利用置信度和兴趣度进行规则的提取。
3 发现的规则
根据以上的算法，我们在新生信息和调查信息数据库中发现部分有价值的关联规则如下：
规则1：学生生源地为县级及以下地区、普通高中毕业，并且分数中等的学生，非常注重学校的专业水平和就业水平对校园文化和学校环境感兴趣情况一般。
规则2：学生生源地为一级城市、职业高中，并且分数较低的同学，非常注重学生的环境和校园文化对专业水平比较重视对专升本情况感兴趣一般。
规则3：学生生普通高中毕业，分数较高，非常注重专升本情况及学校的专业水平对就业水平比较感兴趣，对校园文化感兴趣情况一般。
以上对好多规则进行了省略，总之，此挖掘算法在大专院校对外招生宣传侧重方向上起了很大的作用，挖掘出了学生生源地、毕业院校、成绩等级等因素与所关心学校的各种情况之间的潜在关联。
4 结束语
本文对遗传算法在关联规则提取方面的应用进行了初步的分析，还有许多问题需要进一步地去学习和探讨。文中所采用的掘算法主要考虑了两个称作支持度和可信度的阈值，但近来的研究表明： 在现实应用中只考虑这两个阈值是不够的，可能会产生错误的规则。在高校中，基本关联规则的挖掘算法还可以应用在学生心理分析、贫困生选取等其他方面， 都会具有很好的实用价值.
参考文献：
[1] 薛慧君.基于遗传算法的关联规则数据挖掘的应用研究[D].天津：天津大学，2006，06
[2] 许珂 刘希玉.基于遗传算法的关联规则挖掘方法及应用[J].重庆工学院学报，2007年，7：132-133
[3] 肖冬荣. 基于遗传算法的关联规则数据挖掘[J].通信技术，2010（1）：205-207
[4] 何小东 刘卫国，数据挖掘中关联规则挖掘算法比较研究[J]，计算机工程与设计，2005，5（5）：1265-1268.