【文章內(nèi)容簡介】 temational Conference on Knowledge Discovery and Data Mining，簡稱 KDD 會議。 KDD 會議的規(guī)模由原來的專題討論會發(fā)展到國際學(xué)術(shù)大會。研究重點也逐漸從發(fā)現(xiàn)方法轉(zhuǎn)向系統(tǒng)應(yīng)用。并且注重多種發(fā)現(xiàn)策略和技術(shù)的集成，以及多種學(xué)科之問的相互滲透。 國外的研究重點從發(fā)現(xiàn)方法逐漸向系統(tǒng)應(yīng)用直到專享大規(guī)模的綜合系統(tǒng)開發(fā)，并且注重多種發(fā)現(xiàn)策略和技術(shù)的集成。 國內(nèi)研究和發(fā)展現(xiàn)狀 與國外相比．國內(nèi)對 DMKD 的研究稍晚，沒有形成整體力量。 1993 年國家自然科學(xué)基金首次支持中科院合 肥分院對該領(lǐng)域的研究項目。目前從事數(shù)據(jù)挖掘研究的人員主要在大學(xué)，也有部分在研究所或公司。研究領(lǐng)域一般集中于學(xué)習(xí)算法的研究、數(shù)據(jù)挖掘的實際應(yīng)用以及有關(guān)數(shù)據(jù)挖掘理論方面的研究。國內(nèi)的許多科研單位和高等院校也競相開展知識發(fā)現(xiàn)的基礎(chǔ)理論及其應(yīng)用研究。 指導(dǎo)思想 本設(shè)計主要采用數(shù)據(jù)挖掘技術(shù) 對畢業(yè)生就業(yè)情況進行預(yù)測。整個設(shè)計關(guān)鍵在于貝葉斯定理的分類算法實現(xiàn)。 該設(shè)計方案主要采用數(shù)據(jù)挖掘技術(shù)，通過對往屆畢業(yè)生就業(yè)數(shù)據(jù)的導(dǎo)入，對其進行統(tǒng)計分析，應(yīng)用貝葉斯定理建立預(yù)測模型，并應(yīng)用該模型對未來即將就業(yè)的畢業(yè)生的就業(yè)趨勢進行 預(yù)測?？梢灶A(yù)測到他們的就業(yè)情況和就業(yè)的概率。 數(shù)據(jù)挖掘技術(shù) 數(shù)據(jù)挖掘技術(shù)的產(chǎn)生背景 隨著信息技術(shù) 的高速發(fā)展，人們積累的數(shù)據(jù)量急劇增長，如何從海量的數(shù)據(jù)中提取有用的知識成為當(dāng)務(wù)之急 。數(shù)據(jù)挖掘 就是為順應(yīng)這種需要應(yīng)運而生發(fā)展起來的數(shù)據(jù)處理技術(shù)。其主要任務(wù)是關(guān)聯(lián)分析、分類、預(yù)測時序模式和偏差分析等。是知識發(fā)現(xiàn)(knowledge discovery in database)的關(guān)鍵步驟。 數(shù)據(jù)挖掘技術(shù)是人們長期對數(shù)據(jù)庫技術(shù)進行研究和開發(fā)的結(jié)果。起初 各種商業(yè)數(shù)據(jù) 是存儲在計算機的數(shù)據(jù)庫中的，然后發(fā)展到 可 以 對數(shù)據(jù)庫進行查詢和 訪問 ，進而發(fā)展到對數(shù)據(jù)庫的即時遍歷。數(shù)據(jù)挖掘使數(shù)據(jù)庫技術(shù)進入了一個更高級的階段，它不僅能對過去的數(shù)據(jù)進行查詢和遍歷，并且能夠找出過去數(shù)據(jù)之間的潛在聯(lián)系，從而促進信息的傳遞。 計算機信息工程學(xué)院畢業(yè)設(shè)計說明書 3 數(shù)據(jù)挖掘技術(shù)的 定義及含義 數(shù)據(jù)挖掘 （ Data Mining） 就是從大量的、不完全的、有噪聲的、模糊的、隨機的實際應(yīng)用數(shù)據(jù)中，提取隱含在其中的、人們事先不知道的、但又是潛在有用的信息和知識的過程。 從廣義上 講 ，數(shù)據(jù)、信息也是知識的表現(xiàn)形式，但是人們更把概念、規(guī)則、模式、規(guī)律和約束等看作知識。人們把數(shù)據(jù)看作是形 成知識的源泉 ，不斷地挖掘。原始數(shù)據(jù)可以是結(jié)構(gòu)化的，如關(guān)系數(shù)據(jù)庫中的數(shù)據(jù)；也可以是半結(jié)構(gòu)化的，如文本、圖形 和圖像數(shù)據(jù) ；甚至是分布在網(wǎng)絡(luò)上的異構(gòu)型數(shù)據(jù)。發(fā)現(xiàn)知識的方法可以是數(shù)學(xué)的，也可以是非數(shù)學(xué)的；可以是演繹的，也可以是歸納的。發(fā)現(xiàn)的知識可以被用于信息管理，查詢優(yōu)化，決策支持和過程控制等，還可以用于數(shù)據(jù)自身的維護。因此，數(shù)據(jù)挖掘是一門交叉學(xué)科，它把人們對數(shù)據(jù)的應(yīng)用從低層次的簡單查詢，提升到從數(shù)據(jù)中挖掘知識，提供決策支持。在這種需求牽引下，匯聚了不同領(lǐng)域的研究者，尤其是數(shù)據(jù)庫技術(shù)、人工智能技術(shù) 、數(shù)理統(tǒng)計、可視化 技術(shù)、并行計算等方面的學(xué)者和 工程技術(shù)人員 ，投身到數(shù)據(jù)挖掘這一新興的研究領(lǐng)域，形成新的技術(shù)熱點。 數(shù)據(jù)挖掘 也 是一種新的商業(yè)信息處理技術(shù)，其主要特點是對商業(yè)數(shù)據(jù)庫中的大量業(yè)務(wù)數(shù)據(jù)進行抽取、轉(zhuǎn)換、分析和其他模型化處理，從中提取輔助商業(yè)決策的關(guān)鍵性數(shù)據(jù)。簡而言之，數(shù)據(jù)挖掘其實是一類深層次的數(shù)據(jù)分析方法。商業(yè)領(lǐng)域產(chǎn)生了大量的業(yè)務(wù)數(shù)據(jù)，這些數(shù)據(jù)不再是為了分析的目的而收集的，而是由于純機會的（ Opportunistic） 商業(yè)運作而產(chǎn)生。分析這些數(shù)據(jù)也不再是單純?yōu)榱搜芯康男枰?，更主要是為商業(yè)決策提供真正有價值的信息，進而獲 得利潤。但所有企業(yè)面臨的一個共同問題是： 企業(yè)數(shù)據(jù) 量非常大，而其中真正有價值的信息卻很少，因此從大量的數(shù)據(jù)中經(jīng)過深層分析，獲得有利于商業(yè)運作、提高競爭力的信息，就像從礦石中淘金一樣，數(shù)據(jù)挖掘也因此而得名。 貝葉斯分類算法 貝葉斯算法的介紹 貝葉斯分類算法是統(tǒng)計學(xué)的一種分類方法，它是一類利用概率統(tǒng)計知識進行分類的算法。在許多場合，樸素貝葉斯 (Naive Bayes， NB)分類算法可以與決策樹和神經(jīng)網(wǎng)絡(luò)分類算法相媲美，該算法能運用到大型數(shù)據(jù)庫中，而且方法簡單、分類準確率高、速度快。 由于貝葉斯定 理假設(shè)一個屬性值對給定類的影響?yīng)毩⒂谄渌鼘傩缘闹?，而此假設(shè)在實際情況中經(jīng)常是不成立的，因此其分類準確率可能會下降。為此，就衍生出許多降低獨立性假設(shè)的貝葉斯分類算法，如 TAN(tree augmented Bayes work)算法。 貝葉斯定理 計算機信息工程學(xué)院畢業(yè)設(shè)計說明書 4 貝葉斯定理 （ Bayes39。 theorem）是概率論中的一個結(jié)論，它跟隨機變量的條件概率以及邊緣概率分布有關(guān)。在有些關(guān)于概率的解說中，貝葉斯定理能夠告知我們?nèi)绾卫眯伦C據(jù)修改已有的看法。 通常，事件 A 在事件 B（發(fā)生）的條件下的概率，與事件 B 在事件 A的 條件下的概率是不一樣的；然而，這兩者是有確定的關(guān)系，貝葉斯定理就是這種關(guān)系的陳述。貝葉斯公式的用途在于通過己知三個概率函數(shù)推出第四個。它的內(nèi)容是 :在 B 出現(xiàn)的前提下 ,A出現(xiàn)的概率等于 A出現(xiàn)的前提下 B 出現(xiàn)的概率乘以 A出現(xiàn)的概率再除以 B 出現(xiàn)的概率。通過聯(lián)系 A 與 B,計算從一個事件產(chǎn)生另一事件的概率 ,即從結(jié)果上溯原。 作為一個普遍的原理，貝葉斯定理對于所有概率的解釋是有效的；然而，頻率主義者和貝葉斯主義者對于在應(yīng)用中，某個隨機事件的概率該如何被賦值，有著不同的看法： 頻率主義者根據(jù)隨機事件發(fā)生的頻率，或者總體樣本里面 的發(fā)生的個數(shù)來賦值概率；貝葉斯主義者則根據(jù)未知的命題來賦值概率。這樣的理念導(dǎo)致貝葉斯主義者有更多的機會使用貝葉斯定理。 貝葉斯定理是關(guān)于隨機事件 A 和 B 的條件概率（或邊緣概率）的一則定理。 () 其中 P(A|B)是在 B 發(fā)生的情況下 A 發(fā)生的可能性。 在貝葉斯定理中，每個名詞都有約定俗成的名稱： (1)P(A)是 A 的 先驗概率 或 邊緣概率 。之所以稱為 先驗 是因為它不考慮任何 B 方面的因素。 (2)P(A|B)是已知 B發(fā)生后 A 的 條件概率 ，也由于得自 B 的取值而被稱作 A 的后驗概率。 (3)P(B|A)是已知 A發(fā) 生后 B 的 條件概率 ，也由于得自 A 的取值而被稱作 B 的后驗概率。 (4)P(B)是 B 的 先驗概率 或 邊緣概率 ，也作 標(biāo)準化常量 （ normalizing constant） 。 按這些術(shù)語， Bayes 定理可表述為： 后驗概率 = (相似度 *先驗概率 )/標(biāo)準化常量 。 也就是說，后驗概率與先驗概率和相似度的乘積成正比。 另外，比例 P(B|A)/P(B)也有時被稱作標(biāo)準相似度（ standardised likelihood），Bayes 定理可表述為： 后驗概率 = 標(biāo)準相似度 *先驗概率 。 樸素貝葉斯分類的原理與流程 樸素貝葉斯分類 法 是一種十分簡單的分類算法，樸素貝葉斯分類 名字緣由 是因為)( )()|()|( BP APABPBAP ?計算機信息工程學(xué)院畢業(yè)設(shè)計說明書 5 這種方法的思想很樸素，樸素貝葉斯的思想基礎(chǔ)是這樣的：對于給出的待分類項，求解在此項出現(xiàn)的條件下各個類別出現(xiàn)的概率，哪個 概率 最大，就認為此待分類項屬于哪個類別。通俗說，就好比這么個道理，你在街上看到一個黑人， 我們不能確切說他是從哪里來的 ， 但是 你十有八九猜 是 非洲 人 。 主要原因是 黑人中非洲人的比率最高，不能否定黑人 也可能是美洲人或 其他 ，但 是 在沒有其它可用信息下，我們 一定是 會選擇條件概率最大的類別，這就是樸素貝葉斯的思想基礎(chǔ)。 樸素貝葉斯分類 法 的正 式定義如下： 設(shè) ? ?maaax ,... , 21? 為一個待分類項，而每個 a 為 x 的一個特征屬性 。 有類別集合 ?? nyyyC ,.. ., 21? 。 計算 ? ? ? ? ? ?xyPxyPxyP n |,. .. ,|,| 21 。 如果 ? ? ? ? ? ? ? ??? xyPxyPxyPxyP nk |, .. .,|,|m a x| 21? ，則 kyx? 。 現(xiàn)在的關(guān)鍵是計算第 3 步中 各個條件概率 ，就能得出第 4 步的最大值 。 接下來 我們可以這么做： 先要 找到一個已知分類的待分類項集合，這個集合 稱為 訓(xùn)練樣本集 。 然后 統(tǒng)計得到在各類別下各個特征屬性的條件概率估計。即 )|(),|() 。 . .. 。|() , .. .,|(),|()。|() , .. .,|(),|( 212222111211 nnmm yaPyaPyaPyaPyaPyaPyaPyaP。 如果各個特征屬性是條件獨立的，則根據(jù)貝葉斯定理有如下推導(dǎo)： ? ? ? ? ? ?? ?xP yPyxPxyP iii || ? () 因為分母對于所有類別為常數(shù)， 即 我們只要將分子最大化。又因各特征屬性 為 條件獨立的，所以有： ? ??? mj ijiiimiiii yaPyPyPyaPyaPyaPyPyxP 121 )|()()()|()...|()|()()|( () 根據(jù)上述分析，樸素貝葉斯分類的流程可以由下圖 11表示： 確 定 屬 性 特 征獲 取 訓(xùn) 練 樣 本對 每 個 類 別 計 算 p ( y i )對 每 個 特 征 屬 性 計 算所 有 劃 分 的 條 件 概 率對 每 個 類 別 計 算P ( x | y i ) p ( y i )以 P ( x | y i ) p ( y i ) 最大 項 作 為 x 所 屬 類 別 圖 11樸 素貝葉斯分類流程 圖 計算機信息工程學(xué)院畢業(yè)設(shè)計說明書 6 可以看到，整個樸素貝葉斯分類分為三個階段： 第一階段 —— 準備工作階段，這個階段的任務(wù)是為樸素貝葉斯分類做必要的準備，主要工作是根據(jù)具體情況確定特征屬性，并對每個特征屬性進行適當(dāng)劃分，然后由人工對一部分待分類項進行分類，形成訓(xùn)練樣本集合。這一階段的輸入是所有待分類數(shù)據(jù)，輸出是特征屬性和訓(xùn)練樣本。這一階段是整個樸素貝葉斯分類中唯一需要人工完成的階段，其質(zhì)量對整個過程將有重要影響，分類器的質(zhì)量很大程度上由特征屬性、特征屬性劃分及訓(xùn)練樣本質(zhì)量決定。 第二階段 —— 分類器訓(xùn)練階段，這個階段的任務(wù)就是 生成分類器，主要工作是計算每個類別在訓(xùn)練樣本中的出現(xiàn)頻率及每個特征屬性劃分對每個類別的 條件概率 ,并將結(jié)果記錄。其輸入是特征屬性和訓(xùn)練樣本，輸出是分類器。這一階段是機械性階段，根據(jù)前面討論的公式可以由程序自動計算完成。 第三階段 —— 應(yīng)用階段。這個階段的任務(wù)是使用分類器對待分類項進行分類，其輸入是分類器和待分類項，輸出是待分類項與類別的映射關(guān)系。這一階段也是機械性階段，由程序完成。 估計類別下特征屬性劃分的條件概率及 Laplace 校準 我們可以看出 計算各個劃分的條件概率 P(a|y)是樸素貝葉斯分類的關(guān) 鍵性步驟，當(dāng)特征屬性為離散值時，只要很方便的統(tǒng)計訓(xùn)練樣本中各個劃分在每個類別中出現(xiàn)的頻率即可用來估計 P(a|y)，下面重點討論特征屬性是連續(xù)值的情況。 當(dāng)特征屬性為連續(xù)值時，通常假定其值服從高斯分布（也稱正態(tài)分布）。 即： ? ? ? ?2 222 1, ? ??????? ?? ?eg （ ） 而 ? ? ? ?ii yykik agyaP ?? ,| ? 。 因此只要計算出訓(xùn)練樣本中各個類別中此特征項劃分的各均值和標(biāo)準差，代入上述公式即可得到需要的估計值。 另外出現(xiàn) P(a|y)=0 時應(yīng)該怎么處理。 當(dāng)某個類別下某個特征項劃分沒有出現(xiàn)時 ，就 會 產(chǎn)生這種現(xiàn)象， 這種現(xiàn)象 會令分類器質(zhì)量大大降低。為解決這個問題，我們引入Laplace 校準， 其 思想 很 簡單，就是對沒類別下所有劃分的計數(shù)加 1，這樣如果訓(xùn)練樣本集數(shù)量充分大時，并不會對結(jié)果產(chǎn)生影響，并且解決了上述頻率為 0 的尷尬局面 ，問題得到解決。 貝葉斯定理應(yīng)用 貝葉斯定理用于投資決策分析是在已知相關(guān)項目 B 的資料，而缺乏論證項目 A 的直接資料時，通過對 B項目的有關(guān)狀態(tài)及發(fā)生概率分析推導(dǎo) A 項目的狀態(tài)及發(fā)生概率。如果我們用數(shù)學(xué)語言描繪，即當(dāng)已知事件 Bi 的概率 P（ Bi）和事件 Bi 已發(fā)生條件下事計算機信息工程學(xué)院畢業(yè)設(shè)計說明書 7 件 A 的概率 P（ A│Bi ），則可運用貝葉斯定理計算出在事件 A 發(fā)生條件下事件 Bi 的概率 P（ Bi│A ）。 按貝葉斯定理進行投資決策的基本步驟是： （ 1） 列出在已知項目 B 條件下項目 A 的發(fā)生概率，即將 P（ A│B ）轉(zhuǎn)換為 P（ B│A ）； （ 2） 繪制樹型圖； （ 3） 求各狀態(tài)結(jié)點的期望收益值，并將結(jié)果填入樹型圖； （ 4） 根據(jù)對樹型圖的分析，進行投資項目決策； 搜索巨人 Google 和 Autonomy，一家出售信息恢復(fù)工具的公司，都使用了貝葉斯定理（ Bayesian principles）為數(shù)據(jù)搜索提供近似的（但是技術(shù)上不確切）結(jié)果 。研究人員還使用貝葉斯模型來判斷癥狀和疾病之間的相互關(guān)系，創(chuàng)建個人機器人，開