【文章內(nèi)容簡介】 數(shù)據(jù)和缺失數(shù)據(jù) ,易于和其它系統(tǒng)集成。然而 ,作為一種較新的機器學(xué)習(xí)技術(shù) ,用戶在使用這種方法的14 時候需要具備相當?shù)慕⒑瓦\行該系統(tǒng)的工具知識。 5)歸納性邏輯程序 用一級屬性邏輯來定義來描述概念。首先定義正面和負面的例子 ,然后對新例子進行等級劃分。這一方法具有較強的概念描述機制 ,具有以下兩個優(yōu)點 :一是能較好地表達復(fù)雜關(guān)系 。二是較好地體現(xiàn)專業(yè)領(lǐng)域知識 ,因而用該方法得出的模型易于理解。然而 ,和遺傳算法一樣 ,作為一種較新的機器學(xué)習(xí)技術(shù) ,用戶在使用這種方法的時候需要具備相當?shù)慕⒑瓦\行該系統(tǒng)的工具知識 。 其中 ,商業(yè)應(yīng)用最為廣泛的是歸納推理 ,其次是神經(jīng)網(wǎng)絡(luò) ,基于事例的推理 ,基因算法和歸納性邏輯程序。 可視化 可視化就是把數(shù)據(jù)、信息和知識轉(zhuǎn)化成為可視的表示形式的過程?？梢暬?術(shù)為人類與計算機這兩個最強大的信息處理系統(tǒng)之間提供了一個接口 。 使用有效的可視化界面 ,可以快速高效地分析數(shù)據(jù) ,發(fā)現(xiàn)其中隱藏的特征 、 關(guān)系 、 模式和趨勢等 。 根據(jù)是否包括物理數(shù)據(jù) ,可視化技術(shù)粗略地分為兩類 :科學(xué)計算可視化和信息可視化 。 科學(xué)計算可視化顯示的對象涉及標量 、 矢量和張量等不同類別的空間數(shù)據(jù) ,研究的重點放在如何真實 、 快速地顯示三維數(shù)據(jù)場 。 信息可視化則側(cè)重于多維的標量數(shù)據(jù) ,研究的重點放在設(shè)計和選擇合適的顯示方式表示龐大的多維數(shù)據(jù)及其相互之間的關(guān)系 ,以便于用戶了解 。 文本知識挖掘技術(shù)主要定位于信息可視化。可以將信息可 視化看作是從數(shù)據(jù)信息15 到可視化形式再到人的感知系統(tǒng)的可調(diào)節(jié)的映射 。 主要的可視化方法包括 :基于幾何投影技術(shù)的可視化方法 ,基于圖像技術(shù)的可視化方法 ,面向像素的可視化方法和分層技術(shù)的可視化方法。 16 第三章 知識挖掘中常用算法簡介 算法 算法簡介 ,其核心算法是 ID3 算法 。 算法繼承了 ID3 算法的優(yōu)點，并在以下幾方面對 ID3 算法進行了改進： 1) 用信息增益率來選擇屬性，克服了用信息增益選擇屬性時偏向選擇取值的屬性的不足； 2) 在樹構(gòu)造過程中進行剪枝； 3) 能夠完成對連續(xù)屬性的離散化處理； 4) 能夠?qū)Σ煌暾麛?shù)據(jù)進行處理。 算法有如下優(yōu)點：產(chǎn)生的分類規(guī)則易于理解，準確率較高。其缺點是：在構(gòu)造樹的過程中，需要對數(shù)據(jù)集進行多次的順序掃描和排序，因而導(dǎo)致算法的低效。 機器學(xué)習(xí)中，決策樹是一個預(yù)測模型；他代表的是對象屬性與對象值之間的一種映射關(guān)系。樹中每個節(jié)點表示某個對象，而每個分叉路徑則代表的某個可能的屬性值，而每個葉結(jié)點則對應(yīng)從根節(jié)點到該葉節(jié)點所經(jīng)歷的路徑所表示的對象的值。決策樹僅有單一輸出，若欲有復(fù)數(shù)輸出，可以建立獨立的決策樹以處理不同輸出。 從數(shù)據(jù)產(chǎn)生決策樹的機器學(xué)習(xí)技術(shù)叫做決策樹學(xué)習(xí) , 通俗說就17 是決策樹。 決策樹學(xué)習(xí)也是數(shù)據(jù)挖掘中一個普通的方法。在這里，每個決策樹都表述了一種樹型結(jié)構(gòu)，他由他的分支來對該類型的對象依靠屬性進行分類。每個決策樹可以依靠對源數(shù)據(jù)庫的分割進行數(shù)據(jù)測試。這個過程可以遞歸式的對樹進行修剪。 當不能再進行分割或一個單獨的類可以被應(yīng)用于某一分支時，遞歸過程就完成了。另外，隨機森林分類器將許多決策樹結(jié)合起來以提升分類的正確率。 決策樹同時也可以依靠計算條件概率來構(gòu)造。決策樹如果依靠數(shù)學(xué)的計算方法可以取得更加理想的效果。決策樹是如何工作的決策樹一般都是自上而下的來生成的。選擇分割的方法有好幾種，但是目的都是一致的：對目標類嘗試進行最佳的分割。從根到葉子節(jié)點都有一條路徑，這條路徑就是一條 “ 規(guī)則 ” 。決策樹可以是二叉的，也可以是多叉的。 對每個節(jié)點的衡量： 1) 通過該節(jié)點的記錄數(shù) 2) 如果是葉子節(jié)點的話，分類的路徑 3) 對葉子節(jié)點正確分類的比例。 算法原理 首先，說明一下如何計算信息增益率。 熟悉了 ID3 算法后，已經(jīng)知道如何計算信息增益，計算公式如下所示 18 ( ) ( ) ∑ * ?? ?? ( ) ??+ ?? ?? ?? ( ) (*?? ???? ?? ?? (?? ) ??+) （ 31） 或者，用另一個更加直觀容易理解的公式計算： o 按照類標簽對訓(xùn)練數(shù)據(jù)集 D的屬性集 A進行劃分，得到信息熵： ( ) ∑ ( ) （ 32） 按照屬性集 A 中每個屬性進行劃分，得到一組信息熵： (??) ∑ | | ?? (?? ) （ 33） o 計算信息增益 然后計算信息增益，即前者對后者做差，得到屬性集合 A 一組信息增益： ( ) ( ) (??) （ 34） 這樣，信息增益就計算出來了。 o 計算信息增益率 下面看，計算信息增益率的公式，如下所示 IGR(Ex,a)=IG/IV （ 35） 其中， IG 表示信息增益，按照前面我們描述的過程來計算。而IV 是我們現(xiàn)在需要計算的，它是一個用來考慮分裂信息的度量，分裂信息用來衡量屬性分裂數(shù)據(jù)的廣度和均勻程序，計算公式如下所示： ( ) ∑ * ?? ?? ( ) ??+ ?? ?? ?? ( ) ( * ?? ?? ( ) ??+ ) （ 36） 19 簡化一下，看下面這個公式更加直觀： ( ) ∑ (?? ) (?? ) （ 37） 其中， V 表示屬性集合 A 中的一個屬性的全部取值。 支持向量機 支持向量機算法簡介 支持向量機，簡稱 SV 機（論文中一般簡稱 SVM）。它是一種監(jiān)督式 學(xué)習(xí) 的方法，它廣泛的應(yīng)用于統(tǒng)計分類以及回歸分析中。支持向量機將向量映射到一個更高維的空間里，在這個空間里建立有一個最大間隔超平面。在分開數(shù)據(jù)的超平面的兩邊建有兩個互相平行的超平面。分隔超平面使兩個平行超平面的距離最大化。假定平行超平面間的距離或差距越大，分類器的總誤差越小。 支持向量機屬于一般化線性分類器 .他們也可以認為是提克洛夫規(guī)范化方法的一個特例 。 這族分類器的特點是他們能夠同時最小化經(jīng)驗誤差與最大化幾何邊緣區(qū) 。 因此支持向量機也被稱為最 大邊緣區(qū)分類器。在統(tǒng)計計算中，最大期望算法是在概率模型中尋找參數(shù)最大似然估計的算法，其中概率模型依賴于無法觀測的隱藏變量。最大期望經(jīng)常用在機器學(xué)習(xí)和計算機視覺的數(shù)據(jù)集聚領(lǐng)域。最大期望算法經(jīng)過兩個步驟交替進行計算，第一步是計算期望（ E），也就是將隱藏變量象能夠觀測到的一樣包含在內(nèi)從而計算最大似然的期望值；另外一步是最大化（ M），也就是最大化在 E 步上找到的最大似然的期望值從而計算參數(shù)的最大似然估計。 M 步上找到的參數(shù)然后用于另外一個 E 20 步計算，這個過程不斷交替進行。 SVM 的主要思想可以概括為兩點： (1) 它是針對線性可分情況進行分析，對于線性不可分的情況，通過使用非線性映射算法將低維輸入空間線性不可分的樣本轉(zhuǎn)化為高維特征空間使其線性可分，從而使得高維特征空間采用線性算法對樣本的非線性特征進行線性分析成為可能； (2) 它基于結(jié)構(gòu)風險最小化理論之上在特征空間中建構(gòu)最優(yōu)分割超平面，使得學(xué)習(xí)器得到全局最優(yōu)化 ,并且在整個樣本空間的期望風險以某個概率滿足一定上界。 在學(xué)習(xí)這種方法時，首先要弄清楚這種方法考慮問題的特點，這就要從線性可分的最簡單情況討論起，在沒有弄懂其原理之前，不要急于學(xué)習(xí)線性不可分等較復(fù) 雜的情況，支持向量機在設(shè)計時，需要用到條件極值問題的求解，因此需用拉格朗日乘子理論，但對多數(shù)人來說，以前學(xué)到的或常用的是約束條件為等式表示的方式，但在此要用到以不等式作為必須滿足的條件，此時只要了解拉格朗日理論的有關(guān)結(jié)論就行。 支持向量機原理 起初， SVM 主要用來解決兩類別的分類問題，即在類別間尋找一個最優(yōu)分類超平面，使分類錯誤率最小。如圖 212 所示，圖中黑點和白點代表兩類樣本， H 為分類線， 12,HH為過與分類線最近點且與分類線平行的直線，二者之間的距離成為分類間隔。所謂的最優(yōu)分類21 超平面就是要求分類線不但能將兩類樣本無差錯的分離開，而且要能使兩類別間的距離最大。 1H H 2H 2||||w 圖 21 二維空間 SVM 分類示意圖 假設(shè) n 個 線性可分樣本集 ( , )iixy ， 1 , 2 , 3.. . , , { 1 , 1}di n x R y? ? ? ? ?是類別標號， d 維空間中線性判別函數(shù)的為 ()g x wx b??，分類面方程為： :0H wx b?? (38) 對判別函數(shù)進行歸一化，使所有樣本滿足 | ( )| 1gx? ，即離分類面 H最近的點需滿足 | ( )| 1gx? ，則 12,HH直線方程為： 12:1: 1H wx bH wx b???? ??? (39) 可以求得 12,HH平行線間距離為 2/|| ||w ，則分類間隔等于 2/|| ||w 。若使分類間隔最大，等價于使 || ||w 或 2|| ||w 最小。 根據(jù)分類標號和式 (229)有： 11ii iw x by w x b? ? ??? ?? ? ? ?? (310) 由式 (230)可得： ( ) 1 , 1 , 2 , 3...iiy w x b i n? ? ? (311) 22 也即 ( ) 1 0 1 , 2 , 3...iiy w x b i n? ? ? ? (312) 滿足 式 (232)且使 || ||w 最小的分類面稱為 最優(yōu)分類超平面，12,HH上的樣本點稱為支持向量 （ Support Vector， SV）。 由上可知，求最優(yōu)分類超平面等價于求函數(shù) 21122( ) || || ( )w w w w? ? ? ? (313) 最小且 w 滿足式 (232)。 定義拉格朗日函數(shù)： ? ?11( , , ) ( ) [ ( ) ] 12 ni i iiL w b w w y w x b?? ?? ? ? ? ? ?? (314) 其中 i? 為拉格朗日系數(shù)，且 0i?? ，求 ()w? 極小值等價于對 ,wb求L 函數(shù)的最小值。對 ,wb的求偏導(dǎo)并令它們等于 0 得 11( , , ) 0( , , ) 0ni i iiniiiL w b a w y xwL w b a yb?????? ? ? ?? ??? ?? ??? ???? (315) 將110 , 0 , 1 , 2 , . . . , ,nni i i i i iiiy i n w y x? ? ???? ? ? ???代入式 (234)，可得 L 函數(shù)變成參數(shù)為 i? 參數(shù)的函數(shù)： 1,1( , , ) ( ) ( )2n i i j i j i ji i jL w b a W y y x x? ? ? ??? ? ? ??? (316) 根據(jù)對偶理論，求 L 函數(shù)最小值變成求解 ()W? 函數(shù)的最大值，即 23 1,11( ) ( )2. . 00 , 1 , 2 , ...,ni i j i j i ji i jniiiim ax W y y x xs t yin? ? ? ?