黎 華

(西昌學(xué)院電子工程系，中國(guó)四川 615000)

數(shù)據(jù)挖掘(data mining)是當(dāng)前數(shù)據(jù)庫(kù)研究領(lǐng)域一個(gè)的重要方向.數(shù)據(jù)挖掘主要是指利用各種分析方法和技術(shù)，對(duì)以往累積的大量復(fù)雜的數(shù)據(jù)進(jìn)行分析、歸納和整合，從而在大量數(shù)據(jù)中發(fā)掘出有用的信息，為相應(yīng)的決策提供依據(jù).

所以借助數(shù)據(jù)挖掘技術(shù)，企業(yè)完全有能力從浩瀚的數(shù)據(jù)海洋中，挖掘出全面而又有價(jià)值的信息和知識(shí)，并作為決策支持之用，進(jìn)而形成企業(yè)獨(dú)有的競(jìng)爭(zhēng)優(yōu)勢(shì).

1 CRISP-DM模型

CRISP-DM模型是由歐盟幾家在數(shù)據(jù)挖掘應(yīng)用上有豐富經(jīng)驗(yàn)的公司共同籌劃提出來(lái)的，CRISP-DM模型主要強(qiáng)調(diào)完整的數(shù)據(jù)挖掘過(guò)程，不是只針對(duì)數(shù)據(jù)整理、數(shù)據(jù)顯示、數(shù)據(jù)分析和模型的構(gòu)建，而是將對(duì)企業(yè)的需求問(wèn)題的理解和后期對(duì)模型的評(píng)價(jià)和模型的延伸應(yīng)用都應(yīng)用于數(shù)據(jù)挖掘中［1-2］.

圖1 CRISP-DM模型Fig.1 CRISP-DM model

因此，CRISP-DM模型強(qiáng)調(diào)實(shí)施數(shù)據(jù)挖掘項(xiàng)目的方法和步驟，同時(shí)該模型獨(dú)立于每種具體數(shù)據(jù)挖掘算法和數(shù)據(jù)挖掘系統(tǒng)之外.

2 蜂群算法

2.1 基本原理

自然界中，蜂群實(shí)現(xiàn)采蜜的集體智能行為主要包括3個(gè)主要部分，分別為蜜源、采蜜蜂EF、待工蜂UF.另外，在此基礎(chǔ)上又引入3種行為模式，分別為搜索蜜源、為蜜源招募以及放棄蜜源［3-4］.

蜂群采蜜的流程圖如圖2所示.

假設(shè)目前有2個(gè)已經(jīng)被發(fā)現(xiàn)的食物源A和B，起初，待工蜂沒(méi)有獲得任何食物源的信息，那么它有兩個(gè)可能的選擇:

(1)待工蜂作為偵察蜂，由于外在因素或激勵(lì)因素的存在，其會(huì)自動(dòng)搜尋蜂巢附近的食物源(圖中‘S’線).

(2)當(dāng)待工蜂發(fā)現(xiàn)其他蜜蜂之后，其被招募，按照自身獲取的信息搜尋食物源(圖中‘R’線).

當(dāng)待工蜂找到新的食物源的時(shí)候，蜜蜂可以記住并獲取食物源所在的位置，與此同時(shí)實(shí)現(xiàn)采蜜工作.

因此，這時(shí)待工蜂成為采蜜蜂，等到蜜蜂采蜜回到蜂箱，此時(shí)將采到的蜜吐到空的蜂房之后，其有下面幾個(gè)選擇:

a)拋棄食物源，變成待工蜂的跟隨蜂;

b)返回同一食物源之前，通過(guò)跳搖擺舞實(shí)現(xiàn)蜂群的招募;

c)繼續(xù)采蜜，不招募其他蜂群.

初始時(shí)，所有蜜蜂都是偵察蜂，等到它們隨機(jī)搜索到食物源后，偵察蜂重新回到蜂巢的舞蹈區(qū).依據(jù)食物源的收益度的大小，偵察蜂可以變成任何一種蜜蜂.

圖2 蜜蜂采蜜工作圖Fig.2 Working drawing of honey bees

圖3 蜂群算法流程圖Fig.3 Flowchart of bee colony algorithm

2.2 要素組成

依據(jù)蜂群算法的原理介紹，蜂群算法主要有以下3個(gè)基本要素構(gòu)成:

(1)食物源.食物源表示各種可能的解;食物源值由多種因素決定的，比如食物源和蜂巢的距離、能量的大小和集中程度等.

(2)采蜜蜂EF.采蜜蜂是和食物源有聯(lián)系的，采蜜蜂擁有采集到的具體的食物源信息，信息主要有食物源和蜂巢的距離、食物源方向以及食物源的收益度;

(3)待工蜂UF.待采蜜蜂尋找食物源，主要分為偵察蜂和跟隨蜂;偵察蜂負(fù)責(zé)找尋蜂巢附近的新食物源;而跟隨蜂在蜂巢內(nèi)等待，通過(guò)分享到的采蜜蜂的信息，實(shí)現(xiàn)食物源的尋找［4］.

算法流程如圖3所示.

3 基于蜂群算法的數(shù)據(jù)庫(kù)知識(shí)發(fā)現(xiàn)模型

參考CRISP-DM模型和數(shù)據(jù)庫(kù)知識(shí)發(fā)現(xiàn)的多處理階段模型［5］，本文提出將信任分配學(xué)習(xí)機(jī)制和基于蜂群算法的規(guī)則發(fā)現(xiàn)機(jī)制有機(jī)地結(jié)合在一起的基于蜂群算法的數(shù)據(jù)庫(kù)知識(shí)發(fā)現(xiàn)系統(tǒng)模型，其特點(diǎn)是系統(tǒng)采用概率轉(zhuǎn)換規(guī)則，使用并行的規(guī)則觸發(fā)機(jī)制，是一種自適應(yīng)的學(xué)習(xí)系統(tǒng).

基于蜂群算法的數(shù)據(jù)庫(kù)知識(shí)發(fā)現(xiàn)模型基本結(jié)構(gòu)如圖4所示.

圖4 基于蜂群算法的數(shù)據(jù)庫(kù)發(fā)現(xiàn)模型Fig.4 Model of database discovery based on bee colony algorithm

客觀數(shù)據(jù)庫(kù)環(huán)境信息通過(guò)數(shù)據(jù)處理器將完整的數(shù)據(jù)信息發(fā)往模式生成器，模式生成器根據(jù)指定的數(shù)據(jù)挖掘任務(wù)，從數(shù)據(jù)信息中提取相關(guān)的模式并將這些模式劃分為訓(xùn)練數(shù)據(jù)集以及測(cè)試數(shù)據(jù)集［6］.被觸發(fā)的知識(shí)生成器通過(guò)設(shè)計(jì)的蜂群算法與訓(xùn)練集交互的學(xué)習(xí)，將滿意的學(xué)習(xí)結(jié)果提供給測(cè)試集，測(cè)試集將評(píng)測(cè)結(jié)果交給解釋評(píng)價(jià)價(jià)機(jī)構(gòu)，通過(guò)解釋/評(píng)價(jià)機(jī)構(gòu)將知識(shí)提交給用戶并作用于數(shù)據(jù)庫(kù)環(huán)境，同時(shí)更具評(píng)測(cè)結(jié)果和用戶需求，修改信任分配算法，以希望下次能得到更好的結(jié)果［7］.

4 仿真實(shí)驗(yàn)

數(shù)據(jù)挖掘算法的任務(wù)是對(duì)海量數(shù)據(jù)庫(kù)進(jìn)行挖掘，對(duì)于只有如此少的記錄數(shù)據(jù)庫(kù)的效果不能說(shuō)明問(wèn)題.作者又選擇了機(jī)器學(xué)習(xí)研究通常使用的Cleve心臟病例比較實(shí)驗(yàn)數(shù)據(jù)庫(kù)進(jìn)較實(shí)驗(yàn).訓(xùn)練數(shù)據(jù)為200個(gè)，測(cè)試數(shù)據(jù)為103個(gè).

4.1 Cleve原始數(shù)據(jù)的處理

(1)C leve原始數(shù)據(jù)含有部分?jǐn)?shù)據(jù)屬性值的缺失，首先補(bǔ)足缺失數(shù)據(jù).

(2)對(duì)于 Age，Trestbps，Cholesterol，F(xiàn)asting blood sugar，Max heart rate，Old peak 和 Number of vessels colored的連續(xù)屬性進(jìn)行離散化為:

Age:＞47.5;＜47.5 兩類

Trestbps，Cholestrol對(duì)其劃分的邊界計(jì)算信息嫡，其信息消值都不足以對(duì)分類進(jìn)行有效劃分，因此這兩個(gè)屬性對(duì)分類的劃分不起任何作用，因而從屬性列表中刪去.

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個(gè))，無(wú)需對(duì)其縮減.

圖5 測(cè)試結(jié)果對(duì)比Fig.5 Comparsion chart of test results

4.2 實(shí)驗(yàn)結(jié)果

為了進(jìn)一步驗(yàn)證蜂群算法進(jìn)行數(shù)據(jù)庫(kù)知識(shí)發(fā)現(xiàn)的優(yōu)越性和準(zhǔn)確性，將其同文獻(xiàn)［8］算法進(jìn)行對(duì)比，主要從訓(xùn)練準(zhǔn)確率、測(cè)試準(zhǔn)確率和運(yùn)行時(shí)間3個(gè)方面進(jìn)行驗(yàn)證，運(yùn)用仿真進(jìn)行仿真，仿真結(jié)果分別如圖5～圖7.

從圖5中可以看出，蜂群算法的準(zhǔn)確率達(dá)到100%，而文獻(xiàn)中的算法的準(zhǔn)確率只達(dá)到93.333 3%.從圖6中可以看出，蜂群算法的準(zhǔn)確率普遍高于文獻(xiàn)算法的準(zhǔn)確率.從圖7中可以看出，蜂群算法的運(yùn)行時(shí)間也優(yōu)于文獻(xiàn)算法.

通過(guò)算例的測(cè)試，發(fā)現(xiàn)蜂群算法有很好的尋優(yōu)能力，求解速度也快.下面重點(diǎn)研究蜂群算法的不用參數(shù)對(duì)尋優(yōu)結(jié)果的影響.

圖6 測(cè)試結(jié)果正確率對(duì)比圖Fig.6 Comparison chart of correct rate of testing result

圖7 算法時(shí)間對(duì)比圖Fig.7 Comparison chart of algorithm time

5 不同種群大小對(duì)蜂群算法性能的影響

5.1 不同種群大小對(duì)收斂性的影響

分別分析種群數(shù)為15，30，45時(shí)，種群大小對(duì)蜂群算法性能的影響.

通過(guò)圖8(a)、(b)、(c)3圖的對(duì)比，發(fā)現(xiàn)種群越大，蜂群算法收斂性越快，更容易逼近最優(yōu)值.

5.2 不同迭代次數(shù)對(duì)蜂群算法性能的影響

分析迭代次數(shù)為100，200，300時(shí)，迭代次數(shù)對(duì)GA算法性能的影響.

通過(guò)圖9(a)、(b)、(c)3圖的對(duì)比發(fā)現(xiàn)，隨著迭代次數(shù)的增加，蜂群算法求解問(wèn)題的收斂性不斷增加，能更快地逼近最優(yōu)值.

圖8 蜂群大小對(duì)收斂結(jié)果的影響Fig.8 Colony size effects on convergence results

圖9 不同迭代次數(shù)對(duì)結(jié)果的影響Fig.9 Different iterations effects on results

6 結(jié)論

在CRTSP-DM模型的基礎(chǔ)上，本文提出一種基于蜂群算法的知識(shí)庫(kù)發(fā)現(xiàn)系統(tǒng)模型，將蜂群算法同CRTSP-DM模型有機(jī)地結(jié)合起來(lái)，運(yùn)用Matlab軟件，進(jìn)行仿真實(shí)驗(yàn)，并同文獻(xiàn)中的算法進(jìn)行了對(duì)比，主要研究結(jié)果如下:(1)根據(jù)仿真結(jié)果，蜂群算法的準(zhǔn)確率達(dá)到98.1%，效果很好.(2)同文獻(xiàn)中的算法進(jìn)行對(duì)比，主要從訓(xùn)練準(zhǔn)確率、測(cè)試準(zhǔn)確率和運(yùn)行時(shí)間3個(gè)方面進(jìn)行驗(yàn)證.從圖5中可以看出，蜂群算法的準(zhǔn)確率達(dá)到100%，而文獻(xiàn)中的算法的準(zhǔn)確率只達(dá)到93.333 3%.從圖6中可以看出，蜂群算法的準(zhǔn)確率普遍高于文獻(xiàn)算法的準(zhǔn)確率.由圖7可見(jiàn)，蜂群算法的運(yùn)行時(shí)間也優(yōu)于文獻(xiàn)算法.

最后，調(diào)整蜂群算法的不同參數(shù)，對(duì)比了不同參數(shù)對(duì)蜂群算法知識(shí)庫(kù)發(fā)現(xiàn)系統(tǒng)尋優(yōu)結(jié)果的影響.

［1］王興偉，鄒榮珠，黃 敏.一種基于蜂群算法的ABC支持型QoS組播路由機(jī)制［J］.計(jì)算機(jī)科學(xué)，2009(6):47-52.

［2］袁 浩.基于改進(jìn)蜂群算法無(wú)線傳感器感知節(jié)點(diǎn)部署優(yōu)化［J］.計(jì)算機(jī)應(yīng)用研究，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］.計(jì)算機(jī)工程與應(yīng)用，2009，45(1):53-55.

［5］暴 勵(lì)，曾建潮.一種雙種群差分蜂群算法［J］.控制理論與應(yīng)用，2011，28(2):267-272.

［6］胡中華，趙 敏.基于人工蜂群算法的機(jī)器人路徑規(guī)劃［J］.電焊機(jī)，2009，26(1):93-96.

［7］康 飛，李俊杰，許 青.改進(jìn)人工蜂群算法及其在反演分析中的應(yīng)用［J］.水電能源科學(xué)，2009，27(1):126-129.

［8］暴 勵(lì)，曾建潮.自適應(yīng)搜索空間的混沌蜂群算法［J］.計(jì)算機(jī)應(yīng)用研究，2010，26(4):1331-1334.