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