中国韩国日本在线观看免费,A级尤物一区,日韩精品一二三区无码,欧美日韩少妇色

基于GP算法的知識(shí)發(fā)現(xiàn)系統(tǒng)

發(fā)布時(shí)間:2014-07-29 21:04
在數(shù)據(jù)庫(kù)中發(fā)現(xiàn)有用的知識(shí)是數(shù)據(jù)挖掘(Data Mining, DM)的主要任務(wù),在一定的情況下,所有的數(shù)據(jù)庫(kù)查詢可以認(rèn)為是完成這項(xiàng)任務(wù)。我們現(xiàn)在有一套分析和探索數(shù)據(jù)的工具:SQL查詢、OLAP和數(shù)據(jù)挖掘技術(shù)。SQL查詢由關(guān)系代數(shù)所構(gòu)成;OLAP提供了建立在多維數(shù)據(jù)模型基礎(chǔ)上的高水平查詢;而數(shù)據(jù)挖掘提供了最抽象的數(shù)據(jù)分析操作。我們可以認(rèn)為不同的數(shù)據(jù)挖掘任務(wù)是在高水平上的復(fù)雜查詢。數(shù)據(jù)挖掘是機(jī)器學(xué)習(xí)和數(shù)據(jù)庫(kù)技術(shù)的交叉學(xué)科,DM系統(tǒng)的主要特點(diǎn)是:在數(shù)據(jù)庫(kù)中發(fā)現(xiàn)能夠用某些規(guī)則表述的、隱含的知識(shí);與數(shù)據(jù)庫(kù)是緊密集成的;高度自動(dòng)化的;對(duì)知識(shí)發(fā)現(xiàn)的處理是有效率的(尤其對(duì)大型數(shù)據(jù)庫(kù))。

這里我們給出一種基于GP(Genetic Programming,遺傳編程)算法的知識(shí)發(fā)現(xiàn)系統(tǒng),和通常對(duì)數(shù)據(jù)庫(kù)的查詢不同的是,這個(gè)系統(tǒng)可對(duì)特定的對(duì)象集產(chǎn)生特定的查詢集,系統(tǒng)自動(dòng)根據(jù)查詢集訪問(wèn)數(shù)據(jù)庫(kù),從而發(fā)掘出數(shù)據(jù)庫(kù)中隱含的知識(shí)。本文將對(duì)上述知識(shí)發(fā)掘過(guò)程進(jìn)行詳細(xì)描述,并提出了一種用遺傳編程(GP)來(lái)進(jìn)行數(shù)據(jù)挖掘的方法,GP個(gè)體由數(shù)據(jù)庫(kù)查詢組成,而這些查詢代表了高水平上的規(guī)則。

1 系統(tǒng)基本結(jié)構(gòu)
我們?cè)赱1]文給出的知識(shí)發(fā)現(xiàn)系統(tǒng)結(jié)構(gòu)基礎(chǔ)上加以改進(jìn),給出如圖1的基于GP算法的知識(shí)發(fā)現(xiàn)系統(tǒng)。

1.1 系統(tǒng)結(jié)構(gòu)描述
整個(gè)系統(tǒng)由GP引擎、OODBMS(Object-Oriented Database Management System,面向?qū)ο髷?shù)據(jù)庫(kù)管理系統(tǒng))、知識(shí)庫(kù)、DB接口和用戶接口組成。系統(tǒng)以一組對(duì)象、領(lǐng)域知識(shí)和模式信息作為輸入。根據(jù)所給輸入,GP引擎將產(chǎn)生許多隨機(jī)的查詢,系統(tǒng)將這些查詢應(yīng)用于OODBMS,OODBMS將返回其結(jié)果。系統(tǒng)用給定的輸入對(duì)該返回結(jié)果進(jìn)行評(píng)價(jià),評(píng)價(jià)是計(jì)算個(gè)體查詢的適應(yīng)值的過(guò)程。那些能夠匹配所給對(duì)象集的查詢或查詢集將被選中,在沒有查詢能夠匹配所給對(duì)象集時(shí),那么其最好的查詢將被選中。最后,將能夠最好地描述所給對(duì)象集特性的查詢作為輸出。

1.2 面向?qū)ο蟮臄?shù)據(jù)庫(kù)
這里,我們假定一個(gè)基于面向?qū)ο蠛秃瘮?shù)的數(shù)據(jù)庫(kù)模型(Object-Oriented and Functional Data Model, OOFDM),OOFDM具有面向?qū)ο蠛秃瘮?shù)數(shù)據(jù)模式的特性。這種模型要比傳統(tǒng)的關(guān)系數(shù)據(jù)庫(kù)模型在表達(dá)知識(shí)時(shí)更加逼近和容易。OOFDM的基本概念是"將感知到的真實(shí)世界作為相互關(guān)系對(duì)象的變量,并從不同的更細(xì)的層次上觀察這些對(duì)象。"[2]函數(shù)數(shù)據(jù)模型可以簡(jiǎn)單地借助函數(shù)的數(shù)學(xué)符號(hào)來(lái)表示數(shù)據(jù)間的關(guān)系。每個(gè)類(或?qū)嶓w集)有自己的屬性和值,類與屬性間的關(guān)系是將類中的對(duì)象集映射到屬性域的一個(gè)函數(shù)。關(guān)系或逆關(guān)系組成了類間的連接。

1.3 查詢算子
我們使用下列查詢算子作為其面向?qū)ο髷?shù)據(jù)庫(kù)的查詢語(yǔ)言。
①SEL C-1 [(謂詞)] 該算子選擇所有屬于C-1且滿足謂詞的對(duì)象。C-1既可以是一個(gè)類名也可以是一個(gè)屬于C-1的查詢。謂詞是一個(gè)可選項(xiàng)。如果在這個(gè)算子里沒有謂詞,它將選擇該類中的所有對(duì)象。
②RES C-1 謂詞 該算子根據(jù)所給謂詞,限制給定集合的對(duì)象與另一個(gè)類的對(duì)象關(guān)聯(lián)。C-1和謂詞同SEL算子,但對(duì)于RES的謂詞屬性必須是關(guān)系型的屬性,而對(duì)于SEL算子謂詞屬性則必須是非關(guān)系型屬性。
③REL C-1 R-r Class-2 該算子選擇所有C-1中與C-2中對(duì)象有關(guān)聯(lián)的對(duì)象。這是一個(gè)通過(guò)R-r 將一個(gè)類C-1與另一個(gè)類C-2關(guān)聯(lián)起來(lái)的關(guān)系算子。R-r可以是一個(gè)通過(guò)C-1中定義的關(guān)系集中的關(guān)系屬性之一。C-1既可以是一個(gè)類名也可以是一個(gè)屬于C-1的查詢。C-2必須是一個(gè)類名或是一個(gè)屬于C-2的查詢,并且通過(guò)R-r關(guān)聯(lián)到另一個(gè)類C-1。
④G-REL C-1 R-r C-2 該算子是REL的逆算子,它選擇所有C-2中與C-1中對(duì)象有關(guān)聯(lián)的對(duì)象。C-1、C-2以及R-r的意義同REL算子。

2 GP算法
遺傳編程(GP)屬于進(jìn)化計(jì)算(Evolutionary Computation,EC)模型的一種。EC是一種借鑒自然界進(jìn)化機(jī)制而產(chǎn)生的并行隨機(jī)搜索算法。進(jìn)化算法的基本原理是選擇和改變,它區(qū)別于其他搜索方法有兩個(gè)顯著特征:首先這些算法都是基于種群(population)的;其次在種群中個(gè)體(indvidual)之間存在競(jìng)爭(zhēng)。
為搜索特定的(感興趣的)查詢需要一種工具,這種工具可智能生成一組查詢并以它們是否能導(dǎo)出與用戶給定的同樣的對(duì)象集來(lái)進(jìn)行評(píng)價(jià)。GP算法對(duì)這一類問(wèn)題是很實(shí)用的。

2.1 函數(shù)集與端點(diǎn)集
一般GP中可生成的程序集是使用者定義的函數(shù)集和端點(diǎn)集。表1給出了相應(yīng)的函數(shù)集和端點(diǎn)集,其中函數(shù)集由1.3中定義的查詢算子、邏輯運(yùn)算算子以及比較算子所組成。

函數(shù)集 {SEL,REL,G-REL,RES},{UNI,INT,DIF},{AND,OR,NOT}, {>,>=,筆耕文化傳播,=,<,<=} 端點(diǎn)集類集,屬性集,值集
表1 函數(shù)集和端點(diǎn)集

在我們的應(yīng)用中還有一些具有不同句法的查詢算子。每個(gè)算子具有不同的句法且假定的數(shù)據(jù)庫(kù)是面向?qū)ο蟮摹R虼,它具有為?chuàng)建個(gè)體而使用的特別的函數(shù)集(或算子集)和端點(diǎn)集。從而,構(gòu)成種群的所有個(gè)體的創(chuàng)建必然受到每個(gè)算子的約束[3]。約束可以是算子的句法和查詢的類型,或者是為創(chuàng)建查詢選擇適當(dāng)屬性值的領(lǐng)域知識(shí)。比較算子和邏輯算子只使用于查詢的謂詞。當(dāng)比較符號(hào)操作數(shù)時(shí),僅使用'='。
端點(diǎn)集由CLASS-SET、SLOT-SET和VALUE-SET組成。CLASS-SET由1.2中定義的類名組成,SLOT-SET由每個(gè)類的所有屬性構(gòu)成,VALUE-SET由數(shù)值和符號(hào)值所構(gòu)成(它們均為屬性值)。數(shù)值由整型或?qū)嵭蛿?shù)構(gòu)成,其數(shù)值范圍由所用數(shù)據(jù)庫(kù)模式定義。符號(hào)值由字符串表示的符號(hào)屬性值構(gòu)成。

2.2 創(chuàng)建初始種群
為了創(chuàng)建一個(gè)個(gè)體(查詢),首先必須確定特定查詢所返回的對(duì)象類型。結(jié)果類型被選擇后,從所選類型返回例子的算子集中隨機(jī)地選擇一個(gè)算子,這個(gè)過(guò)程對(duì)查詢的每個(gè)參數(shù)遞歸地進(jìn)行。最初,那些句法正確的預(yù)定義數(shù)量的查詢被隨機(jī)地產(chǎn)生,形成初始種群。

2.3 選擇屬性值
由于可選擇范圍大,要從某個(gè)查詢的值集中選擇一個(gè)屬性值(數(shù)值或符號(hào)常數(shù))是相當(dāng)困難的。對(duì)于一個(gè)范圍為[1,10000]的整數(shù)集,隨機(jī)選到一個(gè)特定整數(shù)的概率僅為1/10000。而對(duì)于符號(hào)常數(shù),則需要很強(qiáng)的背景知識(shí)。因此,我們僅就發(fā)生在數(shù)據(jù)庫(kù)里的范圍選擇屬性值。

2.4 繁殖新一代種群
每個(gè)個(gè)體用預(yù)定義的適應(yīng)函數(shù)來(lái)進(jìn)行評(píng)價(jià)。較適應(yīng)的查詢有較高的概率被選來(lái)繁殖新種群,這個(gè)過(guò)程用三個(gè)遺傳算子:選擇、雜交和變異來(lái)完成。為了產(chǎn)生下一代,選擇算子根據(jù)個(gè)體的適應(yīng)值來(lái)選擇個(gè)體。我們用一個(gè)樹來(lái)表示一個(gè)查詢,雜交算子用交換兩個(gè)父輩的子樹來(lái)創(chuàng)建兩個(gè)后代。變異算子用一個(gè)新的子樹來(lái)代替一個(gè)父輩的子樹,從而產(chǎn)生一個(gè)新的后代。選擇-雜交-變異循環(huán)反復(fù)地進(jìn)行直到終止標(biāo)準(zhǔn)被滿足。

2.5 評(píng)價(jià)(適應(yīng)函數(shù)測(cè)量)
我們使用如下的適應(yīng)函數(shù)f來(lái)評(píng)價(jià)種群中的個(gè)體查詢i :
f ( ni , hi ) = T - ( hi * hi ) / ni ,
其中:ni > 0 , T ≥ hi , 且 i = 1 ,2 ,… ,種群的大。═是被確定的對(duì)象集的勢(shì),hi是一個(gè)個(gè)體查詢i 被選中的次數(shù),ni是查詢 i 結(jié)果集的勢(shì))。
上述適應(yīng)函數(shù)依賴于hi和ni ,如果一個(gè)查詢沒有被選中(hi=0),則函數(shù)的值為T,這是最差的一個(gè)適應(yīng)值。另一方面,如果查詢結(jié)果能夠很好地匹配提交給系統(tǒng)的對(duì)象集,那么它的適應(yīng)值為0(在這種情況下hi = ni = T )。如果種群中出現(xiàn)個(gè)體適應(yīng)值遠(yuǎn)遠(yuǎn)超過(guò)種群平均適應(yīng)值,該個(gè)體很快就會(huì)在群體中占有絕對(duì)的比例,從而出現(xiàn)過(guò)早收斂的現(xiàn)象。另一方面,在搜索過(guò)程的后期,群體的平均適應(yīng)值可能會(huì)接近群體的最優(yōu)適應(yīng)值,從而導(dǎo)致搜索目標(biāo)難以得到改善,出現(xiàn)停滯現(xiàn)象[4]。為了防止上述情況的發(fā)生,我們將對(duì)一個(gè)個(gè)體查詢的例子個(gè)數(shù) ni 作為分母。

3 一個(gè)例子
我們首先給出一個(gè)如表2所示的模擬"售后質(zhì)量管理函數(shù)數(shù)據(jù)庫(kù)",用它來(lái)代表一個(gè)基于OOFDM的面向?qū)ο髷?shù)據(jù)庫(kù),它包含了客戶及其相關(guān)的信息。表3說(shuō)明了類間的相互聯(lián)系。

類屬性值 客戶代碼、電話、名稱、地址、類別、地區(qū)、委托、購(gòu)買 代理商代碼、名稱、地址、電話、信譽(yù)等級(jí) 產(chǎn)品名稱、編號(hào)、出廠日期、購(gòu)買日期、檢驗(yàn)員 維修記錄問(wèn)題、維修時(shí)間、維修次數(shù)、維修員 使用培訓(xùn)否、技術(shù)力量 質(zhì)量問(wèn)題外觀、電器、機(jī)械、裝配
表2 售后質(zhì)量管理數(shù)據(jù)庫(kù)

類客戶代理商產(chǎn)品維修記錄使用質(zhì)量問(wèn)題 客戶   + +   +   代理商 +           產(chǎn)品 +       + + 維修記錄           + 使用 +   +       質(zhì)量問(wèn)題     + +    
表3 類間的連接表

3.1 問(wèn)題的提出
根據(jù)質(zhì)量管理部門反映,有兩個(gè)客戶反饋的產(chǎn)品質(zhì)量問(wèn)題較為嚴(yán)重,我們希望通過(guò)對(duì)數(shù)據(jù)庫(kù)的查詢來(lái)找出這兩個(gè)客戶在購(gòu)買的產(chǎn)品及使用上所具有的共性。



本文編號(hào):6515

資料下載
論文發(fā)表

本文鏈接:http://www.lk138.cn/kejilunwen/jisuanjikexuelunwen/6515.html


Copyright(c)文論論文網(wǎng)All Rights Reserved | 網(wǎng)站地圖 |

版權(quán)申明:資料由用戶86065***提供,本站僅收錄摘要或目錄,作者需要?jiǎng)h除請(qǐng)E-mail郵箱bigeng88@qq.com