基于遺傳算法的樸素貝葉斯分類研究摘要分類是數(shù)據(jù)挖掘領(lǐng)域中重要的研究分支，國內(nèi)外己經(jīng)取得了許多令人矚目的成就。樸素貝葉斯分類器由于計算高效、精確度高，并具有堅實的理論基礎(chǔ)而得到廣泛的應(yīng)用。然而，樸素貝葉斯分類器的條件獨立性假設(shè)限制了對實際數(shù)據(jù)的應(yīng)用。遺傳算法是模擬生物在自然環(huán)境中的遺傳和進(jìn)化過程而形成的一種自適應(yīng)全局優(yōu)化概率搜索算法，具有簡單、通用、穩(wěn)健等特性，使其在復(fù)雜實際問題的求解中顯示出巨大的優(yōu)越性，而且能在概率意義下收斂到問題的全局最優(yōu)解。本文基于遺傳算法，對樸素貝葉斯分類問題進(jìn)行研究，主要工作如下1概述數(shù)據(jù)挖掘的研究背景，數(shù)據(jù)挖掘的主要任務(wù)，描述了數(shù)據(jù)挖掘中分類問題的定義、方法以及分類模型評價的標(biāo)準(zhǔn)等。2描述了樸素貝葉斯分類模型，樸素貝葉斯分類模型的一般原理，以及存在的問題。3闡述了遺傳算法的基本思想，并描述了遺傳算法的一種改進(jìn)算法即自適應(yīng)遺傳算法。4將遺傳算法引入到樸素貝葉斯分類研究中，提出一種基于遺傳算法的樸素貝葉斯分類算法GNBC，該算法為避免數(shù)據(jù)預(yù)處理時，訓(xùn)練集的噪音及數(shù)據(jù)規(guī)模過大使屬性約簡的效果不太理想，并進(jìn)而影響分類效果的問題，在訓(xùn)練集上通過隨機(jī)屬性選取生成若干屬性子集，并以這些子集構(gòu)建相應(yīng)的樸素貝葉斯分類器，進(jìn)而采用遺傳算法進(jìn)行優(yōu)選。實驗表明了該算法的有效性。關(guān)鍵詞數(shù)據(jù)挖掘，分類，樸素貝葉斯，遺傳算法THERESEARCHOFNAIVEBAYESIANCLASSIFICATIONBASEDONGENETICALGORITHMSABSTRACTTHECLASSIFICATIONISANIMPORTANTRESEARCHBRANCHINTHEDATAMININGDOMAINITHASOBTAINEDMANYAMAZINGACHIEVEMENTSOWINGTOITSHIGMYEFFICIENTANDHI曲LYPRECISECALCULATIONASWELLASITSSTRICTTHEORETICALFOUNDATION，NAIVEBAYESIANCLASSIFIERHASOBTAINEDWIDESPREADAPPLICATIONHOWEVER,ITSCONDITIONINDEPENDENCEASSUMPTIONLIMITSITSREALAPPLICATIONTHEGENETICALGORITHMSAREONEKINDOFAUTOADAPTEDGLOBALOPTIMIZATIONPROBABILITYSEARCHALGORITHMSWHICHFORMTHROUGHSIMULATINGTHEHEREDITYANDEVOLUTIONPROCESSOFTHEBIOLOGYINTHENATURALENVIRONMENTITSSIMPLE，ALLPURPOSE，STEADYCHARACTERHASMADEGREATACHIEVEMENTSINTHESOLUTIONTODIFFICULT，COMPLEXPROBLEMS，ANDCANCONVERGENCETOTHEGLOBALMINIMUMBASEDONTHEGENETICALGORITHMS，NAIVEBAYESIANCLASSIFICATIONMETHODWASSTUDIEDINTHISDISSERTATIONTHEMALNWORKWEREASFOLLOWSFIRST，THERESEARCHBACKGROUNDANDTHEPRIMARYMISSIONOFDATAMININGWEREOUTLINED，ANDTHEDEFINITIONTHEMETHODASWELLASTHECLASSIFICATIONMODELAPPRAISALSTANDARDOFTHECLASSIFICATIONQUESTIONINTHEDATAMININGDOMAINWEREDESCRIBEDSECOND，THENAIVEBAYESIANCLASSIFICATIONMODEL，THEGENERALPRINCIPLEOFTHEMODEL，ASWELLASSOMEEXISTINGQUESTIONSWASDESCRIBEDTHIRD，THEBASICIDEASOFTHEGENETICALGORITHMSWEREELABORATED，ANDONEKINDOFIMPROVEMENTGENETICALGORITHMSNAMELYAUTOADAPTEDGENETICALGORITHMSWASDESCRIBEDLAST，BYINTRODUCINGTHEGENETICALGORITHMSTOTHENAIVEBAYESIANCLASSIFICATIONRESEARCH，ANAIVEBAYESIANCLASSIFICATIONALGORITHMBASEDONGENETICALGORITHMSGNBCFORSHORTLWASPROPOSEDINTHISARTICLEINORDERTOAVOIDTHEEFFECTOFTHETRAININGSETSNOISEANDTHEDATASCALECAUSINGTHEINFLUENCEOFFEATUREREDUCTIONNOTTOBETOOAPPROXIMATELYIDEAL，ANDTHENEFFECTINGTHECLASSIFICATIONINFLUENCE，THISALGORITHMGENERATESCERTAINATTRIBUTESUBSETSOFTHETRAININGSETSTHROUGHTHERANDOMATTRIBUTESELECTION，ANDCONSTRUCTSTHECORRESPONDINGNAIVEBAYESIANCLASSIFIERS，ANDTHENOPTIMIZESTHEBAYESIANCLASSIFIERSBYUSINGGENETICALGORITHMSTHEEXPERIMENTSATTHEENDOFTHISDISSERTATIONCONFIRMEDTHEVALIDITYOFTHISALGORITINNKEYWORDSDAMMINING，CLASSIFICATION,NAIVEBAYESIANCLASSIFIER,GENETICALGORITHMS插圖清單數(shù)據(jù)挖掘過程2一個簡單的貝葉斯信念網(wǎng)絡(luò)16基本遺傳算法的流程圖26系統(tǒng)功能結(jié)構(gòu)圖37系統(tǒng)主界面39數(shù)據(jù)管理40運(yùn)行界面41參數(shù)設(shè)置41單步執(zhí)行42最優(yōu)染色體42實驗結(jié)果顯示43分類精度柱形圖比較43OOO234567812345IIII圖酊雕酊臥臥郾郾郾郾郾臥表格清單表21條件概率表16表41G_NBC算法與NBC算法分類精度比較36表42響應(yīng)時間表38獨創(chuàng)性聲明本人聲明所呈交的學(xué)位論文是本人在導(dǎo)師指導(dǎo)下進(jìn)行的研究工作及取得的研究成果。據(jù)我所知，除了文中特別加以標(biāo)注和致謝的地方外，論文中不包含其他人已經(jīng)發(fā)表或撰寫過的研究成果，也不包含為獲得盒膽些盍堂或其他教育機(jī)構(gòu)的學(xué)位或證書而使用過的材料。與我一同工作的同志對本研究所做的任何貢獻(xiàn)均已在論文中作了明確的說明并表示謝意。學(xué)位論文作者簽名、昌村再磷、簽字日期誦年填產(chǎn)日學(xué)位論文版權(quán)使用授權(quán)書本學(xué)位論文作者完全了解金蟹王些盔堂有關(guān)保留、使用學(xué)位論文的規(guī)定，有權(quán)保留并向國家有關(guān)部門或機(jī)構(gòu)送交論文的復(fù)印件和磁盤，允許論文被查閱和借閱。本人授權(quán)僉膽王些太堂可以將學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫進(jìn)行檢索，可以采用影印、縮印或掃描等復(fù)制手段保存、匯編學(xué)位論文。保密的學(xué)位論文在解密后適用本授權(quán)書學(xué)位論文作者簽名吒悄善叫簽字日期弧年J月，蛔新徘習(xí)輔可簽字眺咖占細(xì)L學(xué)位論文作者畢業(yè)后去向工作單位鼬串受警屯通訊地蟣苦同璽F之計可機(jī)專電話吻PFJ嘣郵編易力口7致謝首先，衷心感謝我的導(dǎo)師胡學(xué)鋼教授。在論文的寫作過程中，導(dǎo)師胡學(xué)鋼教授給予了我悉心的指導(dǎo)。胡老師從開始的選題到研究方法，他都給予我耐心的指導(dǎo)和反復(fù)的啟發(fā)，在我做課題遇到困難的時候，胡老師通過親切的聊天給我指明了繼續(xù)的方向和正確的研究方法。胡老師同時又是一個非常細(xì)心的人，論文中多處的修改和對細(xì)微處的嚴(yán)謹(jǐn)?shù)囊?，不僅僅是對我課題的幫助，這些教誨會給我未來的工作和學(xué)習(xí)產(chǎn)生很大的影響，讓我受益終生。此外，在我研究生的學(xué)習(xí)期間中，王浩副院長、吳共慶老師以及給研究生課程班上過課的老師都給予了我有益的指導(dǎo)和幫助，使我學(xué)到了許多知識，受益匪淺。在此衷心的感謝各位老師另外，還要感謝好友海深及我的同事，在我讀書期間對我工作上的幫助，使我能夠集中精力完成我的學(xué)業(yè)。同時，還要感謝徐勇、胡春玲等人工智能和數(shù)據(jù)挖掘?qū)嶒炇业耐瑢W(xué)，感謝他們對我的幫助最后要感謝我的愛人程轉(zhuǎn)流對我始終如一的支持，讓我可以安心完成自己的學(xué)業(yè)。再次感謝所有關(guān)心和支持我的老師、同事、朋友、同學(xué)和家人，謹(jǐn)以此文作為獻(xiàn)給他們的禮物作者胡為成2006年5月第一章緒論隨著信息技術(shù)的快速發(fā)展和信息搜集能力的目益提高，產(chǎn)生了海量的數(shù)據(jù)。這些海量的數(shù)據(jù)或是以靜態(tài)的形式存儲在企業(yè)的物理存儲器上，或是不被存儲而瞬時出現(xiàn)的動態(tài)數(shù)據(jù)。面對如此豐富的海量數(shù)據(jù)，傳統(tǒng)的數(shù)據(jù)處理方法和能力己遠(yuǎn)遠(yuǎn)不能滿足實際的需求。面對日趨激烈的市場競爭，人們需要從這些蘊(yùn)含著豐富決策信息的數(shù)據(jù)中抽取能幫助領(lǐng)導(dǎo)進(jìn)行決策的知識。在需求的強(qiáng)烈驅(qū)動下，數(shù)據(jù)挖掘技術(shù)應(yīng)運(yùn)而生。本章概述了數(shù)據(jù)挖掘的概念和研究現(xiàn)狀，重點介紹了其中的分類問題。此外還給出了本文的內(nèi)容組織。11數(shù)據(jù)挖掘11。1數(shù)據(jù)挖掘定義及研究背景進(jìn)入九十年代，伴隨著因特網(wǎng)INTERNET的出現(xiàn)和發(fā)展，將整個世界聯(lián)成一個小小的地球村，人們可以跨越時空地在網(wǎng)上交換數(shù)據(jù)信息和協(xié)同工作。這樣，展現(xiàn)在人們面前的己不是局限于本部門，本單位和本行業(yè)的龐大數(shù)據(jù)庫。而是浩瀚無垠的信息海洋，數(shù)據(jù)洪水正向人們滾滾涌來。激增的數(shù)據(jù)背后隱藏著許多重要的信息，人們希望能夠?qū)ζ溥M(jìn)行更高層次的分析，以便更好地利用這些數(shù)據(jù)。目前的數(shù)據(jù)庫系統(tǒng)可以高效地實現(xiàn)數(shù)據(jù)的錄入、查詢、統(tǒng)計等功能，但無法發(fā)現(xiàn)數(shù)據(jù)中存在的關(guān)系和規(guī)則，無法根據(jù)現(xiàn)有的數(shù)據(jù)預(yù)測未來的發(fā)展趨勢。缺乏挖掘數(shù)據(jù)背后隱藏的知識的手段，導(dǎo)致了“數(shù)據(jù)爆炸但知識貧乏”的現(xiàn)象。于是，一個新的挑戰(zhàn)被提了出來在這被稱之為信息爆炸的時代，信息過量幾乎成為人人需要面對的問題。如何才能不被信息的汪洋大海所淹沒，從中及時發(fā)現(xiàn)有用的知識，提高信息利用率昵要想使數(shù)據(jù)真正成為一個公司的資源，只有充分利用它為公司自身的業(yè)務(wù)決策和戰(zhàn)略發(fā)展服務(wù)才行，否則大量的數(shù)據(jù)可能成為包袱，甚至成為垃圾。因此，面對“人們被數(shù)據(jù)淹沒，人們卻饑餓于知識”的挑戰(zhàn)，從數(shù)據(jù)庫中發(fā)現(xiàn)知識KNOWLEDGEDISCOVERYINDATABASES，KDD及其核心技術(shù)一一數(shù)據(jù)挖掘DATAMINING，DM便應(yīng)運(yùn)而生，并得以蓬勃發(fā)展，越來越顯示出其強(qiáng)大的生命力。數(shù)據(jù)挖掘DM就是從大量的、不完全的、有噪聲的、模糊的、隨機(jī)的實際應(yīng)用數(shù)據(jù)中，提取隱含在其中的、人們事先不知道的、但又是潛在有用的信息和知識的過程”。其流程圖如圖卜1所示。這個定義包括以下四個層次的含義1數(shù)據(jù)源必須是真實的、大量的、含噪聲的2發(fā)現(xiàn)的是用戶感興趣的知識3發(fā)現(xiàn)的知識要可接受、可理解、可運(yùn)用，最好能用自然語言表達(dá)發(fā)現(xiàn)結(jié)果；4并不是要求發(fā)現(xiàn)放之四海皆準(zhǔn)的知識，也不是要去發(fā)現(xiàn)嶄新的自然科學(xué)定理和純數(shù)學(xué)公式，更不是什么機(jī)器定理證明，所有發(fā)現(xiàn)的知識都是相對的，是有特定前提和約束條件、面向特定領(lǐng)域的。預(yù)112數(shù)據(jù)挖掘的研究現(xiàn)狀圖11數(shù)據(jù)挖掘過程從數(shù)據(jù)庫中發(fā)現(xiàn)知識KDD一詞首次出現(xiàn)在1989年舉行的第十一屆國際聯(lián)合人工智能學(xué)術(shù)會議上。到目前為止，由美國人工智能協(xié)會主辦的KDD國際研討會已經(jīng)召開了8次，規(guī)模由原來的專題討論會發(fā)展到國際學(xué)術(shù)大會，研究重點也逐漸從發(fā)現(xiàn)方法轉(zhuǎn)向系統(tǒng)應(yīng)用，注重多種發(fā)現(xiàn)策略和技術(shù)的集成，以及多種學(xué)科之間的相互滲透。到了1995年，在美國計算機(jī)年會ACM上，提出了數(shù)據(jù)挖掘的概念，即通過從數(shù)據(jù)庫中抽取隱含的、未知的、具有潛在使用價值信息的過程。數(shù)據(jù)挖掘是KDD過程中最為關(guān)鍵的步驟。1997年亞太地區(qū)在新加坡組織了第一次規(guī)模較大的PAKDD學(xué)術(shù)研討會，以后每年召開一次。IEEE的GNOWLEDGEANGDATAENGINEERING會刊率先在1993年出版了KDD技術(shù)?？l(fā)表的5篇論文代表了當(dāng)時KDD研究的最新成果和動態(tài)。隨后，各類KDD會議、研討會紛紛涌現(xiàn)，許多領(lǐng)域的國際會議也將KDD列為專題討論。1999年，IEEE和ACM再次推出KDD專刊，介紹數(shù)據(jù)挖掘在各個領(lǐng)域的應(yīng)用成果。此外，并行計算、計算機(jī)網(wǎng)絡(luò)和信息工程等其他領(lǐng)域的國際學(xué)會、學(xué)千U也把數(shù)據(jù)挖掘和知識發(fā)現(xiàn)列為專題和?？懻摗Ｗ罱珿ARTNERGROUP的一次高級技術(shù)調(diào)查將數(shù)據(jù)挖掘和人工智能列為“未來三到五年內(nèi)將對工業(yè)產(chǎn)生深遠(yuǎn)影響的五大關(guān)鍵技術(shù)”之首，并且還將并行處理體系和數(shù)據(jù)挖掘列為未來五年內(nèi)投資焦點的十大新興技術(shù)前兩位。根據(jù)最近GARTL3EF的HPC研究表明，“隨著數(shù)據(jù)捕獲、傳輸和存儲技術(shù)的快速發(fā)展，大型系統(tǒng)用戶將更多地需要采用新技術(shù)來挖掘市場以外的價值，采用更為廣闊的并行處理系統(tǒng)來創(chuàng)建新的商業(yè)增長點?！蹦壳?，國外數(shù)據(jù)挖掘的發(fā)展趨勢及其研究方面主要有對知識發(fā)現(xiàn)方法的研究迸一步發(fā)展，如近年來注重對遺傳算法的研究；傳統(tǒng)的統(tǒng)計學(xué)回歸法在DM中的應(yīng)用DM與數(shù)據(jù)庫的緊密結(jié)合等等。在應(yīng)用方一面包括DM商業(yè)軟件工具不斷產(chǎn)生和完善，注重建立解決問題的整體系統(tǒng)，而不是孤立的過程。用戶主要集中在大型銀行、保險公司、電信公司和銷售業(yè)。國外很多計算機(jī)公司非常重視數(shù)據(jù)挖掘的開發(fā)應(yīng)用，IBM和微軟都成立了相應(yīng)的研究中心進(jìn)行這方面的工作。許多著名的計算機(jī)公司開始開發(fā)嘗試著DM軟件的開發(fā)，比較典型的如SAS公司的EILTERPRISEMIHER，IBM公司的INTELLIGENTMINER，SGI公司的SETMINET，SPSS公司的CLEMENTINE，還有KNOWLEDGEDISCOVERYWORKBENCH，DBMINET，QUEST等。WEB數(shù)據(jù)挖掘產(chǎn)品有NETPERCERPTIOIIS，ACCRUEINSIGHT和ACCRUEHITLIST，COMMERCETREND、等。與國外相比，國內(nèi)對KDD的研究稍晚，目前進(jìn)行的大多數(shù)研究項目是由政府資助進(jìn)行的，如國家自然科學(xué)基金、863計劃、“九五”計劃等。1993年國家自然科學(xué)基金開始對數(shù)據(jù)挖掘研究進(jìn)行支持。1999年4月在北京召開的第三屆亞太地區(qū)KDD國際會議PAKDD99響應(yīng)熱烈，收到論文158篇，國內(nèi)從事數(shù)據(jù)挖掘研究的人員主要集中在大學(xué)，也有部分在研究所或公司。所涉及的研究領(lǐng)域很多，一般集中于學(xué)習(xí)算法的研究、數(shù)據(jù)挖掘的實際應(yīng)用以及有關(guān)數(shù)據(jù)挖掘理論方面的研究。如北京系統(tǒng)工程研究所對模糊方法在數(shù)據(jù)挖掘中的應(yīng)用研究、北京大學(xué)對數(shù)據(jù)立方體的研究、華中理工大學(xué)、復(fù)旦大學(xué)、浙江大學(xué)等對關(guān)聯(lián)規(guī)則的研究等。但到目前為止，國內(nèi)還沒有比較成熟的數(shù)據(jù)挖掘產(chǎn)品。當(dāng)前，DM研究正方興未艾，預(yù)計今后還會形成更大的高潮，研究焦點可能會集中到以下幾個方面數(shù)據(jù)挖掘語言的標(biāo)準(zhǔn)化；不完全和不精確的數(shù)據(jù)的處理標(biāo)記數(shù)據(jù)，計算機(jī)處理，存儲數(shù)據(jù)庫，創(chuàng)建數(shù)據(jù)倉庫，數(shù)據(jù)清潔，解決不確定性，格式化數(shù)據(jù)；數(shù)據(jù)挖掘過程的可視化，使得知識發(fā)現(xiàn)的過程能夠被用戶理解，也便于在數(shù)據(jù)挖掘過程中的人機(jī)交互；研究在網(wǎng)絡(luò)環(huán)境下的數(shù)據(jù)挖掘技術(shù)，特別是在INTERNET上建立DM服務(wù)器，與數(shù)據(jù)庫服務(wù)器配合，實現(xiàn)數(shù)據(jù)挖掘；加強(qiáng)對各種非結(jié)構(gòu)化數(shù)據(jù)的挖掘，如文本數(shù)據(jù)、圖形圖像數(shù)據(jù)、多媒體數(shù)據(jù)數(shù)據(jù)挖掘算法的交叉性研究。數(shù)據(jù)挖掘技術(shù)的應(yīng)用首先是滿足信息時代用戶的急需。因此，研制開發(fā)大量基于數(shù)據(jù)挖掘的決策支持軟件工具產(chǎn)品將是首要的任務(wù)。113數(shù)據(jù)挖掘與知識發(fā)現(xiàn)談到數(shù)據(jù)挖掘必須提到數(shù)據(jù)庫中的知識發(fā)現(xiàn)KDDKNOWLEDGEDISCOVERYINDATABASES。關(guān)于KDD與DATAMINING的關(guān)系，有以下幾種不同的看法。1KDD是數(shù)據(jù)挖掘的一個特例既然數(shù)據(jù)挖掘系統(tǒng)可以在關(guān)系數(shù)據(jù)庫、事務(wù)數(shù)據(jù)庫、數(shù)據(jù)倉庫、空間數(shù)據(jù)庫SPATIALDATABASE、文本數(shù)據(jù)TEXTDATA以及諸如WEB等多種數(shù)據(jù)組織形式中挖掘知識，那么數(shù)據(jù)庫中的知識發(fā)現(xiàn)只是數(shù)據(jù)挖掘的一個方面，這是早期比較流行的觀點，在許多文獻(xiàn)可以看到這種說法“，因此從這個意義說，數(shù)據(jù)挖掘就是從數(shù)據(jù)庫、數(shù)據(jù)倉庫以及其它數(shù)據(jù)存儲方式中挖掘有用知識的過程，這種描述強(qiáng)調(diào)了數(shù)據(jù)挖掘在源數(shù)據(jù)形式上的多樣性。2數(shù)據(jù)挖掘是KDD過程的一個步驟例如，在I996年的知識發(fā)現(xiàn)國際會議上，許多學(xué)者建議對這兩個名詞加以區(qū)分”1，核心思想是KDD是從數(shù)據(jù)庫中發(fā)現(xiàn)知識的全部過程，而DATADINING則是此全部過程的一個特定的關(guān)鍵步驟。這種觀點有它的合理性。雖然我們可以從數(shù)據(jù)倉庫、WEB等源數(shù)據(jù)中挖掘知識，但是這些數(shù)據(jù)源都是和數(shù)據(jù)庫技術(shù)相關(guān)的，數(shù)據(jù)倉庫是由源數(shù)據(jù)庫集成而來的，即使是像WEB這樣的數(shù)據(jù)源，恐怕也離不開數(shù)據(jù)庫技術(shù)來組織和存儲抽取的信息。因此，KDD是一個更廣義的范疇，它包括數(shù)據(jù)清洗、數(shù)據(jù)集成、數(shù)據(jù)選擇、數(shù)據(jù)轉(zhuǎn)換、數(shù)據(jù)挖掘、模式生成及評估等一系列步驟，這樣我們可以把KDD看作是一些基本功能構(gòu)件的系統(tǒng)化協(xié)同工作系統(tǒng)，而數(shù)據(jù)挖掘則是這個系統(tǒng)中的一個關(guān)鍵的部分。源數(shù)據(jù)經(jīng)過清洗和轉(zhuǎn)換等成為適合于挖掘的數(shù)據(jù)集，數(shù)據(jù)挖掘在這種具有固定形式的數(shù)據(jù)集上完成知識的提煉，最后以合適的知識模式用于進(jìn)一步分析決策工作。從這種狹義的觀點上我們可以定義數(shù)據(jù)挖掘是從特定形式的數(shù)據(jù)集中提煉知識的過程。數(shù)據(jù)挖掘作為KDD的一個重要步驟看待，可以使我們更容易聚焦研究，重點有效解決問題。目前人們在數(shù)據(jù)挖掘算法的研究上基本屬于這樣的范疇。3KDD與DATAMINING含義相同有些人認(rèn)為，KDD與DATAMINING只是叫法不一樣，它們的含義基本相同。事實上，在現(xiàn)今的文獻(xiàn)中，許多場合，如技術(shù)綜述等，這兩個術(shù)語仍然不加區(qū)分地使用著。也有人說，KDD在人工智能界很流行，DATAMINING在數(shù)據(jù)庫界使用的更多。所以從廣義的觀點，數(shù)據(jù)挖掘是從大型數(shù)據(jù)集可能是不完全的、有噪聲的、不確定性的、各種存儲形式的中挖掘隱含在其中的、人們事先不知道的、對決策有用的知識的過程。從上面的描述中可以看出，數(shù)據(jù)挖掘概念可以在不同的技術(shù)層面上來理解，但是其核心仍然是從數(shù)據(jù)中挖掘知識，所以有人說口Q知識挖掘更合適“1。4114數(shù)據(jù)挖掘的任務(wù)數(shù)據(jù)挖掘的任務(wù)主要有關(guān)聯(lián)分析、聚類分析、分類、預(yù)測、時序模式和偏差分析等。一、關(guān)聯(lián)分析ASSOCIATI013ANAIYSIS兩個或兩個以H數(shù)據(jù)項的取值之間存在某種規(guī)律性，就稱為關(guān)聯(lián)?？梢越⑵疬@些數(shù)據(jù)項的關(guān)聯(lián)規(guī)則”3。數(shù)據(jù)關(guān)聯(lián)是數(shù)據(jù)庫中存在的一類重要的、可被發(fā)現(xiàn)的知識，它反映一個事件和其他事件之間依賴或關(guān)聯(lián)。如果兩項或多項屬性之間存在關(guān)聯(lián)，那么其中一項的屬性值就可以依據(jù)其他屬性值進(jìn)行預(yù)測。例如，買面包的顧客中90還買牛奶，這就是一條關(guān)聯(lián)規(guī)則。在商場中將這兩樣物品擺放在一起銷售，將會提高銷售量。在大型數(shù)據(jù)庫中，這樣的關(guān)聯(lián)規(guī)則可以產(chǎn)生很多，這就需要進(jìn)行篩選。一般用“支持度”和“可信度”兩個閥值來淘汰那些無用的關(guān)聯(lián)規(guī)則。二、聚類分析CIUSTERING聚類是把數(shù)據(jù)按照它們的相似性歸納成若干類別，同一類別中的數(shù)據(jù)距離較小、彼此相似，不同類別中的數(shù)據(jù)距離偏大、彼此相異陋1聚類分析可以建立宏觀的概念，發(fā)現(xiàn)數(shù)據(jù)的分布模式，以及可能的數(shù)據(jù)屬性之間的相互關(guān)系。聚類方法包括統(tǒng)計分析方法、機(jī)器學(xué)習(xí)方法和神經(jīng)網(wǎng)絡(luò)方法等。在統(tǒng)計分析方法中，聚類分析是基于距離的聚類。這種聚類分析方法是一種基于全局比較的聚類，它需要考察所有的個體才能決定類的劃分。在機(jī)器學(xué)習(xí)方法中，聚類是無導(dǎo)師的學(xué)習(xí)。此時距離是跟據(jù)概念的描述來確定的，又稱為概念聚類。當(dāng)聚類對象動態(tài)增加時，概念聚類則稱為概念形成。在神經(jīng)網(wǎng)絡(luò)中，自組織神經(jīng)網(wǎng)絡(luò)方法用于聚類。如ART模型、KOHONEN模型等，這是一種無監(jiān)督學(xué)習(xí)方法。當(dāng)給定距離閥值后，各樣本按閥值進(jìn)行聚類。三、分類C1ASSIFICATION分類是數(shù)據(jù)挖掘中應(yīng)用得最多得任務(wù)。分類就是找出一個類別的概念描述，并用這種描述來構(gòu)造模型一般用規(guī)則或決策樹模式表示。類別的概念描述代表著這類數(shù)據(jù)的整體信息，也就是該類的內(nèi)涵描述”3。類的內(nèi)涵描述分為特征描述和辨別性描述。特征描述是對類中對象的共同特征的描述。辨別性描述是對兩個或多個類之間的區(qū)別的描述。分類的過程是分析輸入數(shù)據(jù)，通過在訓(xùn)練集中的數(shù)據(jù)所表現(xiàn)出來的特性，經(jīng)過有關(guān)算法，為每一個類找到一種準(zhǔn)確的描述或者模型，并使用這種類的描述對未來的測試數(shù)據(jù)進(jìn)行分類。四、預(yù)測PREDICATION預(yù)測是利用歷史數(shù)據(jù)找出變化規(guī)律，建立模型，并由此模型對未來數(shù)據(jù)的種類及特征進(jìn)行預(yù)測哺1。典型的預(yù)測方法是回歸分析，即和用大量的歷史數(shù)據(jù)，以時間為變量建立線性或非線性回歸方程。預(yù)測時，只要輸入任意的時間值，通過回歸方程就可求出該時間的狀態(tài)。近年來，發(fā)展起來的神經(jīng)網(wǎng)絡(luò)方法如BP模型，實現(xiàn)了非線性樣本的學(xué)習(xí)，能進(jìn)行非線性函數(shù)的判別。分類也能進(jìn)行預(yù)測，但分類一般用于離散數(shù)值回歸預(yù)測用于連續(xù)數(shù)值；神經(jīng)網(wǎng)絡(luò)方法預(yù)測既可以用于連續(xù)數(shù)值，也可以用于離散數(shù)值。五、時序模式TIFILESERIESPATTERN時序模式是指通過時間序列搜索出的重復(fù)發(fā)生概率較高的模式“。與回歸一樣，它也是用己知的數(shù)據(jù)預(yù)測未來的值，但這些數(shù)據(jù)的區(qū)別是變量所處時問的不同。在時序模式中，需要找出在某個最小時間內(nèi)出現(xiàn)比率一直高于某一最小百分比最小支持度閥值的規(guī)則。這些規(guī)則會隨著形勢的變化作適當(dāng)?shù)恼{(diào)整。時序模式中，一個有重要影響的方法是“相似時序”。用“相似時序”的方法，要按時間順序查看時間事件數(shù)據(jù)庫，從中找出另一個或多個相似的時序事件。六、偏差分析DEVIATION數(shù)據(jù)庫中的數(shù)據(jù)存在很多異常情況，發(fā)現(xiàn)數(shù)據(jù)庫中數(shù)據(jù)存在的異常情況是菲常重要的。偏差包括很多潛在的知識，如分類中的反常實例、不滿足規(guī)則的特例、觀測結(jié)果與模型預(yù)測值的偏差、量值隨時間的變化等。偏差檢測的基本方法是，尋找觀測結(jié)果與參照值之間有意義的差別。2數(shù)據(jù)挖掘中的分類闖題121分類的定義分類就是根據(jù)數(shù)據(jù)集的特點找出類別的概念描述，這個概念描述代表了這類數(shù)據(jù)的整體信息，也就是該類的內(nèi)涵描述。“”1。分類的目的是分析輸入數(shù)據(jù)，通過在訓(xùn)練集中的數(shù)據(jù)所表現(xiàn)出來的特性，為每一個類找到一種準(zhǔn)確的描述或者模型。這種描述常常用謂詞表示。并使用這種類的描述對未來的測試數(shù)據(jù)進(jìn)行分類。盡管這些未來的測試數(shù)據(jù)的類標(biāo)簽是未知的，我們?nèi)钥梢杂纱祟A(yù)測這些新數(shù)據(jù)所屬的類。分類可描述為給定一訓(xùn)練數(shù)據(jù)的集合T簡稱為訓(xùn)練集或訓(xùn)練數(shù)據(jù)庫，T中的元素一一記錄由若干個屬性描述。在所有屬性中有且僅有一個屬性作為類別屬性。屬性集合用矢量XX。，X。，X。表示，其中X。1ISN對應(yīng)各非類別屬性，可以具有不同的值域，即對于任一屬性XIX，X，X。T，MI隨屬性的不同而變化。當(dāng)一屬性的值域為連續(xù)值域時，該屬性稱為連續(xù)屬性NUMERICALHTTRIBUTE，否則稱為離散屬性DISCRETEATTRIBUTE；用C表示類別屬性，CC1，C2CK，即數(shù)據(jù)集有K個不同的類別。那么，T就隱含地確定了一個從矢量X到類別屬性C的映射函數(shù)HFX一C，分類的目的就是采用某種方法模型將該隱含函數(shù)H表示出來。122幾種主要的分類模型分類技術(shù)是很多領(lǐng)域，比如統(tǒng)計、模式識別、人工智能、神經(jīng)網(wǎng)絡(luò)等領(lǐng)域的研究課題。本節(jié)介紹了一些分類算法和知識模型。一、決策樹決策樹方法，在許多的機(jī)器學(xué)習(xí)書或論文中可以找到，這類方法的詳細(xì)介紹ID3算法是最典型的決策樹分類算法，之后的改進(jìn)算法包括ID4，IDS，C4“，C50等。這些算法都是從機(jī)器學(xué)習(xí)角度研究和發(fā)展起來的，對于大訓(xùn)練樣本集很難適應(yīng)。這是決策樹應(yīng)用向數(shù)據(jù)挖掘方向發(fā)展必須面對和解決的關(guān)鍵問題。在這方面的嘗試也很多。比較有代表性的研究有AGRAWAL等人提出的LIQ“，SPRINT算法“，它們強(qiáng)調(diào)了決策樹對大訓(xùn)練集的適應(yīng)性。1998年，IICHALSKI等對決策樹與數(shù)據(jù)挖掘的結(jié)合方法和應(yīng)用進(jìn)行了歸納“”，另一個比較著名的研究是GEHRKE等人提出了一個稱為雨林RAINFOREST的在大型數(shù)據(jù)集中構(gòu)建決策樹的挖掘構(gòu)架“，并在1999年提出這個模型的改進(jìn)算法BOAT“”，另外的些研究，集中在針對數(shù)據(jù)挖掘特點所進(jìn)行的高效決策樹、裁減決策樹中規(guī)則的提取技術(shù)與算法等方面。二、貝葉斯分類貝葉斯分類BAYESIANCLASSIFICATION來源于概率統(tǒng)計學(xué)，并且在機(jī)器學(xué)習(xí)中被很好地研究。近幾年，作為數(shù)據(jù)挖掘的重要方法倍受矚目。樸素貝葉斯分類NAIVEBAYESIANCLASSIFICATION具有堅實的理論基礎(chǔ)，和其它分類方法比，理論上具有較小的出錯率。但是，由于受其對應(yīng)用假設(shè)的準(zhǔn)確性設(shè)定的限制，因此需要在提高和驗證它的適應(yīng)性等方面迸步工作。JONE提出連續(xù)屬性值的內(nèi)核稠密估計的樸素貝葉斯分類方法N“，提高了基于普遍使用的高斯估計的準(zhǔn)確性，DOMINGOS等對于類條件獨立性假設(shè)應(yīng)用假設(shè)不成立時樸素貝葉斯分類的適應(yīng)性迸行了分析“”，貝葉斯信念網(wǎng)絡(luò)BAYESIANBELIEFNETWORK是基于貝葉斯分類技術(shù)的學(xué)習(xí)框架，集中在貝葉斯信念網(wǎng)絡(luò)本身架構(gòu)，以及它的推理算法研究上，其中，比較有代表性的工作有RUSSELL的布爾變量簡單信念網(wǎng)、訓(xùn)練貝葉斯信念網(wǎng)絡(luò)的梯度下降法“、BUNTINE等建立的訓(xùn)練信念網(wǎng)絡(luò)的基本操作”以及LAURITZEN等的具有蘊(yùn)藏數(shù)據(jù)學(xué)習(xí)的信念網(wǎng)絡(luò)及其推理算法、EM2。3等。三、神經(jīng)網(wǎng)絡(luò)分類神經(jīng)網(wǎng)絡(luò)作為一個相對獨立的研究分支己經(jīng)很一早被提出，有許多著作和文獻(xiàn)詳細(xì)介紹了它的原理。由于神經(jīng)網(wǎng)絡(luò)需要較長的訓(xùn)練時間和其可解釋性較差，為它的應(yīng)用帶來了困難。但是，由于神經(jīng)網(wǎng)絡(luò)具有高度的抗干擾能力和可以對未訓(xùn)練數(shù)據(jù)進(jìn)行分類等優(yōu)點，又使得它具有極大的誘惑力。因此，在數(shù)據(jù)挖掘中使用神經(jīng)網(wǎng)絡(luò)技術(shù)是一件有意義但仍需要艱苦探索的工作。在神經(jīng)網(wǎng)絡(luò)和數(shù)據(jù)挖掘技術(shù)的結(jié)合方面，一些利用神經(jīng)網(wǎng)絡(luò)挖掘知識的算法被提出，例如LU和SETION。等提出的數(shù)據(jù)庫中提取規(guī)則的方法”，WIDRO等系統(tǒng)介紹了神經(jīng)網(wǎng)絡(luò)在商業(yè)等方面的應(yīng)用技術(shù)?！?。四、類比學(xué)習(xí)和案例學(xué)習(xí)最典型的類比學(xué)習(xí)ANALOGYLEARNING方法是K最臨近分類KNEARESTNEIGHBORCLASSIFICATION方法，它屬于懶散學(xué)習(xí)法，相比決策樹等急切學(xué)習(xí)法，具有訓(xùn)練時間短，但分類時間長的特點。K最臨近方法可以用于分類和聚類中，基于案例的學(xué)習(xí)CASEBASEDLEARNING方法可以應(yīng)用到數(shù)據(jù)挖掘的分類中?；诎咐龑W(xué)習(xí)的分類技術(shù)的基本思想是，當(dāng)對一個新案例進(jìn)行分類時，通過檢查己有的訓(xùn)練案例找出相同的或最接近的案例，然后根據(jù)這些案例提出這個新案例的可能解。利用案例學(xué)習(xí)來進(jìn)行數(shù)據(jù)挖掘的分類必須要解決案例的相似度、度量訓(xùn)練案例的選取以及利用相似案例生成新案例的組合解等關(guān)鍵問題，并且它們也正是目前研究的主要問題。五、其它方法如粗糙集和模糊集FUZZYSET方法等。另外需要強(qiáng)調(diào)的是，任何一種分類技術(shù)與算法都不是萬能的，不同的商業(yè)問題需要用不同的方法去解決。即使對于同一個商業(yè)問題可能有多種分類算法。分類的效果一般和數(shù)據(jù)的特點有關(guān)。有些數(shù)據(jù)噪聲大、有缺值、分布稀疏，有些屬性是離散的，而有些是連續(xù)值的，所以目前普遍認(rèn)為不存在某種方法能適合于所有特點的數(shù)據(jù)。因此，對于一個特定問題和一類特定數(shù)據(jù)，需要評估具體算法的適應(yīng)性。123分類模型的評價我們一般從以下幾個方面對分類模型的性能進(jìn)行評價1預(yù)測準(zhǔn)確度預(yù)測準(zhǔn)確度是分類器的一個重要度量，分類器是已知數(shù)據(jù)集的描述模型，也可用于對目標(biāo)數(shù)據(jù)進(jìn)行預(yù)測。預(yù)測準(zhǔn)確度可以評價一個分類器對于預(yù)測將來數(shù)據(jù)的準(zhǔn)確度，是用得最多的一種比較尺度，特別是對于預(yù)測型分類任務(wù)，評價分類器的預(yù)測準(zhǔn)確度有兩種常用的方法保持HOLDOUT和K一次交叉驗證KFOLDCROSSVALIDATION，還有其他的方法也可用于評價分類器的準(zhǔn)確度，如BOOTSTRAPPING，LEAVEONEOUT等等。2計算復(fù)雜度計算復(fù)雜度依賴于算法的實現(xiàn)細(xì)節(jié)與機(jī)器的硬件環(huán)境。在數(shù)據(jù)挖掘中，目標(biāo)數(shù)據(jù)大多是大型數(shù)據(jù)庫，數(shù)據(jù)規(guī)模也越來越大。因此，時空性能將是非常重要的一個因素。3模型描述的簡潔度與可解釋性對于描述型的分類任務(wù)，模型描述越簡潔越受歡迎，因為分類器是通過特定算法挖掘出的模式，這些模式最終是面向特定領(lǐng)域用戶的，所以挖掘出的模式要易于理解，便于用戶進(jìn)行決策。4健壯性健壯性是衡量分類器優(yōu)劣的一個方面，也是分類器抗干擾能力的度量。現(xiàn)實生活中的數(shù)據(jù)總會存在噪音數(shù)據(jù)，而對存在噪音數(shù)據(jù)的數(shù)據(jù)集，能否得出好的分類器以及給出正確的預(yù)測類別，這一點也很重要。5可伸縮性目前大部分的分類算法是基于數(shù)據(jù)規(guī)模很小的假定。算法的可伸縮性意味著當(dāng)給定大數(shù)據(jù)量能否有效的構(gòu)造模型?？傊?，分類的效果一般與應(yīng)用領(lǐng)域背景以及數(shù)據(jù)的特點有關(guān)。目前，還沒有發(fā)現(xiàn)一種對于所有的數(shù)據(jù)集都最優(yōu)的方法。也就是說，不存在某種方法能適用任何應(yīng)用，適合各種特點的數(shù)據(jù)。13本文的內(nèi)容組織本文由五章組成第一章主要簡述數(shù)據(jù)挖掘產(chǎn)生的原因以及研究背景，描述了數(shù)據(jù)挖掘的概念及其與KDD的關(guān)系，介紹了數(shù)據(jù)挖掘的主要任務(wù)；詳細(xì)闡述了數(shù)據(jù)挖掘中分類問題的定義、方法以及分類模型評價的標(biāo)準(zhǔn)等。最后簡要給出了文章的組織結(jié)構(gòu)。第二章對貝葉斯分類技術(shù)的原理和方法作了全面的介紹首先給出了貝葉斯分類的原理，即貝葉斯定理，貝葉斯定理是貝葉斯分類技術(shù)的理論基礎(chǔ)，所有的貝葉斯分類模型都是基于貝葉斯定理的。接著重點討論了樸素貝葉斯分類模型，給出了樸素貝葉斯分類模型的一般原理，并在此基礎(chǔ)上的一系列改進(jìn)；最后，簡要介紹了貝葉斯信念網(wǎng)絡(luò)。第三章詳細(xì)介紹了遺傳算法的基本思想，重點討論實現(xiàn)遺傳算法所涉及的幾個主要因素參數(shù)的編碼，選擇、交叉、變異等遺傳操作，適應(yīng)度函數(shù)的設(shè)計進(jìn)一步介紹基本遺傳算法的表示和過程，最后簡要介紹遺傳算法的一種改進(jìn)自適應(yīng)遺傳算法。第四章給出了本文的核心內(nèi)容。在對前面理論總結(jié)研究的基礎(chǔ)上，將遺傳算法和貝葉斯分類兩種軟計算方法相結(jié)合，提出了一種基于遺傳算法的樸素貝葉斯分類方法GNGC。然后選擇UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫提供的典型數(shù)據(jù)庫實例，通過實驗對GNBC算法和NBC算法進(jìn)行了比較。第五章對已有的工作進(jìn)行總結(jié)，并對下一步的工作進(jìn)行了展望。9第二章貝葉斯理論與貝葉斯分類模型貝葉斯分類器是建立在經(jīng)典的貝葉斯概率理論的基礎(chǔ)上的基于統(tǒng)計方法的分類模型“2”。本章主要討論貝葉斯分類的基本原理和幾種常見的貝葉斯分類模型。21貝葉斯分類器的一般原理貝葉斯學(xué)派是現(xiàn)代統(tǒng)計學(xué)中與經(jīng)典頻率學(xué)派并列的兩大學(xué)派之一，貝葉斯數(shù)據(jù)分析就是先驗分布在經(jīng)過數(shù)據(jù)提供的證據(jù)修訂之后所形成的后驗分布。TOMASBAYES在1763年提出了后來以他名字命名的貝葉斯理論在具體行動之前，無論決策是如何制定的，在結(jié)果的證據(jù)收集并確認(rèn)后，決策是可以改變的。211貝葉斯理論經(jīng)典的頻率統(tǒng)計學(xué)派對具有不確定性的未知參數(shù)。的推斷直接利用樣本信息，而與具體的應(yīng)用領(lǐng)域無關(guān)。因此，認(rèn)為總體研究對象的全體X的概率分布一一概率密度或概率分布率FX0中的未知參數(shù)0是一個確定的數(shù)，完全由樣本集決定。與經(jīng)典統(tǒng)計學(xué)的客觀概率不同，貝葉斯概率是觀測者對某一事件的發(fā)生的相信程度。貝葉斯理論認(rèn)為0除了與樣本信息相關(guān)外，還與來自于非樣本信息的先驗信息相關(guān)。先驗信息一半來自包含類似0的過去的經(jīng)驗，先驗信息具有一定的主觀性。因此FX0變?yōu)闂l件分布，記為FXL0。貝葉斯理論正式地將先驗信息納入統(tǒng)計學(xué)并利用這種主觀信息進(jìn)行推斷。212貝葉斯定理設(shè)試驗E的樣本空間為Q，A、B為Q的事件，事件A發(fā)生的概率記為PA，事件B發(fā)生的概率記為PB，事件A事件B同時發(fā)生的概率記為PAB，在A己經(jīng)發(fā)生的條件下，B發(fā)生的概率稱為A發(fā)生的條件下事件B發(fā)生的條件概率，記為P剛篙21無論事件A、B是否是相互獨立的事件，下式顯然成立PABPBPALBPAPBJA稱為概率乘法定理22假設(shè)B。，BB。是樣本空間Q的一個劃分，即滿足1BI兩兩互斥，B。BJ中IJ；2BIQI1，2，N則PAPANQPANB；PAB。PABPBTPA1B，稱為全概率公式23在式23中PB，是由以前的分析得到的，因此稱為先驗概率，而PALBI是根據(jù)新得到的信息B，的信息重新加以修正的概率，因此成為后驗概率。條件概率PAFB說明事件B發(fā)生時事件A的概率。相反的問題就是計算逆概率，即當(dāng)事件A發(fā)生時，事件B發(fā)生的概率。根據(jù)乘法定理和全概率公式郴川，籌警勰稱為貝葉斯公式24相互獨立的隨機(jī)事件是一系列這樣的事件其中任何一次事件發(fā)生的概率，都與此前各事件的結(jié)果無關(guān)。因此，對于獨立隨機(jī)事件，借助已經(jīng)發(fā)生事件的結(jié)果來推測后來事件的概率是不可能的。因此假如事件A、B是相互獨立的事件，貝有PABPA25所以對于獨立事件PABPAFBPBPAPB262。1。3極大后驗假設(shè)與極大似然假設(shè)在許多學(xué)習(xí)任務(wù)中，需要考慮候選假設(shè)集合H并在其中尋找給定的數(shù)據(jù)D時可能性最大的假設(shè)HH。任何這樣具有最大可能性的假設(shè)被稱為極大后驗假設(shè)MAXILLLL1TLLAPOSTERIORI，MAP，記為HMPARGMAXPHDA增MAXPDHPOARGMAXPDI尸廳27由于PD是不依賴于H的常量，所以在最后一步去掉了PD。上式就是一個原始的分類模型。貝葉斯分類就是根據(jù)上述MAP假設(shè)找出新實例最可能的分類。所有對貝葉斯分類模型的研究工作都是以此假設(shè)為前提的。在某些情況下，可假定H中每個假設(shè)有相同的先驗概率即對H中任意的H。和H。，PH，PH，。這時可把27式進(jìn)一步簡化，只考慮PDLH來尋找極大可能假設(shè)。PDH常被稱為給定H時數(shù)據(jù)D的似然度1IKELIHOOD，任何使PDIH最大的假設(shè)稱為極大似然假設(shè)MAXIMUMLIKELIHOOD，ML記為H_LHML5ARGMAXPDH28在分類過程中，28式常被用來在啟發(fā)式搜索時進(jìn)行模型檢測。22樸素貝葉斯分類模型221樸素貝葉斯分類原理樸素貝葉斯分類器假定特征向量的各分量間相對于決策變量是相對獨立的，并使用概率規(guī)則來實現(xiàn)學(xué)習(xí)或某種推理過程，即將學(xué)習(xí)或推理的結(jié)果表示為隨機(jī)變量的概率分布，這可以解釋為對不同可能性的信任程度。它的理論基礎(chǔ)就是貝時斯定理和貝葉斯假設(shè)“2“。樸素貝葉斯分類器將每個訓(xùn)練樣本數(shù)據(jù)分解成一個N維特征向量X和決策類別變量C，并假定特征向量的各分量間相對于決策變量是相對獨立的。設(shè)特征向量XX，ON，X表示數(shù)據(jù)I“1個屬性H。，A。，A。的具體取值，類別變量C有M個不同的取值C。，C。，C，即有M個不同的類別。則PXJOP扎X2，洳IGNPJO1KM291J由貝葉斯定理知X屬于C。的后驗概率為反CKXPXICKPCOPX1KM210樸素貝葉斯分類器將未知類別的決策變量X歸屬于類別C。當(dāng)且僅當(dāng)PCKIXPCJJZ對于1，M，T即PQIX最大。由于PX對于所有類別均是相同的，因此NPCKIZ芘PXJCOPCECXFIPX，ICKLKM211T1由于類別的事前概率是未知的，因此，可以假設(shè)各類別出現(xiàn)的概率相同，即PC1PC2PC塒。這樣求公式211的最大轉(zhuǎn)換為求PXIG最大，否則就要求PXLCKPC,O得最大?？梢酝ㄟ^訓(xùn)練樣本數(shù)據(jù)集合估計PCO和PGIIT，1KMPCO腓S212PXIIGSKI船。213其中，為訓(xùn)練樣本數(shù)據(jù)集合中類別為C。的樣本個數(shù)，S為整個訓(xùn)練樣本數(shù)據(jù)集合的容量。S。為訓(xùn)練樣本數(shù)據(jù)集合中類別為Q且屬性4的取值為X，的樣本個數(shù)。樸素貝葉斯分類模型的優(yōu)點是1算法邏輯簡單，易于實現(xiàn)2算法實施的時間空間開銷小；3算法性能穩(wěn)定，對于不同特點的數(shù)據(jù)其分類性能差別不大，即模型的健壯性比較好。222樸素貝葉斯分類模型的不足樸素貝葉斯分類模型中的類條件獨立性假設(shè)是它的先天不足所在，獨立性假設(shè)在許多實際問題中并不成立，如果在這些問題中忽視這一點，會引起分類的誤差。為了克服這一不足，已有許多相關(guān)文獻(xiàn)對樸素貝葉斯分類算法作了一些改進(jìn)，主要是放寬條件獨立性的限制。下面將就這些改進(jìn)方法作一簡單的介紹，并提出一種我們自己的改進(jìn)方法。2。2。3樸素貝葉斯分類模型的改進(jìn)一、從屬性變量間的關(guān)系來改進(jìn)樸素貝葉斯分類器樸素貝葉斯分類器關(guān)于變量獨立性的假設(shè)雖然大大減少了參數(shù)量，但在現(xiàn)實生活中，這種獨立性假設(shè)經(jīng)常是不滿足的。經(jīng)過分析得知，樸素貝葉斯分類器的本質(zhì)是一種具有很強(qiáng)限制條件的貝葉斯網(wǎng)絡(luò)分類器，但是它限制條件太強(qiáng)，不適于現(xiàn)實應(yīng)用；然而，完全無限制的貝葉斯網(wǎng)絡(luò)也是不現(xiàn)實的，因為學(xué)習(xí)這樣的網(wǎng)絡(luò)非常耗時，其時間復(fù)雜度為屬性變量的指數(shù)級，并且空間復(fù)雜度也很高。因此，可以從屬性變量間的關(guān)系來改進(jìn)樸素貝葉斯分類器，研究具有較寬松條件限制的貝葉斯網(wǎng)絡(luò)分類器。1屬性分組適用于屬性可以分為獨立的子集合的情況。KONONERKO提出一種采用窮盡搜索的屬性分組技術(shù)”“，假定同一組內(nèi)的屬性之間可能是相互依賴的，但組與組之間是滿足獨立性假設(shè)的屬性集合。也就是說，獨立性假設(shè)弱化為這些屬性組之間的獨立性。但是，這種算法的復(fù)雜性要遠(yuǎn)遠(yuǎn)高于樸素貝葉斯分類器，而且在現(xiàn)實世界中，屬性可以完全被分成獨立的子集合只是少數(shù)情況。2屬性刪除技術(shù)適用于存在冗余屬性的情況。LANGLEY和SAGE提出了一種基于屬性刪除的選擇性貝葉斯分類器O。當(dāng)存在一些屬性依賴于其他屬性，特別是存在冗余屬性時，屬性刪除方法確實能夠改善樸素貝葉斯分類器的預(yù)測精確度。3局部樸素貝葉期分類器適用于屬性之間相互依賴的情形比較復(fù)雜的情況。這種方法是為屬性變量的每一種取值或某個范圍建立一個樸素貝葉斯分類器。也就是說，單一的全局樸素貝葉斯分類器被許多局部樸素貝葉斯分類器所代替，將屬性獨立性假設(shè)放寬到只要局部屬性獨立就可以了。KOHAVI將樸素貝葉斯分類器和決策樹相結(jié)合O“，用一棵決策樹來分割實例空間，在每個葉子結(jié)點上建立局部樸素貝葉斯分類器。ZHENG和WEBB等利用懶惰式學(xué)習(xí)策略提出了一種懶惰式貝葉斯規(guī)則LAZYBAYESIANRULE，LBR學(xué)習(xí)技術(shù)O”該方法將懶惰式技術(shù)應(yīng)用到局部樸素貝葉斯規(guī)則的歸納中。該算法雖然較大地提高了分類精確度，但是效率很低。為了提高LBR的效率，WANG和WEBB給出了一種啟發(fā)式LBR算法BLBRO“，可以有效地提高學(xué)習(xí)效率。LBR和HLBR是目前該方向上的最新研究成果之一。4通過屬性約簡改善屬性間的依賴性運(yùn)用粗糙集合理論可以對條件屬性集進(jìn)行約簡處理而不改變分類質(zhì)量，然后結(jié)合信息嫡理論可以計算出約簡后的屬性依賴度，從而可以選擇一個近似獨立的約簡后的屬性集。這樣，既可以滿足樸素貝葉斯分類的類條件獨立的基本要求，又可以通過約簡降低特征維數(shù)，縮減求解問題的規(guī)?！?。二、利用遺傳算法對多個樸素貝葉斯分類器進(jìn)行優(yōu)選我們提出一種基于遺傳算法的樸素貝葉斯方法，該方法為避免數(shù)據(jù)預(yù)處理時，訓(xùn)練集的噪音及數(shù)據(jù)規(guī)模使屬性約簡的效果不太理想，并進(jìn)而影響分類效果，在訓(xùn)練集上通過隨機(jī)屬性選取生成若干屬性子集，并以這些子集構(gòu)建相應(yīng)的樸素貝葉斯分類器，然后結(jié)合遺傳算法，將這些樸素貝葉斯分類器作為初始種群，設(shè)立適應(yīng)度函數(shù)，采用遺傳算子進(jìn)行優(yōu)選，這樣最后一代的最優(yōu)秀個體即是要求的分類器。具體方法的介紹將在第四章給出。22，4樸素貝葉斯分類器的提升提升方法“”BOOSTING總的思想是學(xué)習(xí)一系列分類器，在這個序列中每一個分類器對它前一個分類器導(dǎo)致的錯誤分類例子給予更大的重視。尤其是，在學(xué)習(xí)完分類器H“之后，增加了H。導(dǎo)致分類錯誤的訓(xùn)練例子的權(quán)值，并且通過重新對訓(xùn)練例子計算權(quán)值，再學(xué)習(xí)下一個分類器H。這個過程重復(fù)T次。最終的分類器從這一系列的分類器中綜合得出。在這個過程中，每個訓(xùn)練例子被賦予一個相應(yīng)的權(quán)值，如果一個訓(xùn)練例子被分類器錯誤分類，那么就相應(yīng)增加該例子的權(quán)重，使得在下一次的學(xué)習(xí)中，分類器對該例代表的情況更加重視。對多類分類問題的提升方法如下INPUTN個訓(xùn)練實例N個訓(xùn)練實例上分布DW，W為訓(xùn)練實例的權(quán)向量。T為訓(xùn)練重復(fù)的趟數(shù)。1INITIALIZE2初始化訓(xùn)練實例的權(quán)向量。W一1N，I1，N3FORT1TOT4給定權(quán)值W得到一個假設(shè)HX一Y5估計假設(shè)日01，靜總體誤差，PW吖弘矗JX，6計算盧“K百817計算下一輪樣本的權(quán)值W；“1W。地”8正規(guī)化彬”，使其總和為19ENDFOR10OUTPUTY11廳算ARGMAX109去砌。石J，TLP這里，O1，如果中T；否則，中0。上述提升樸素貝葉斯分類器的時間復(fù)雜度是0TNF，其中F是每個樣本的屬性的個數(shù)。在一般情況下，提升后的分類性能有了較大的提高。但是，這種提升方法也存在以下的不足不能捕捉屬性間的相關(guān)性，也就是說沒有突破條件獨立性假設(shè)的限制。當(dāng)訓(xùn)練集中存在噪音數(shù)據(jù)時，提升方法會把噪音數(shù)據(jù)當(dāng)成有用的信息通過權(quán)值而放大，從而降低提升的性能。23貝葉斯信念網(wǎng)絡(luò)樸素貝葉斯分類假定條件獨立，即給定樣木的類標(biāo)號，屬性的值相互條件獨立。這一假定簡化了計算。當(dāng)假定成立時，與其他所有分類算法相比，樸素貝葉斯分類是最精確的。然而，在實踐中，變量之間的依賴可能存在。貝葉斯信念網(wǎng)絡(luò)BAYESIALLBELIEFNETWORK說明鏈和條件概率分布。它允許在變量的子集間定義類條件獨立性。它提供一種因果關(guān)系的圖形，可以在其上進(jìn)行學(xué)習(xí)。這種網(wǎng)絡(luò)也被稱作信念網(wǎng)絡(luò)、貝葉顛網(wǎng)絡(luò)和概率網(wǎng)絡(luò)。為簡潔計，我們稱它為信念網(wǎng)絡(luò)。貝葉斯信念網(wǎng)絡(luò)由RHOWARD和JMATHESON于1981年提出，它是一種概率推理方法，它能從不完全、不精確和不確定的知識和信息中做出推理，可以處理不完整和帶有噪音的數(shù)據(jù)集，從而解決了數(shù)據(jù)間不一致甚至相互獨立的問題。其堅實的理論基礎(chǔ)、知識結(jié)構(gòu)的自然表述方式、靈活的推理能力、方便的決策機(jī)制使其應(yīng)用越來越廣泛。貝葉斯信念網(wǎng)絡(luò)將不確定事件以網(wǎng)絡(luò)的形式連結(jié)起來，實現(xiàn)對某一與其它事件有關(guān)的時間的預(yù)測。與傳統(tǒng)的不確定信息模型相比，貝葉斯信念網(wǎng)絡(luò)建立在嚴(yán)格的統(tǒng)計理論的基礎(chǔ)上，因此具有堅實的理論基礎(chǔ)。信念網(wǎng)絡(luò)由兩部分定義。第一部分是有向無環(huán)圖，其每個節(jié)點代表一個隨機(jī)變量，而每條弧F代表一個概率依賴。如果一條弧由節(jié)點Y到Z，則Y是Z的雙親或直接前驅(qū)，而Z是Y的后繼。給定其雙親，每個變量條件獨立于圖中的非后繼。變量可以是離散的或連續(xù)值的。它們可以對應(yīng)于數(shù)據(jù)中給定的實際屬性，或?qū)?yīng)于一個相信形成聯(lián)系的“隱藏變量”如影響學(xué)生的身體健康的綜合因素。圖31給出了一個6個布爾變量的簡單信念網(wǎng)絡(luò)。弧表示因果關(guān)系。例如，得肺病的學(xué)生受家族肺病史的影響，也受其是否吸煙的影響。此外，該弧還表明給定其雙親FAMILYHISTORY和SMOKER，變量LUNGCANCER條件獨立于EMPHYSEMA。這意味，一旦FAMILYHISTORY和SMOKER的值己知，變量EMPHYSEMA并不提供關(guān)于LUNGCANCER的附加信息。定義信念網(wǎng)絡(luò)的第二部分使每個屬性一個條件概率表CPT。變量Z的CPT說明條件分布PZIPARENTSZ，其中PARENTSZ是Z的雙親。表31給出了LUNGCANCER的CPT。圖21一個簡單的貝葉斯信念網(wǎng)絡(luò)表21條件概率表RESU|TFH，SFH，SFHSFHSLCO805O701LC02050309對于其雙親值的每個可能組合，表中給出了LUNGCANCER的每個值的條件概率。例如，有左上角和右下角，我們分別看到PHUNGCANCER“NO”IFAMILYHISTORY“NO”，SMOKER“NO”O(jiān)9對應(yīng)屬性或變量ZL，ZN的聯(lián)合概率由