一种基于蜂群算法的数据库知识发现过程的研究
2014-10-11黎华
黎 华
(西昌学院电子工程系，中国四川 615000)
数据挖掘(data mining)是当前数据库研究领域一个的重要方向.数据挖掘主要是指利用各种分析方法和技术，对以往累积的大量复杂的数据进行分析、归纳和整合，从而在大量数据中发掘出有用的信息，为相应的决策提供依据.
所以借助数据挖掘技术，企业完全有能力从浩瀚的数据海洋中，挖掘出全面而又有价值的信息和知识，并作为决策支持之用，进而形成企业独有的竞争优势.
1 CRISP-DM模型
CRISP-DM模型是由欧盟几家在数据挖掘应用上有丰富经验的公司共同筹划提出来的，CRISP-DM模型主要强调完整的数据挖掘过程，不是只针对数据整理、数据显示、数据分析和模型的构建，而是将对企业的需求问题的理解和后期对模型的评价和模型的延伸应用都应用于数据挖掘中［1-2］.
图1 CRISP-DM模型Fig.1 CRISP-DM model
因此，CRISP-DM模型强调实施数据挖掘项目的方法和步骤，同时该模型独立于每种具体数据挖掘算法和数据挖掘系统之外.
2 蜂群算法
2.1 基本原理
自然界中，蜂群实现采蜜的集体智能行为主要包括3个主要部分，分别为蜜源、采蜜蜂EF、待工蜂UF.另外，在此基础上又引入3种行为模式，分别为搜索蜜源、为蜜源招募以及放弃蜜源［3-4］.
蜂群采蜜的流程图如图2所示.
假设目前有2个已经被发现的食物源A和B，起初，待工蜂没有获得任何食物源的信息，那么它有两个可能的选择:
(1)待工蜂作为侦察蜂，由于外在因素或激励因素的存在，其会自动搜寻蜂巢附近的食物源(图中‘S’线).
(2)当待工蜂发现其他蜜蜂之后，其被招募，按照自身获取的信息搜寻食物源(图中‘R’线).
当待工蜂找到新的食物源的时候，蜜蜂可以记住并获取食物源所在的位置，与此同时实现采蜜工作.
因此，这时待工蜂成为采蜜蜂，等到蜜蜂采蜜回到蜂箱，此时将采到的蜜吐到空的蜂房之后，其有下面几个选择:
a)抛弃食物源，变成待工蜂的跟随蜂;
b)返回同一食物源之前，通过跳摇摆舞实现蜂群的招募;
c)继续采蜜，不招募其他蜂群.
初始时，所有蜜蜂都是侦察蜂，等到它们随机搜索到食物源后，侦察蜂重新回到蜂巢的舞蹈区.依据食物源的收益度的大小，侦察蜂可以变成任何一种蜜蜂.
图2 蜜蜂采蜜工作图Fig.2 Working drawing of honey bees
图3 蜂群算法流程图Fig.3 Flowchart of bee colony algorithm
2.2 要素组成
依据蜂群算法的原理介绍，蜂群算法主要有以下3个基本要素构成:
(1)食物源.食物源表示各种可能的解;食物源值由多种因素决定的，比如食物源和蜂巢的距离、能量的大小和集中程度等.
(2)采蜜蜂EF.采蜜蜂是和食物源有联系的，采蜜蜂拥有采集到的具体的食物源信息，信息主要有食物源和蜂巢的距离、食物源方向以及食物源的收益度;
(3)待工蜂UF.待采蜜蜂寻找食物源，主要分为侦察蜂和跟随蜂;侦察蜂负责找寻蜂巢附近的新食物源;而跟随蜂在蜂巢内等待，通过分享到的采蜜蜂的信息，实现食物源的寻找［4］.
算法流程如图3所示.
3 基于蜂群算法的数据库知识发现模型
参考CRISP-DM模型和数据库知识发现的多处理阶段模型［5］，本文提出将信任分配学习机制和基于蜂群算法的规则发现机制有机地结合在一起的基于蜂群算法的数据库知识发现系统模型，其特点是系统采用概率转换规则，使用并行的规则触发机制，是一种自适应的学习系统.
基于蜂群算法的数据库知识发现模型基本结构如图4所示.
图4 基于蜂群算法的数据库发现模型Fig.4 Model of database discovery based on bee colony algorithm
客观数据库环境信息通过数据处理器将完整的数据信息发往模式生成器，模式生成器根据指定的数据挖掘任务，从数据信息中提取相关的模式并将这些模式划分为训练数据集以及测试数据集［6］.被触发的知识生成器通过设计的蜂群算法与训练集交互的学习，将满意的学习结果提供给测试集，测试集将评测结果交给解释评价价机构，通过解释/评价机构将知识提交给用户并作用于数据库环境，同时更具评测结果和用户需求，修改信任分配算法，以希望下次能得到更好的结果［7］.
4 仿真实验
数据挖掘算法的任务是对海量数据库进行挖掘，对于只有如此少的记录数据库的效果不能说明问题.作者又选择了机器学习研究通常使用的Cleve心脏病例比较实验数据库进较实验.训练数据为200个，测试数据为103个.
4.1 Cleve原始数据的处理
(1)C leve原始数据含有部分数据属性值的缺失，首先补足缺失数据.
(2)对于 Age，Trestbps，Cholesterol，Fasting blood sugar，Max heart rate，Old peak 和 Number of vessels colored的连续属性进行离散化为:
Age:＞47.5;＜47.5 两类
Trestbps，Cholestrol对其划分的边界计算信息嫡，其信息消值都不足以对分类进行有效划分，因此这两个属性对分类的划分不起任何作用，因而从属性列表中删去.
Fasting blood sugar:＞120;＜120两类;
Max heart rate:＞ 147.5;＜ 147.5 两类;
Old peak:＞ 1.7;＜ 1.7 两类 ;
Number of vessels colored:＞ 0.5;＜ 0.5两类:
由于离散属性的属性值均较少(2～4个)，无需对其缩减.
图5 测试结果对比Fig.5 Comparsion chart of test results
4.2 实验结果
为了进一步验证蜂群算法进行数据库知识发现的优越性和准确性，将其同文献［8］算法进行对比，主要从训练准确率、测试准确率和运行时间3个方面进行验证，运用仿真进行仿真，仿真结果分别如图5～图7.
从图5中可以看出，蜂群算法的准确率达到100%，而文献中的算法的准确率只达到93.333 3%.从图6中可以看出，蜂群算法的准确率普遍高于文献算法的准确率.从图7中可以看出，蜂群算法的运行时间也优于文献算法.
通过算例的测试，发现蜂群算法有很好的寻优能力，求解速度也快.下面重点研究蜂群算法的不用参数对寻优结果的影响.
图6 测试结果正确率对比图Fig.6 Comparison chart of correct rate of testing result
图7 算法时间对比图Fig.7 Comparison chart of algorithm time
5 不同种群大小对蜂群算法性能的影响
5.1 不同种群大小对收敛性的影响
分别分析种群数为15，30，45时，种群大小对蜂群算法性能的影响.
通过图8(a)、(b)、(c)3图的对比，发现种群越大，蜂群算法收敛性越快，更容易逼近最优值.
5.2 不同迭代次数对蜂群算法性能的影响
分析迭代次数为100，200，300时，迭代次数对GA算法性能的影响.
通过图9(a)、(b)、(c)3图的对比发现，随着迭代次数的增加，蜂群算法求解问题的收敛性不断增加，能更快地逼近最优值.
图8 蜂群大小对收敛结果的影响Fig.8 Colony size effects on convergence results
图9 不同迭代次数对结果的影响Fig.9 Different iterations effects on results
6 结论
在CRTSP-DM模型的基础上，本文提出一种基于蜂群算法的知识库发现系统模型，将蜂群算法同CRTSP-DM模型有机地结合起来，运用Matlab软件，进行仿真实验，并同文献中的算法进行了对比，主要研究结果如下:(1)根据仿真结果，蜂群算法的准确率达到98.1%，效果很好.(2)同文献中的算法进行对比，主要从训练准确率、测试准确率和运行时间3个方面进行验证.从图5中可以看出，蜂群算法的准确率达到100%，而文献中的算法的准确率只达到93.333 3%.从图6中可以看出，蜂群算法的准确率普遍高于文献算法的准确率.由图7可见，蜂群算法的运行时间也优于文献算法.
最后，调整蜂群算法的不同参数，对比了不同参数对蜂群算法知识库发现系统寻优结果的影响.
［1］王兴伟，邹荣珠，黄 敏.一种基于蜂群算法的ABC支持型QoS组播路由机制［J］.计算机科学，2009(6):47-52.
［2］袁 浩.基于改进蜂群算法无线传感器感知节点部署优化［J］.计算机应用研究，2010，26(7):2704-2708.
［3］KARABOGA D，OKDEM S，OZTURK C.Cluster based wireless sensor network routings using artificial bee colony algorithm［J］.J Wireless Networks，2012，18(7):847-860.
［4］丁海军，冯庆娴.基于boltzmann选择策略的人工蜂群算法［J］.计算机工程与应用，2009，45(1):53-55.
［5］暴 励，曾建潮.一种双种群差分蜂群算法［J］.控制理论与应用，2011，28(2):267-272.
［6］胡中华，赵 敏.基于人工蜂群算法的机器人路径规划［J］.电焊机，2009，26(1):93-96.
［7］康 飞，李俊杰，许 青.改进人工蜂群算法及其在反演分析中的应用［J］.水电能源科学，2009，27(1):126-129.
［8］暴 励，曾建潮.自适应搜索空间的混沌蜂群算法［J］.计算机应用研究，2010，26(4):1331-1334.
