畢業(yè)設(shè)計(jì)（論文）基于遺傳算法的數(shù)據(jù)挖掘方法研究及應(yīng)用

1、目錄摘要 1abstract(英文摘要) 2第一章緒論1.1 引言 31.2 國(guó)內(nèi)外研究現(xiàn)狀 3第二章數(shù)據(jù)挖掘概述2.1 數(shù)據(jù)挖掘的發(fā)展歷史 52.2 數(shù)據(jù)挖掘的定義 52.3 數(shù)據(jù)挖掘的目的、任務(wù)和對(duì)象 62.3.1 數(shù)據(jù)挖掘的目的 62.3.2 數(shù)據(jù)挖掘的任務(wù) 62.3.3 數(shù)據(jù)挖掘的對(duì)象 72.4 數(shù)據(jù)挖掘的特點(diǎn) 82.5 數(shù)據(jù)挖掘的常用方法 82.5.1 歸納學(xué)習(xí)方法 82.5.2 公式發(fā)現(xiàn) 92.5.3 統(tǒng)計(jì)分析方法 92.5.4仿生物技術(shù) 92.5.5可視化技術(shù) 102.6 數(shù)據(jù)挖掘的基本步驟 10第三章關(guān)聯(lián)規(guī)則基本理論3.1 關(guān)聯(lián)規(guī)則的定義及性質(zhì) 123.2 關(guān)聯(lián)規(guī)則的挖掘過程

2、133.3 衡量規(guī)則的價(jià)值 14第四章遺傳算法概述4.1 遺傳算法的發(fā)展歷史 154.2 遺傳算法的特點(diǎn) 154.3 基本遺傳算法的主要思想及術(shù)語(yǔ) 164.4 基本遺傳算法的描述與形式化定義 174.5 遺傳算法的基本實(shí)現(xiàn)技術(shù)及設(shè)計(jì)步驟 174.5.1 編碼方法的選取 174.5.2 適應(yīng)度函數(shù)的設(shè)計(jì) 184.5.3 遺傳算法的設(shè)計(jì)步驟 18第五章基于遺傳算法的關(guān)聯(lián)規(guī)則挖掘模型 19參考文獻(xiàn) 21致 謝 22摘要隨著人們對(duì)數(shù)據(jù)庫(kù)技術(shù)逐步深入的研究, 數(shù)據(jù)挖掘技術(shù)應(yīng)運(yùn)而生. 最初, 商業(yè)活動(dòng)中的各種數(shù)據(jù)僅僅是存儲(chǔ)在計(jì)算機(jī)的數(shù)據(jù)庫(kù)中, 然而為了人們對(duì)數(shù)據(jù)庫(kù)管理的需求, 我們開始能夠查詢并訪問計(jì)算機(jī)

3、的數(shù)據(jù)庫(kù), 從而實(shí)現(xiàn)了數(shù)據(jù)庫(kù)的即時(shí)遍歷. 數(shù)據(jù)挖掘技術(shù)甚至將數(shù)據(jù)庫(kù)技術(shù)推動(dòng)到了一個(gè)更為高級(jí)的階段, 自此這項(xiàng)技術(shù)不僅能夠查詢和遍歷過去的數(shù)據(jù), 并且能夠識(shí)別數(shù)據(jù)之間潛在的聯(lián)系, 從而對(duì)信息的傳遞起到相當(dāng)?shù)拇龠M(jìn)作用. 作為一門典型交叉學(xué)科, 數(shù)據(jù)挖掘具有計(jì)算機(jī)科學(xué)、統(tǒng)計(jì)學(xué)的學(xué)術(shù)背景,其為當(dāng)下數(shù)據(jù)庫(kù)系統(tǒng)研究及應(yīng)用領(lǐng)域的熱門研究方向, 吸引了學(xué)術(shù)界和業(yè)界的廣泛關(guān)注. 首先，本文對(duì)數(shù)據(jù)挖掘技術(shù)做了概述, 以明確其定義、目的、任務(wù)、對(duì)象及主要過程、基本方法. 其次, 我們對(duì)關(guān)聯(lián)規(guī)則的定義、性質(zhì)及種類等概念作初步介紹. 再次, 重點(diǎn)介紹著名的優(yōu)化搜索算法遺傳算法, 在回顧遺傳算法的發(fā)展歷史以及主要理論之后

4、, 給出了基本遺傳算法和算法描述以及算法的基本實(shí)現(xiàn)技術(shù). 基于以上本文提出一種基于遺傳算法的關(guān)聯(lián)規(guī)則提取方法, 并從編碼方法及適應(yīng)度函數(shù)等方面詳細(xì)討論. 最后，本文給出遺傳算法在關(guān)聯(lián)規(guī)則挖掘中的應(yīng)用模型. 關(guān)鍵詞：數(shù)據(jù)挖掘；遺傳算法；關(guān)聯(lián)規(guī)則；適應(yīng)度函數(shù)abstractdata mining is a result of long-term research on database technology. initially the data used on the business occasions were only stored incomputers database,whose i

5、nquiries and visits is later on developed then real-time database inquiries is further on so developed. data mining pushed database technology to an even more advanced stage. it can not only inquire old data butalso identify the potential relationship between them, thusbenefit the information spread

6、ing. as a typical cross-discipline,data mining is a popular area for the current research on database system and its applications,ithas a double academic backgrounds on computer science and statistics, and it hasalsocaught the attentions from industrial fields. firstly in this paper we give data min

7、ing an overview, as well as clarify its definition, purpose, mission andobjects, further we shall talk about the main processand techniques involved in data mining. secondly weintroduce its definition, nature, typesof the associated rules. witha huge significance weintroducegenetic algorithm,which i

8、s widely applied in data mining practices. we make a briefing on history and main theory of genetic algorithm, then give the basic genetic algorithms and its descriptionsalong with several basic implementation technologies. last but not least, webring forward a mining method for association rules wh

9、ich is mainly based on genetic algorithms. at the same time, we would like to discussthe genetic algorithms fromthe aspects such as coding method, fitness function andgenetic operators.as the ending of the paper, we give the application model of the association rules mining based on genetic. key wor

10、ds: data mining;genetic algorithm; fitness function; association rules第一章 緒論1.1引言計(jì)算機(jī)科學(xué)及現(xiàn)代通信技術(shù)的迅猛發(fā)展已將人類帶入了信息時(shí)代, 近幾十年應(yīng)由社會(huì)與經(jīng)濟(jì)發(fā)展的需求, 計(jì)算機(jī)的數(shù)據(jù)庫(kù)存儲(chǔ)的數(shù)據(jù)劇增, 人們掌握有大量的數(shù)據(jù)得以提取所需要的信息, 而這些數(shù)據(jù)所提供的信息在給人們帶來方便的同時(shí)也對(duì)原有數(shù)據(jù)庫(kù)技術(shù)提出了新的挑戰(zhàn). 現(xiàn)代社會(huì)的信息爆炸程度已遠(yuǎn)遠(yuǎn)超出了人們掌握和理解數(shù)據(jù)的能力, 這為正確地利用數(shù)據(jù)帶來了困難. 人們開始逐漸意識(shí)到, 那些能夠描述事物整體特征、預(yù)測(cè)未來發(fā)展趨勢(shì)的信息往往是隱藏在大規(guī)模的數(shù)

11、據(jù)背后更深層次的內(nèi)容, 這些潛在信息對(duì)于人們做出決策具有重要的參考價(jià)值. 那么如何透過巨量的數(shù)據(jù)信息獲取這些有用的“知識(shí)”呢？計(jì)算機(jī)科學(xué)與統(tǒng)計(jì)學(xué)的最新研究給出回答：數(shù)據(jù)挖掘. 數(shù)據(jù)挖掘匯集了數(shù)據(jù)庫(kù)、數(shù)理統(tǒng)計(jì)、人工智能、并行計(jì)算、可視化等諸多領(lǐng)域的研究者及業(yè)界的工程師,通過對(duì)數(shù)據(jù)庫(kù)進(jìn)行從微觀到宏觀的統(tǒng)計(jì)分析與綜合推理, 以發(fā)現(xiàn)數(shù)據(jù)之間的相互關(guān)聯(lián), 乃至利用已有數(shù)據(jù)對(duì)未來進(jìn)行預(yù)測(cè), 從而針對(duì)實(shí)際問題為人們提供決策支持. 1.2國(guó)內(nèi)外研究現(xiàn)狀數(shù)據(jù)挖掘技術(shù)在諸多方面已得到廣泛之應(yīng)用, 但就其目前的研究狀況來看, 這一技術(shù)還未能稱得上成熟, 故在應(yīng)用上有很大局限. 局限其一, 即挖掘?qū)ο笾窒? 面對(duì)維

12、數(shù)更高、各屬性之間更為復(fù)雜的超大型數(shù)據(jù)庫(kù), 現(xiàn)有數(shù)據(jù)挖掘技術(shù)處理如此巨量數(shù)據(jù)不免捉襟見肘；局限其二, 大部分?jǐn)?shù)據(jù)庫(kù)在知識(shí)發(fā)現(xiàn)的過程中可能存在數(shù)據(jù)或?qū)傩詠G失的問題；局限其三, 目前數(shù)據(jù)挖掘工具一般僅能處理特定數(shù)值型的結(jié)構(gòu)化數(shù)據(jù). 反而思之, 正是由于這些局限的存在, 方才能不斷推動(dòng)數(shù)據(jù)挖掘技術(shù)有著更為長(zhǎng)足的發(fā)展. 遺傳算法作為全局并行優(yōu)化搜索算法的有效性為人稱道, 其在解決具有混沌、隨機(jī)和非線性等典型特性的復(fù)雜問題中提供一種新的計(jì)算模型, 克服了由大量數(shù)據(jù)嘈雜無序造成的難題. 這一模擬自然界進(jìn)化過程的通用全局搜索算法, 有效避免搜索過程中出現(xiàn)的局部最優(yōu), 有望在規(guī)則發(fā)掘中大施拳腳. 遺傳算法自誕

13、生至今雖已經(jīng)過歷次改進(jìn), 但仍有待進(jìn)一步深入研究的必要. 其一, 算法的理論研究相對(duì)滯后, 遺傳算法提出之靈感源于一種仿生的思想, 故其盡管在實(shí)踐中被證明極為有用, 然而在理論證明上卻遇到瓶頸；其二, 算法的參數(shù)設(shè)置仍無明確標(biāo)準(zhǔn), 之前的應(yīng)用中采用的均為過往的經(jīng)驗(yàn)數(shù)值, 而不同編碼與遺傳技術(shù)將對(duì)遺傳參數(shù)的選取產(chǎn)生影響, 這無疑制約了算法的通用性；其三, 算法對(duì)于約束化問題的處理缺乏足夠的有效性. 近年對(duì)關(guān)聯(lián)規(guī)則挖掘的研究主要可分為四個(gè)方面. 一是改進(jìn)由r. agrawal等提出的apriori算法, 這些工作主要集中在有效地生成最大項(xiàng)目集并改善該算法效率；二是對(duì)關(guān)聯(lián)規(guī)則的閾值進(jìn)行調(diào)整, 增強(qiáng)所

14、挖掘規(guī)則的關(guān)聯(lián)性與有效性使之更為符合人們的需求；三是提出用于關(guān)聯(lián)規(guī)則發(fā)掘的并行算法；四是擴(kuò)展關(guān)聯(lián)規(guī)則發(fā)掘中的二級(jí)問題, 諸如多層/廣義關(guān)聯(lián)規(guī)則、循環(huán)關(guān)聯(lián)規(guī)則、定量關(guān)聯(lián)規(guī)則等. 因遺傳算法簡(jiǎn)單通用且適于并行處理之特性, 使其在數(shù)據(jù)挖掘技術(shù)占用舉足輕重的地位. 目前, 對(duì)以遺傳算法為基礎(chǔ)的數(shù)據(jù)挖掘研究主要在分類系統(tǒng)方面, 而在關(guān)聯(lián)規(guī)則提取方面的應(yīng)用仍未常見. 本文提出用遺傳算法輔助對(duì)關(guān)聯(lián)規(guī)則進(jìn)行挖掘, 便是希望能在這方面進(jìn)行新的嘗試. 第二章 數(shù)據(jù)挖掘概述2.1數(shù)據(jù)挖掘的發(fā)展歷史1989年8月, 于底特律召開的第十一屆國(guó)際人工智能聯(lián)合會(huì)議的專題討論中首次提出kdd(knowledge discov

15、ery in database)這一術(shù)語(yǔ). 隨后, 首屆知識(shí)發(fā)現(xiàn)和數(shù)據(jù)挖掘國(guó)際學(xué)術(shù)會(huì)議于1995年在加拿大蒙特利爾召開. 亞太地區(qū)則于1997年在新加坡召開了第一屆亞太知識(shí)發(fā)現(xiàn)和數(shù)據(jù)挖掘國(guó)際會(huì)議, 歐洲也于1998年召開了第一屆歐洲知識(shí)發(fā)現(xiàn)和數(shù)據(jù)挖掘?qū)W術(shù)會(huì)議. 知識(shí)發(fā)現(xiàn)和數(shù)據(jù)挖掘長(zhǎng)期作為數(shù)據(jù)庫(kù)和機(jī)器學(xué)習(xí)的分支, 直到1998年6月acm(associationofcomputingmachinery)成立sigkdd(specialinternetgrouponknowledgediscoveryanddatamining), 才使其正式脫身為一門獨(dú)立學(xué)科. metagroup有評(píng)論如下, “

16、全球重要的企業(yè)及各類組織將會(huì)發(fā)現(xiàn), 在二十一世紀(jì), 數(shù)據(jù)挖掘技術(shù)將在決定其在商業(yè)經(jīng)營(yíng)中成功與否產(chǎn)生至關(guān)重要的影響”. ibm在之后幾年隨即發(fā)布ibmdb2智能挖掘器積分服務(wù), 這一服務(wù)基于標(biāo)準(zhǔn)的數(shù)據(jù)挖掘技術(shù), 提供個(gè)性化解決方案. 統(tǒng)計(jì)軟件spss與sas亦分別推出數(shù)據(jù)挖掘工具clementine和enterpriseminer. 2.2數(shù)據(jù)挖掘的定義數(shù)據(jù)挖掘, 即從大量不完全并且模糊有噪聲的隨機(jī)數(shù)據(jù)中提取隱含其中事先未知卻潛在有用的信息和知識(shí)的過程. 這一表述具有若干層次含義, 其一, 數(shù)據(jù)挖掘中原始數(shù)據(jù)真實(shí)、大量且含噪聲；其二, 數(shù)據(jù)挖掘?qū)Ｗ⒂诎l(fā)現(xiàn)人們感興趣、有價(jià)值的知識(shí)；其三, 數(shù)據(jù)挖掘

17、著力于發(fā)現(xiàn)直覺無法發(fā)現(xiàn)乃至有悖直覺的知識(shí), 其越是出人意料, 便可能越有價(jià)值；其四, 潛在有用性是指數(shù)據(jù)挖掘發(fā)現(xiàn)的知識(shí)對(duì)于所討論的業(yè)務(wù)或研究領(lǐng)域具有實(shí)用價(jià)值, 諸如常識(shí)性的結(jié)論、已掌握的事實(shí)及無法實(shí)現(xiàn)的推論均視作無意義；其五, 數(shù)據(jù)挖掘發(fā)現(xiàn)的知識(shí)須可為人們所接受、理解并運(yùn)用于解決實(shí)際問題；其六, 數(shù)據(jù)挖掘并非要發(fā)現(xiàn)那些放之四海皆準(zhǔn)的真理抑或全新的自然科學(xué)定理, 所有被發(fā)現(xiàn)的知識(shí)都具有特定約束條件或面向特定領(lǐng)域. 目前來說, 學(xué)術(shù)界對(duì)數(shù)據(jù)挖掘仍未形成統(tǒng)一的精確定義, 在不同的文獻(xiàn)中, 不同的應(yīng)用領(lǐng)域里有著不同側(cè)重的定義表述. 常見的如ferruzza定義數(shù)據(jù)挖掘?yàn)橛谥R(shí)發(fā)現(xiàn)過程用以辨識(shí)存在數(shù)據(jù)間

18、未知關(guān)系和模式的方法；zekulin定義數(shù)據(jù)挖掘?yàn)閺拇笮蛿?shù)據(jù)庫(kù)中提取未知的、可理解的、可執(zhí)行的信息并利用其輔助商業(yè)決策的過程；parsaye則認(rèn)為數(shù)據(jù)挖掘是為獲取未知的信息模式而研究大型數(shù)據(jù)集合的決策支持過程. 2.3數(shù)據(jù)挖掘的目的、任務(wù)和對(duì)象2.3.1 數(shù)據(jù)挖掘的目的隨著數(shù)據(jù)庫(kù)及信息系統(tǒng)技術(shù)逐步深入的應(yīng)用, 面對(duì)長(zhǎng)時(shí)間積累所形成的海量數(shù)據(jù)人們常無所適從, 以至淹沒在數(shù)據(jù)的海洋中卻缺少“知識(shí)”. 我們開始考慮嘗試發(fā)現(xiàn)數(shù)據(jù)中存在的關(guān)系和規(guī)則并根據(jù)已有數(shù)據(jù)預(yù)測(cè)未來發(fā)展趨勢(shì), 從而做到不被信息淹沒, 提高信息利用率. 現(xiàn)在, 數(shù)據(jù)挖掘分析海量數(shù)據(jù)并發(fā)現(xiàn)其中的潛在聯(lián)系. 2.3.2數(shù)據(jù)挖掘的任務(wù)數(shù)據(jù)挖

19、掘有關(guān)聯(lián)分析、時(shí)間序列模式、聚類、分類、偏差檢測(cè)及預(yù)測(cè)六項(xiàng)基本任務(wù). 我們先討論關(guān)聯(lián)分析. 當(dāng)若干數(shù)據(jù)項(xiàng)取值出現(xiàn)重復(fù), 這之間即有某種關(guān)聯(lián), 從而可建立關(guān)聯(lián)規(guī)則. 我們常用“可信度”與“支持度”對(duì)其進(jìn)行篩選. 時(shí)間序列模式即根據(jù)時(shí)間序列搜索重復(fù)發(fā)生概率較高的模式. 我們需要在時(shí)序模式中找出在某個(gè)最小時(shí)間段內(nèi)出現(xiàn)概率高于閾值的規(guī)則, 當(dāng)然, 隨著形式的變化我們將對(duì)規(guī)則做出適當(dāng)?shù)恼{(diào)整. 聚類, 即根據(jù)意義之不同對(duì)數(shù)據(jù)庫(kù)中的數(shù)據(jù)劃分一系列子集, 即類. 人們通過聚類以建立宏觀概念,統(tǒng)計(jì)分析、機(jī)器學(xué)習(xí)和神經(jīng)網(wǎng)絡(luò)均是常見方法. 分類作為數(shù)據(jù)挖掘中應(yīng)用最多的任務(wù), 描述一個(gè)類別的概念以代表這類數(shù)據(jù)的整體信

20、息, 稱為其內(nèi)涵描述, 一般用規(guī)則或決策樹表示. 分類可將數(shù)據(jù)庫(kù)中元組影射到給定類別的某一個(gè)中. 分類通常是基于訓(xùn)練樣本集（已知數(shù)據(jù)庫(kù)元組及類別所組成的樣本）通過相關(guān)算法求得. 然后是偏差檢測(cè). 數(shù)據(jù)庫(kù)中數(shù)據(jù)往往存在諸多異常, 偏差檢測(cè)便是尋找觀察結(jié)果與參照之間的差別. 觀察結(jié)果一般為一個(gè)或多個(gè)域的值的匯總, 參照則通常是給定模型的預(yù)測(cè)結(jié)果、外界提供的標(biāo)準(zhǔn)或另一個(gè)觀察結(jié)果. 最后我們討論預(yù)測(cè). 預(yù)測(cè), 顧名思義, 從歷史數(shù)據(jù)中尋找變化規(guī)律以建立模型, 并基于此預(yù)測(cè)未來. 主流的預(yù)測(cè)方法有回歸分析和神經(jīng)網(wǎng)絡(luò), 回歸分析用于預(yù)測(cè)連續(xù)數(shù)值, 而神經(jīng)網(wǎng)絡(luò)預(yù)測(cè)則連續(xù)、離散皆適用. 2.3.3數(shù)據(jù)挖掘的對(duì)

21、象理論上, 在任何類型的數(shù)據(jù)存儲(chǔ)上均可進(jìn)行數(shù)據(jù)挖掘, 包括關(guān)系數(shù)據(jù)庫(kù)、事務(wù)數(shù)據(jù)庫(kù)、數(shù)據(jù)倉(cāng)庫(kù)等. 這里我們對(duì)主要的數(shù)據(jù)挖掘?qū)ο笥枰越榻B. 首先是關(guān)系數(shù)據(jù)庫(kù). 關(guān)系數(shù)據(jù)庫(kù)是表的集合, 每個(gè)表命名唯一, 其中包含一組屬性用于存放大量元組. 關(guān)系中每一元組代表一個(gè)被唯一關(guān)鍵字標(biāo)識(shí)的對(duì)象, 并由一組屬性值所描述. 關(guān)系數(shù)據(jù)庫(kù)可通過數(shù)據(jù)庫(kù)的結(jié)構(gòu)化查詢語(yǔ)言訪問. 關(guān)系數(shù)據(jù)庫(kù)擁有完備的數(shù)學(xué)理論基礎(chǔ)且具有相當(dāng)高的普及度, 是當(dāng)下數(shù)據(jù)挖掘最為豐富的數(shù)據(jù)源之一. 其次, 我們討論事務(wù)數(shù)據(jù)庫(kù). 一般地, 事務(wù)數(shù)據(jù)庫(kù)由一個(gè)文件組成, 每一個(gè)事物由其中一個(gè)記錄所代表. 通常, 一個(gè)事務(wù)有唯一的事務(wù)標(biāo)識(shí)號(hào)和一個(gè)組成項(xiàng)列表（

22、部分包含事務(wù)的處理時(shí)間）. 事務(wù)數(shù)據(jù)庫(kù)常應(yīng)用于“購(gòu)物籃數(shù)據(jù)分析”, 其對(duì)關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘十分有效. 再次, 我們介紹數(shù)據(jù)倉(cāng)庫(kù). 數(shù)據(jù)倉(cāng)庫(kù)的創(chuàng)始人williamh.inmon對(duì)數(shù)據(jù)倉(cāng)庫(kù)定義如下：數(shù)據(jù)倉(cāng)庫(kù)是面向主題的(subject-oriented)、集成的(integrated)、隨時(shí)間而變化的(time-variant)、穩(wěn)定的(non-volatile)數(shù)據(jù)集合. 從辨證的角度來看, 從關(guān)系數(shù)據(jù)模型到數(shù)據(jù)倉(cāng)庫(kù)的誕生, 數(shù)據(jù)倉(cāng)庫(kù)的出現(xiàn)與廣泛為人們所接受實(shí)質(zhì)上是數(shù)據(jù)管理螺旋式的上升.數(shù)據(jù)倉(cāng)庫(kù)技術(shù)的逐步成熟很大程度上推動(dòng)了數(shù)據(jù)挖掘技術(shù)的繁榮. 近年來, 數(shù)據(jù)庫(kù)技術(shù)發(fā)生了翻天覆地的變化, 其已由

23、最初單一的關(guān)系數(shù)據(jù)庫(kù)逐步發(fā)展為面向?qū)ο髷?shù)據(jù)庫(kù)、事物數(shù)據(jù)庫(kù)、空間數(shù)據(jù)庫(kù)、對(duì)象-關(guān)系數(shù)據(jù)庫(kù)、多媒體數(shù)據(jù)庫(kù)等新的數(shù)據(jù)庫(kù)系統(tǒng), 與此同時(shí), 數(shù)據(jù)挖掘的數(shù)據(jù)來源也更多地取自于新型的高級(jí)數(shù)據(jù)庫(kù)系統(tǒng). 2.4數(shù)據(jù)挖掘的特點(diǎn)數(shù)據(jù)挖掘的特點(diǎn)可初步歸納為五個(gè)方面. 其一, 數(shù)據(jù)挖掘所處理的數(shù)據(jù)規(guī)模十分龐大；其二, 數(shù)據(jù)庫(kù)查詢一般是即時(shí)的隨機(jī)查詢, 因不能有精確查詢要求, 數(shù)據(jù)挖掘技術(shù)則可輔助尋找用戶感興趣的知識(shí)；其三, 在一些應(yīng)用中數(shù)據(jù)在很短時(shí)間內(nèi)即有較大變化, 數(shù)據(jù)挖掘技術(shù)能夠在這種情況下快速反應(yīng)以提供決策支持；其四, 數(shù)據(jù)挖掘不僅要發(fā)現(xiàn)潛在規(guī)則, 而且要管理、維護(hù)規(guī)則, 規(guī)則往往不是一成不變的, 隨著數(shù)據(jù)的不

24、斷更新, 規(guī)則亦需隨之而變；其五, 數(shù)據(jù)挖掘是基于大樣本統(tǒng)計(jì)規(guī)律發(fā)現(xiàn)規(guī)則, 這未必適用于全部數(shù)據(jù), 當(dāng)達(dá)到某一閾值時(shí)即可認(rèn)為此規(guī)則成立. 2.5數(shù)據(jù)挖掘的常用方法2.5.1歸納學(xué)習(xí)方法歸納學(xué)習(xí)方法從技術(shù)上分為兩類：信息論方法與集合論方法. 我們先討論前者. 信息論方法主要基于信息論原理建立決策樹, 由于最終將以決策樹的形式表示知識(shí), 故文獻(xiàn)中經(jīng)常稱其為決策樹方法. 這里我們介紹兩種較有特色的信息論方法. 一是id3等系列方法, 其利用信息增益尋找包含最大信息量的字段以建立樹的結(jié)點(diǎn), 由不同字段取值建立分枝, 再對(duì)數(shù)據(jù)子集重復(fù)以上過程, 最終建立決策樹. 對(duì)愈為龐大的數(shù)據(jù)庫(kù), 這一方法愈為有效；

25、還有一種方法我們稱為ible(information-basedlearningfromexamples)方法, 其根據(jù)信息量大小尋找各字段取值建立樹的結(jié)點(diǎn), 并將結(jié)點(diǎn)中指定字段值的權(quán)值和與閾值比較, 建立三個(gè)分枝, 再對(duì)各分枝子集重復(fù)以上過程, 最終建立決策樹. 再說集合論方法.這類方法廣為人知的有覆蓋正例排斥反例的方法、概念樹方法和粗糙集(roughset)方法.概念樹方法則是將數(shù)據(jù)庫(kù)中的屬性字段根據(jù)歸類方式進(jìn)行合并, 以此建立的層次結(jié)構(gòu)稱為概念樹；最后介紹粗糙集方法, 我們將數(shù)據(jù)庫(kù)中的行元素看作對(duì)象, 列元素看作屬性（分為條件屬性與決策屬性）. 定義等價(jià)關(guān)系為不同對(duì)象某一個(gè)或多個(gè)屬性具有

26、相同取值, 稱滿足同一等價(jià)關(guān)系的對(duì)象所組成的集合為該等價(jià)關(guān)系的等價(jià)類. 條件屬性上等價(jià)類與決策屬性上等價(jià)類之間有三種關(guān)系, 分別是下近似(包含)、上近似(和的交非空)和無關(guān)(和的交為空). 我們對(duì)下近似建立確定性規(guī)則, 對(duì)上近似建立不確定性規(guī)則, 而無關(guān)情況下則不存在規(guī)則. 2.5.2公式發(fā)現(xiàn)公式發(fā)現(xiàn)的含義即是對(duì)工程或科學(xué)數(shù)據(jù)庫(kù)中的若干數(shù)據(jù)項(xiàng)進(jìn)行數(shù)學(xué)運(yùn)算并求相應(yīng)的數(shù)學(xué)公式. 這里舉兩個(gè)典型的例子. 一是經(jīng)驗(yàn)公式發(fā)現(xiàn)系統(tǒng)fdd, 其基本思想是對(duì)兩個(gè)數(shù)據(jù)項(xiàng)交替取初等函數(shù)后再與另一數(shù)據(jù)項(xiàng)進(jìn)行線性組合, 若組合結(jié)果為直線, 就得到由數(shù)據(jù)項(xiàng)的初等函數(shù)表示的線性組合公式；二是物理定律發(fā)現(xiàn)系統(tǒng)bacon,

27、其基本思想很簡(jiǎn)單, 就是對(duì)數(shù)據(jù)項(xiàng)進(jìn)行初等數(shù)學(xué)運(yùn)算以形成組合數(shù)據(jù)項(xiàng), 若值為常數(shù), 就得到組合數(shù)據(jù)項(xiàng)等于常數(shù)的公式. 2.5.3統(tǒng)計(jì)分析方法統(tǒng)計(jì)分析利用統(tǒng)計(jì)學(xué)原理分析數(shù)據(jù)庫(kù)中數(shù)據(jù)從而得到其中的統(tǒng)計(jì)信息與知識(shí), 已發(fā)展成一門獨(dú)立的學(xué)科. 下面簡(jiǎn)要介紹六種統(tǒng)計(jì)分析中的基本方法. 一是常用統(tǒng)計(jì), 即求最簡(jiǎn)單的統(tǒng)計(jì)量；二是相關(guān)分析, 即計(jì)算變量間的相關(guān)系數(shù)；三是回歸分析, 即以回歸方程表示變量間數(shù)量關(guān)系；四是差異分析, 即從樣本統(tǒng)計(jì)量的出發(fā)進(jìn)行假設(shè)檢驗(yàn)；五是聚類分析, 即直接計(jì)算樣本數(shù)據(jù)間的距離, 將距離小于某一閾值的歸為一類；六是判別分析, 即確立一個(gè)判別標(biāo)準(zhǔn)以建立一個(gè)或多個(gè)判別函數(shù), 據(jù)此將未知對(duì)象

28、劃歸到某一類別. 2.5.4仿生物技術(shù)典型的仿生物技術(shù)方法有遺傳算法和神經(jīng)網(wǎng)絡(luò)方法.我們先討論遺傳算法. 遺傳算法的基本思路是模擬生物進(jìn)化過程, 有選擇、交叉和變異三個(gè)基本遺傳算子. 選擇算子描述從舊種群選擇出具有更強(qiáng)競(jìng)爭(zhēng)力的個(gè)體產(chǎn)生新種群的過程；交叉算子描述兩個(gè)不同個(gè)體（染色體）的部分（基因序列）進(jìn)行交換并產(chǎn)生新個(gè)體的過程；變異算子描述個(gè)體的某些基因進(jìn)行變異（1變0, 0變1）的現(xiàn)象. 在優(yōu)化計(jì)算和分類機(jī)器學(xué)習(xí)方面遺傳算法已廣泛應(yīng)用并證實(shí)了其顯著的效果. 后文將對(duì)遺傳算法做進(jìn)一步介紹. 再討論神經(jīng)網(wǎng)絡(luò)方法. 神經(jīng)網(wǎng)絡(luò)方法基于mp模型與hebb學(xué)習(xí)規(guī)則, 模擬人腦神經(jīng)元結(jié)構(gòu)建立三類多種神經(jīng)網(wǎng)絡(luò)

29、模型. 一是前饋式網(wǎng)絡(luò), 其代表為感知機(jī)、bp反向傳播模型及函數(shù)型網(wǎng)絡(luò). 此類網(wǎng)絡(luò)在預(yù)測(cè)和模式識(shí)別方面有廣泛應(yīng)用；二是反饋式網(wǎng)絡(luò), 其代表是hopfield的連續(xù)及離散模型, 分別應(yīng)用于優(yōu)化計(jì)算和聯(lián)想記憶；三是自組織網(wǎng)絡(luò), 其代表為kohonen模型和art模型, 常用于聚類. 2.5.5可視化技術(shù)可視化技術(shù), 顧名思義, 是一種圖形顯示技術(shù). 以圖形顯示多維數(shù)據(jù), 可深刻揭示數(shù)據(jù)的分布規(guī)律及內(nèi)在本質(zhì). 同樣, 對(duì)數(shù)據(jù)挖掘過程進(jìn)行可視化與人機(jī)交互可顯著提高挖掘效果. d.a.keim定義數(shù)據(jù)挖掘可視化為尋找并分析數(shù)據(jù)庫(kù)以找到隱藏的有用信息的過程. 常見的可視化方法有三種, 一是提取幾何圖元,

30、在構(gòu)造、仿真和分析數(shù)據(jù)分布模型上極為有效；二是繪制, 主要基于計(jì)算機(jī)圖形學(xué)近年的發(fā)展成果來進(jìn)行圖像生成、消隱、光照效應(yīng)及部件繪制；三是顯示和演放, 為取得更佳顯示效果, 圖片組合、文件標(biāo)準(zhǔn)、著色、旋轉(zhuǎn)、放大和存儲(chǔ)等諸多功能在這一部件中均有提供. 2.6數(shù)據(jù)挖掘的基本步驟以下我們將以順序方式列出數(shù)據(jù)挖掘的各步驟, 但數(shù)據(jù)挖掘過程并不是線性的, 需不斷重復(fù)以下步驟以得到最優(yōu)的結(jié)果. 步驟一：確定業(yè)務(wù)對(duì)象. 首先, 對(duì)業(yè)務(wù)問題要有清晰的定義, 數(shù)據(jù)挖掘的第一步也是最為重要的一步即是認(rèn)清數(shù)據(jù)挖掘的目的；步驟二：數(shù)據(jù)準(zhǔn)備.包含數(shù)據(jù)選擇、預(yù)處理與轉(zhuǎn)換；步驟三：數(shù)據(jù)挖掘. 挖掘已經(jīng)過轉(zhuǎn)換之?dāng)?shù)據(jù), 只需選擇適

31、當(dāng)?shù)耐诰蛩惴? 剩下的工作可交由計(jì)算機(jī)自動(dòng)完成. 步驟四：結(jié)果分析. 即解釋并評(píng)估結(jié)果, 用到的分析方法由數(shù)據(jù)挖掘的具體操作決定, 可視化技術(shù)通常會(huì)被應(yīng)用于此. 步驟五：知識(shí)的同化. 即在業(yè)務(wù)信息系統(tǒng)的組織結(jié)構(gòu)中集成數(shù)據(jù)挖掘所得知識(shí). 第三章 關(guān)聯(lián)規(guī)則基本理論3.1關(guān)聯(lián)規(guī)則的定義及性質(zhì)定義3.1 設(shè)為個(gè)不同項(xiàng)目之集合, 為事務(wù)數(shù)據(jù)庫(kù), 其中每一事務(wù)為一項(xiàng)目子集, 即. 稱事務(wù)包含項(xiàng)目集, 表示為. 關(guān)聯(lián)規(guī)則為形如的邏輯蘊(yùn)含式, 其中, 且. 稱作前提, 稱作結(jié)果. 定義3.2 若事務(wù)數(shù)據(jù)庫(kù)中有的事務(wù)包含, 則稱規(guī)則的支持度為；若事務(wù)數(shù)據(jù)庫(kù)中包含的事務(wù)中有也包含, 則稱規(guī)則的置信度為. 可信度表

32、示的是一條規(guī)則可信賴的程度. 我們發(fā)現(xiàn)關(guān)聯(lián)規(guī)則是為了找到可信賴且具有代表性的規(guī)則, 因而我們需要事先對(duì)支持度和可信度分別給定最小閾值, 所謂發(fā)現(xiàn)關(guān)聯(lián)規(guī)則, 即是發(fā)現(xiàn)可信度與支持度均高于閾值的規(guī)則. 性質(zhì)4.1 若關(guān)聯(lián)規(guī)則與在中均成立, 規(guī)則不一定在中成立. 性質(zhì)4.2 若, 且中支持的都只支持或, 則的支持度為零, 故規(guī)則的可信度為零. 性質(zhì)4.1-2描述了關(guān)聯(lián)規(guī)則的非結(jié)合性, 因其據(jù)定義顯然, 故此不復(fù)證之. 類似地, 若與成立, 不一定成立. 性質(zhì)4.3 若在中成立, 與不一定在中成立. 證 由與, 若成立, 則與均成立, 矛盾, 故得證. 性質(zhì)4.3描述的是關(guān)聯(lián)規(guī)則的不可分解性. 性質(zhì)4

33、.4 由及不能推出. 證 設(shè)最小可信度為, 即由, 由, 由, , 又, 故, 故規(guī)則不成立. 證畢. 性質(zhì)4.4描述的是關(guān)聯(lián)規(guī)則的不可傳遞性. 性質(zhì)4.5 設(shè)項(xiàng)目集滿足, 若不滿足最小可信度條件, 則也不滿足最小可信度條件. 證 由子集支持性質(zhì), 設(shè)和是兩個(gè)不同的項(xiàng)目集, 若, 則. 又因中支持的交易一定支持, 故, 再由可信度定義有, 同理, 對(duì)滿足的項(xiàng)目集, 若成立, 則亦成立. 性質(zhì)4.5描述的是關(guān)聯(lián)規(guī)則的可擴(kuò)展性, 當(dāng)項(xiàng)目集及支持度已確定, 可用這一性質(zhì)加速規(guī)則發(fā)現(xiàn)的過程. 3.2關(guān)聯(lián)規(guī)則的挖掘過程關(guān)聯(lián)規(guī)則的挖掘一般有兩個(gè)過程, 一是找出所有頻繁項(xiàng)集,二是由頻繁項(xiàng)集產(chǎn)生關(guān)聯(lián)規(guī)則, 這

34、些規(guī)則須滿足可信度和支持度條件. 第二個(gè)過程須在前一個(gè)的基礎(chǔ)上進(jìn)行, 工作量較小, 而過程一則決定了關(guān)聯(lián)規(guī)則挖掘總體性能. 關(guān)聯(lián)規(guī)則的可信度較之期望要高方才表明的出現(xiàn)對(duì)的出現(xiàn)產(chǎn)生促進(jìn)作用, 即表明其之間在某種程度上相關(guān). 對(duì)于給定交易集, 挖掘關(guān)聯(lián)規(guī)則便是發(fā)現(xiàn)可信度與支持度均大于預(yù)先給定閾值的關(guān)聯(lián)規(guī)則. 3.3衡量規(guī)則的價(jià)值在用數(shù)據(jù)挖掘方法發(fā)現(xiàn)了一些關(guān)聯(lián)規(guī)則后, 系統(tǒng)如何得知哪些規(guī)則對(duì)于用戶來說是有價(jià)值的？對(duì)這個(gè)問題常分為兩個(gè)層面來考慮, 即系統(tǒng)客觀層面與用戶主觀層面. 我們先討論系統(tǒng)客觀層面. 首先, 我們需明確一點(diǎn)：使用前文所述的“支持度和信任度”框架可能發(fā)掘出“不正確”的規(guī)則, 即若我們

35、人為地將閾值設(shè)置得過低, 則可能得到互相矛盾的規(guī)則, 而反之,若閾值被設(shè)置得過高, 則所得到的規(guī)則又可能不合實(shí)際. 因此只依靠可信度與支持度的閾值設(shè)定不一定能得出我們需要的規(guī)則. 于是, “興趣度”這一概念被引入用來篩掉我們不感興趣的規(guī)則. 在統(tǒng)計(jì)獨(dú)立性假設(shè)下, 定義一條規(guī)則的興趣度為真實(shí)強(qiáng)度與期望強(qiáng)度之比值. 再是用戶主觀層面的考慮, 之前的討論僅僅是基于系統(tǒng)方面, 但規(guī)則的價(jià)值判定最終仍應(yīng)取決于用戶, 因?yàn)橛心芰Ψ直嫠诰蛞?guī)則有效性與可行性的只有用戶. 這里我們提出可以采用一種基于約束(constraint-based)的挖掘方式, 包括數(shù)據(jù)約束、維度/層次的約束乃至規(guī)則約束, 這其中的約

36、束條件能夠和算法緊密結(jié)合, 從而可以做到既提高效率, 又更加明確挖掘的目的. 第四章 遺傳算法概述4.1遺傳算法的發(fā)展歷史上世紀(jì)六十年代密歇根大學(xué)的j.h.holland教授首先提出將生物體通過遺傳變異來適應(yīng)環(huán)境的進(jìn)化論思想應(yīng)用于優(yōu)化技術(shù)并基于此設(shè)計(jì)新的優(yōu)化算法. 在研究自適應(yīng)系統(tǒng)時(shí)他即提出系統(tǒng)與外部環(huán)境相互作用與協(xié)調(diào)的重要性. 另一方面, 涉及到進(jìn)化算法的思想, 他則已經(jīng)意識(shí)到利用群體搜索方法及選擇交叉等策略. 隨后, 他和他的學(xué)生們?cè)谧赃m應(yīng)系統(tǒng)方面做了許多工作, 1967年j.d.bagay在其博士論文中首次使用了遺傳算法(geneticalgorithm)這一術(shù)語(yǔ), 他采用的是雙倍體編碼

37、, 并發(fā)展了復(fù)制、交叉及變異等基因操作, 提出了自組織遺傳算法及適應(yīng)度定標(biāo)的概念. j.h.holland教授于1975年問世的專著自然界和人工系統(tǒng)的適應(yīng)性較為全面地介紹了遺傳算法. 遺傳算法的數(shù)學(xué)基礎(chǔ)由這本書所奠定, 現(xiàn)在人們常將其視為遺傳算法正式誕生并得到世人承認(rèn)的標(biāo)志, 至此遺傳算法已完成萌芽及蘊(yùn)育階段, j.h.holland亦被視為遺傳算法的funding father. 直到八十年代, 遺傳算法經(jīng)歷了不斷的完善與成長(zhǎng), 并且隨著研究和應(yīng)用逐步深入, 一系列以遺傳算法為主題的國(guó)際會(huì)議一度非常活躍.研究者們意識(shí)到, 對(duì)復(fù)雜問題求最優(yōu)解常常是不現(xiàn)實(shí)的, 遺傳算法在尋求近似解中則可大展身手

38、, 因?yàn)槿魏螖?shù)學(xué)理論與證明都不會(huì)比自然界中生物遺傳進(jìn)化的客觀事實(shí)更有效用與說服力. 4.2遺傳算法的特點(diǎn)歸納來講, 遺傳算法與其他優(yōu)化算法相比主要有四大特點(diǎn). 其一, 遺傳算法對(duì)決策變量的編碼進(jìn)行運(yùn)算, 傳統(tǒng)優(yōu)化算法則往往直接計(jì)算決策變量的實(shí)際值. 對(duì)決策變量的進(jìn)行編碼處理使借鑒遺傳學(xué)中染色體和基因的概念以模仿自然界生物遺傳進(jìn)化機(jī)理有了可能, 尤其是對(duì)于無數(shù)值概念的優(yōu)化問題, 編碼處理方式顯示了其不可替代的優(yōu)越性；其二, 遺傳算法可直接搜索目標(biāo)函數(shù), 而傳統(tǒng)優(yōu)化算法還往往需要其他輔助信息（如導(dǎo)數(shù)值）. 遺傳算法僅由適應(yīng)度函數(shù)值（由目標(biāo)函數(shù)值變換而來）便可進(jìn)一步確定搜索范圍, 這一特點(diǎn)使得對(duì)難以

39、求導(dǎo)（或?qū)?shù)不存在）的目標(biāo)函數(shù)的優(yōu)化問題的求解便捷了許多；其三, 遺傳算法同時(shí)使用多點(diǎn)搜索, 而傳統(tǒng)優(yōu)化算法則是從解空間某初始點(diǎn)開始迭代搜索以尋求最優(yōu)解, 而單個(gè)搜索點(diǎn)所提供的搜索信息限制了算法的搜索效率, 甚至于陷入局部最優(yōu)解而停滯不前. 遺傳算法從初始群體而非單一個(gè)體開始搜索, 對(duì)初始群體進(jìn)行的選擇、交叉及變異等運(yùn)算產(chǎn)生出新一代的群體, 其中必然包括諸多群體信息, 從而可避免搜索那些不必搜索的點(diǎn), 實(shí)質(zhì)則相當(dāng)于搜索了更多的點(diǎn), 我們稱其為遺傳算法特有的“隱含并行性”；其四, 遺傳算法使用概率搜索, 而很多傳統(tǒng)優(yōu)化算法更多是用確定性的搜索算法, 這無疑限制了算法的應(yīng)用范圍. 4.3基本遺傳算

40、法的主要思想及術(shù)語(yǔ)自然界中的生物體在演進(jìn)過程中通過遺傳變異來適應(yīng)環(huán)境并發(fā)展進(jìn)化, 遺傳算法模擬了這一進(jìn)化現(xiàn)象. 在遺傳算法中, 我們將問題的解空間映為遺傳空間, 所謂向量是由空間中每個(gè)可能的解編碼得到, 亦稱為一個(gè)染色體, 群體由全體染色體所組成, 并依預(yù)先給定的適應(yīng)度函數(shù)評(píng)價(jià)群體中的每個(gè)染色體, 從而給出其適應(yīng)度. 算法初始化時(shí)染色體隨機(jī)產(chǎn)生并計(jì)算其適應(yīng)度, 然后根據(jù)適應(yīng)度的取值對(duì)其進(jìn)行遺傳操作以篩除適應(yīng)度低的染色體, 從而得到新的群體. 經(jīng)此反復(fù)迭代, 群體將不斷進(jìn)化, 直到滿足預(yù)先給定的優(yōu)化指標(biāo)，即得到了所求的最優(yōu)解. 作為計(jì)算機(jī)科學(xué)與遺傳學(xué)相互結(jié)合滲透的產(chǎn)物, 遺傳算法借用了一些生物學(xué)

41、上的基礎(chǔ)術(shù)語(yǔ). 如群體(population)和個(gè)體(individual), 染色體作為個(gè)體是遺傳算法的處理對(duì)象, 以一維串結(jié)構(gòu)數(shù)據(jù)表示, 若干個(gè)體組成的集合成為群體, 也稱為集團(tuán). 群體規(guī)模表示群體中個(gè)體的數(shù)量. 適應(yīng)度, 顧名思義為個(gè)體對(duì)外部環(huán)境的適應(yīng)程度, 適應(yīng)度函數(shù)在優(yōu)化問題中即為目標(biāo)函數(shù). 4.4 基本遺傳算法的描述與形式化定義在遺傳算法中, 我們以表示維決策向量. 其中每個(gè)元素可視作一個(gè)遺傳基因, 其所有可能取值稱為等位基因, 從而可被視作由若干遺傳基因組成的一個(gè)染色體, 遺傳算法的解空間由決策變量組成. 遺傳算法以所謂遺傳算子(geneticoperators)作用于群體, 與

42、生物進(jìn)化過程中染色體的交叉與變異對(duì)應(yīng)的，有選擇(selection)算子、交叉(crossover)算子和變異(mutation)算子. 只使用這三種基本算子的遺傳算法我稱為基本遺傳算法(simplegeneticalgorithms, sga), 構(gòu)成其四要素為染色體編碼、個(gè)體適應(yīng)度評(píng)價(jià)、遺傳算子及運(yùn)行參數(shù). 基本遺傳算法可形式化定義為一個(gè)由八個(gè)元素組成的組, 即, 其中, 表示染色體的編碼方法, 表示染色體的適應(yīng)度評(píng)價(jià)函數(shù), 表示初始群體, 表示群體大小, 表示選擇算子, 表示交叉算子, 表示變異算子, 表示終止條件. 4.5 遺傳算法的基本實(shí)現(xiàn)技術(shù)及設(shè)計(jì)步驟4.5.1編碼方法的選取迄今各

43、個(gè)領(lǐng)域應(yīng)用于遺傳算法的編碼技術(shù)主要有二進(jìn)制、浮點(diǎn)數(shù)編碼、可變?nèi)旧w長(zhǎng)度編碼及樹結(jié)構(gòu)編碼. 以下我們對(duì)以上編碼方法作簡(jiǎn)要介紹. 二進(jìn)制編碼作為一種一維染色體編碼方法, 將參數(shù)從搜索空間轉(zhuǎn)換到遺傳空間后染色體呈一維排列. 二進(jìn)制編碼方法對(duì)多維且精度要求高的連續(xù)函數(shù)優(yōu)化存在離散化映射誤差, 為克服這一缺點(diǎn)人們提出所謂浮點(diǎn)數(shù)編碼方法, 即用浮點(diǎn)數(shù)表示個(gè)體基因值, 個(gè)體編碼長(zhǎng)度就是其決策變量個(gè)數(shù), 由于這里使用的是決策變量的真實(shí)值, 故浮點(diǎn)數(shù)編碼方法也稱真值編碼方法. 我們知道, 生物進(jìn)化過程中生物的染色體長(zhǎng)度并非是固定不變的, 為描述這一現(xiàn)象, goldberg等人提出了一種可變長(zhǎng)度的染色體編碼方法用

44、以克服基本遺傳算法在處理非線性問題上的不足, 除此之外還可以提高函數(shù)優(yōu)化及算法搜索性能, 從而提高短距模式下的檢測(cè)與重組效率. 然而, 以上編碼方法在諸多應(yīng)用場(chǎng)合已顯現(xiàn)出若干不足之處, 如所求問題之結(jié)構(gòu)層次難于個(gè)體所表示, 且問題的解須經(jīng)特定編碼與解碼技術(shù)才能表示為合適的形式, 最重要的, 以上編碼方法在表示高層次知識(shí)及相應(yīng)學(xué)習(xí)系統(tǒng)方面顯得余力不足. 在實(shí)際應(yīng)用中, 由于很多問題本身可由結(jié)構(gòu)方式描述, 故可將其結(jié)構(gòu)表示直接作為染色體處理, 總而省去編碼譯碼操作. 4.5.2 適應(yīng)度函數(shù)的設(shè)計(jì)遺傳算法中設(shè)計(jì)適應(yīng)度函數(shù)有一些基本準(zhǔn)則, 其適應(yīng)度函數(shù)并不需要滿足連續(xù)可微條件, 且其定義域可為任意集合

45、. 在處理規(guī)模較小群體的遺傳算法進(jìn)化初期, 常出現(xiàn)占群體比例極高的異常個(gè)體, 這一現(xiàn)象可能導(dǎo)致未成熟收斂, 進(jìn)一步影響算法的全局優(yōu)化. 除此之外, 在進(jìn)化過程中群體平均適應(yīng)度接近最佳時(shí)即使仍存在個(gè)體多樣性, 但因個(gè)體間競(jìng)爭(zhēng)減弱使得最佳個(gè)體無法獲得被優(yōu)先選擇的機(jī)會(huì), 導(dǎo)致優(yōu)化過程趨于隨機(jī)漫游. 對(duì)于未成熟收斂現(xiàn)象, 可縮小適應(yīng)度函數(shù)值以削弱異常個(gè)體競(jìng)爭(zhēng)力；相應(yīng)對(duì)于隨機(jī)漫游現(xiàn)象, 可放大適應(yīng)度函數(shù)值以促進(jìn)個(gè)體間競(jìng)爭(zhēng). 稱這種對(duì)適應(yīng)度的縮放調(diào)整為適應(yīng)度定標(biāo),常見定標(biāo)方式有線性定標(biāo)、截?cái)嗉俺藘鐦?biāo). 4.5.3 遺傳算法的設(shè)計(jì)步驟步驟一, 確定決策變量及約束條件；步驟二, 建立優(yōu)化模型及其數(shù)學(xué)描述形式（

46、量化方法）；步驟三, 確定染色體編碼與解碼方法；步驟四, 確定對(duì)適應(yīng)度的量化評(píng)價(jià)方法；步驟五, 設(shè)計(jì)遺傳算予；步驟六, 確定運(yùn)行參數(shù). 第五章 基于遺傳算法的關(guān)聯(lián)規(guī)則挖掘模型目前已有的針對(duì)關(guān)聯(lián)規(guī)則發(fā)掘的算法主要是r.agrawal等提出的apriori算法, 該算法將對(duì)關(guān)聯(lián)規(guī)則的發(fā)現(xiàn)分作兩個(gè)步驟：先識(shí)別所有的頻繁項(xiàng)目集, 再?gòu)闹袠?gòu)造信任度大于預(yù)先設(shè)定值的規(guī)則. 整個(gè)發(fā)掘過程最核心的問題便是識(shí)別頻繁項(xiàng)目集, 這是一個(gè)全局搜索過程, 遺傳算法在這一方面的應(yīng)用恰好能夠利用其作為全局優(yōu)化算法的優(yōu)勢(shì)以避免得到局部最優(yōu)的結(jié)果. 除此之外, 遺傳算法可針對(duì)具體問題選取合適的編碼方式、適應(yīng)度函數(shù), 還能夠校正遺傳算子以避免進(jìn)化過程中可能出現(xiàn)的一些問題. 如此看來, 遺傳算法很適合用于關(guān)聯(lián)規(guī)則挖掘, 這樣的“量身定制”更體現(xiàn)了數(shù)據(jù)挖掘的個(gè)性化特征. 為此, 我們提出基于遺傳算法的關(guān)聯(lián)規(guī)則挖掘模型, 下面簡(jiǎn)述其工作過程. 首先, 問題信息通過預(yù)處理器編碼為有限長(zhǎng)的消息, 同時(shí)為每個(gè)屬性創(chuàng)建映射表, 其次, 用sql查詢器依據(jù)屬性（字段）在數(shù)據(jù)庫(kù)中查詢以生成臨時(shí)消息表, 再由屬性映射表將其離散化之后得消息表, 然后用遺傳算法得到滿足條件的種群并將解輸出到優(yōu)化器, 最后經(jīng)優(yōu)化器提取以生成關(guān)聯(lián)規(guī)則返回給用戶. 其中, 預(yù)處理器將信息分為條件部分和結(jié)論部分, 消息表則