1、數學文化之機器學習,劉丙強山東大學數學學院知新樓B835; 88363455bingqiangsdu@gmail.com2013-11-20 (3),1,統(tǒng)計與機器學習,統(tǒng)計學：從不完全的信息里取得準確知識的技巧。統(tǒng)計應用：用數理統(tǒng)計的原理和方法，分析和解釋自然界界的種種現象和數據資料，以求把握其本質和規(guī)律性。機器學習：可以理解為計算機自動從數據中發(fā)現規(guī)律，并應用于解決新問題。內容比較雜，至今還沒

2、有統(tǒng)一的定義，而且也很難給出一個公認的和準確的定義。機器學習在大多數情況下應用概率論與統(tǒng)計學理論來設計算法；,2,機器學習,給定數據 (X1, Y1), (X2, Y2), … ,(Xn, Yn)，機器自動學習 X 和 Y 之間的關系，從而對新的 Xi，能夠預測 Yi。垃圾郵件識別：(郵件 1, 垃圾), (郵件 2, 正常), (郵件 3, 垃圾), …(郵件 N, 正常)郵件 X => 垃圾 or 正常？,3,測試數據

3、,發(fā)現規(guī)律,預測,預測結果,規(guī)則,,,,,,郵件Xi,Yi：垃圾or正常,發(fā)件人郵件地址異常；標題含有“低價促銷”…,機器學習,一般流程：,4,訓練數據,測試數據,學習,預測,預測結果,模型,,,,,,,,訓練過程,應用過程,(X1, Y1)(X2, Y2)… (Xn, Yn),Xi,Yi,機器學習,模型：問題的影響因素(特征)有哪些？它們之間的關系如何？策略：什么樣的模型是好的模型；算法：如何高效的找到最優(yōu)參數

4、；分類：有監(jiān)督的學習；無監(jiān)督的學習；半監(jiān)督的學習；增強學習；多任務學習；,5,統(tǒng)計與機器學習,內容：聚類與分類；統(tǒng)計推斷：參數檢驗，假設檢驗；回歸分析；馬爾科夫鏈與隱馬爾科夫模型。遺傳算法與神經網絡；。。。,6,機器學習：聚類 (Clustering),聚類就是對大量未知標注的數據集，按數據的內在相似性將數據集劃分為多個類別，使類別內的數據相似度較大而類別間的數據相似度較小;簇（或類Cluster）：子集合最

5、大化簇（或類）內的相似性；最小化簇（或類）間的相似性；聚類是一種無監(jiān)督分類法：沒有預先指定的類別；典型的應用作為一個獨立的分析工具，用于了解數據的分布； 作為其它算法的一個數據預處理步驟；,7,機器學習：聚類 (Clustering),簡單示例：聚類后預測：,8,訓練數據,待分類數據,機器學習：聚類 (Clustering),基因表達芯片（微陣列）：預測新測序基因的功能是重要的生物學問題；基因表達微陣列提供了預

6、測功能的途徑；基因芯片對研究調控網絡提供了最基本的數據；基因芯片可以衡量基因在不同條件下的表達量；基因如果被轉錄，就可以認為是處于激活狀態(tài)；轉錄產物 mRNA 的數量代表基因的活性；,9,機器學習：聚類 (Clustering),DNA 芯片的應用：研究基因樣本在在不同的時間段表達的差異；研究不同的基因樣本在相同的條件下的表達差異,10,機器學習：聚類 (Clustering),DNA芯片數據：綠色：僅僅在參考狀態(tài)表達

7、；紅色：僅僅在所研究的狀態(tài)表達；黃色：在兩種狀態(tài)都表達；黑色：在兩種狀態(tài)都不表達；表達強度數據會被標準化、組成表達強度矩陣。,11,機器學習：聚類 (Clustering),DNA 芯片數據的聚類：每組數據可以看做 n 維空間里的點；通過對每個點對計算距離構造距離矩陣；距離較近的基因表達情況相似、或許更有可能具有功能上的相關性；聚類能夠構造功能相關基因集合；,12,機器學習：聚類 (Clustering),DNA芯片數

8、據的聚類：同質性：一個類中基因相似，即距離較??；差異性：不同類的基因非常不同，即距離較大；聚類并非易事；算法不同可能得到不同的結果；,13,,,,,,機器學習：聚類 (Clustering),DNA芯片數據的聚類：兩點之間的距離歐氏距離： 平方歐氏距離：夾角余弦：絕對距離： Chebychev距離:皮爾森相關系數：M

9、inkowski距離：,14,機器學習：聚類 (Clustering),DNA芯片數據的聚類：兩類之間的距離最短距離法:最長距離法：重心法：類平均法：離差平方和：,15,機器學習：聚類 (Clustering),聚類方法：k-均值法（k-means）給定 k, k-均值算法由以下四步來完成:把對象劃分為 k 個非空的子集；隨機的選擇一些種子點作為目前劃分的簇的質心。質心是簇的中心（平均點）；把每一個對象賦

10、給最近的種子點；重復第二步，直到沒有新的分配；,16,機器學習：聚類 (Clustering),聚類方法：k-均值法,17,,,,,,,,,,,,,,,,,,,,,,,,,,,,機器學習：聚類 (Clustering),聚類方法：k-均值法,18,,,,,,,,,,,,,,,,,,,,,,,,,,,,機器學習：聚類 (Clustering),聚類方法：k-均值法,19,,,,,,,,,,,,,,,,,,,,,,,,,,,,機器學習：聚

11、類 (Clustering),聚類方法：k-均值法,20,,,,,,,,,,,,,,,,,,,,,,,,,,,,機器學習：聚類 (Clustering),聚類方法：k-均值法優(yōu)點：復雜度: O(tkn), 其中 n 是對象的數目, k 是 cluster 的數目, t 是迭代的次數，通常 k, t << n；通常以局部最優(yōu)結束，使用遺傳算法技術可以達到全局最優(yōu)；缺點：只有在 cluster 的平均值被定義的情況下才

12、能使用，那當涉及有分類屬性的數據時該怎么辦?需要事先給出 k， cluster 的數目；不能處理噪聲數據和孤立點；不適合發(fā)現非凸面形狀的 cluster ；對初值比較敏感；,21,機器學習：聚類 (Clustering),聚類方法：k-均值法的初值敏感性,22,機器學習：聚類 (Clustering),聚類方法：層次聚類（ Hierarchical Clustering）,23,,,,,,,機器學習：聚類 (Clusterin

13、g),聚類方法：層次聚類（ Hierarchical Clustering）自底向下的聚類每一項自成一類迭代，將最近的兩類合為一類自頂向下的聚類將所有項看作一類找出最不相似的項分裂出去成為兩類,24,機器學習：聚類 (Clustering),聚類方法：層次聚類（ Hierarchical Clustering）,25,機器學習：聚類 (Clustering),聚類方法：層次聚類（ Hierarchical Clusteri

14、ng）常用于系統(tǒng)發(fā)生樹的構造（基于序列）：,26,機器學習：聚類 (Clustering),聚類與系統(tǒng)發(fā)生樹,27,棕熊 北極熊 黑熊 眼鏡熊 大熊貓 浣熊 小熊貓,機器學習：聚類 (Clustering),聚類與系統(tǒng)發(fā)生樹,28,機器學習：聚類 (Clustering),聚類方法：有瑕團聚類（ Corrupted Cliques Clustering）團是圖論中的概念：通過刪邊和加邊，一個圖可以破解

15、為團的集合：,29,,,機器學習：聚類 (Clustering),聚類方法：有瑕團聚類待聚類數據的距離矩陣為完全圖的鄰接矩陣：通過取一個閾值，可以將距離大的邊刪除；將剩余的圖破解為團的集合，每個團對應一個聚類；,30,機器學習：雙聚類 (Bi-Clustering),雙聚類：大規(guī)模表達數據的聚類基因并不在所有條件下表達；基因受多個轉錄因子調控；兩步聚類不能解決問題；,31,,,,,,,,,,,,傳統(tǒng)聚類,雙聚類,機器學習：

16、雙聚類 (Bi-Clustering),雙聚類的目標：相關性,32,機器學習：分類,聚類與分類的區(qū)別：訓練集合有無（監(jiān)督與非監(jiān)督）類別已知和未知,33,機器學習：分類,分類問題及其算法對研究對象進行貼標簽式分類；用途：自然科學中有很多分類問題；生物種群分類；基于訓練集合進行特征選??；基于各種特征進行疾病診斷；方式：基于各種特征，或在機器學習過程中提取特征；一般基于訓練集合給出關于特征的標準；,34,機器學習：分

17、類,二分類問題：目的：將研究目標分為不同屬性的兩類；標準：基于訓練集合的特征選取和特征函數構造；方法：利用學習出來的標準對新目標進行分類；方法：貝葉斯分類；決策樹；支持向量機；人工神經網絡；k 近鄰法；。。。,35,機器學習：決策樹,決策樹(Decision Tree) 決策樹由一個決策圖和可能的結果組成， 用來創(chuàng)建到達目標的規(guī)劃。常用于分類；動物分類的例子：基于不同的屬性進行分步驟的判斷；,36,機器學習

18、：決策樹,要素：特征參數：xi；分類標簽： y= 0 or 1；訓練集合： (xi, yi)構造樹：決策結點、分支和葉結點。步驟：利用訓練集建立并精化決策樹，建立決策樹模型。利用決策樹對新數據進行分類。從根結點依次測試記錄的屬性值，直到到達某葉結點，找到該記錄所在的類。關鍵點：建樹（Tree Building）：決策樹建樹算法見下，這是一個遞歸的過程，最終將得到一棵樹。剪枝（Tree Pruning）：剪枝的目的是降低

19、由于訓練集存在噪聲而產生的起伏。,37,機器學習：決策樹,決策樹算法的點如下：決策樹是一種構建分類模型的非參數方法；不需要昂貴的的計算代價；決策樹相對容易解釋；決策樹是學習離散值函數的典型代表；決策數對于噪聲的干擾具有相當好的魯棒性；冗余屬性不會對決策樹的準確率造成不利影響；找到最佳的決策樹理論上是 NP 難問題；,38,機器學習：決策樹,例子：天氣與高爾夫球場客流量；對決策樹的期望：規(guī)模較??；葉節(jié)點盡量少，熵值低

20、；決策節(jié)點特征的選??；,39,機器學習：決策樹,決策樹的一些缺點：數據碎片問題。隨著樹的生長，可能導致葉結點記錄數太少，對于葉結點代表的類，不能做出具有統(tǒng)計意義的判決；子樹可能在決策樹中重復多次，使決策樹過于復雜；判定條件太過明確，導致爭議；,40,機器學習：支持向量機,支持向量機 （SVM, Supporting Vector Machine）Vapnik；起源于線性分類器，線性可分；擴展到線性不可分的情況；甚至擴展

21、到使用非線性函數中去。近年來的熱點方法；監(jiān)督式學習（supervised learning）,41,機器學習：支持向量機,思想：如果兩類別訓練樣本線性可分，則在兩個類別的樣本集之間存在一個間隔。我們來尋找最優(yōu)分界面；對一個二維空間的問題用下圖表示。,42,機器學習：支持向量機,思想（續(xù)1）H 是將兩類分開的分界面，而 H1 與 H2 與 H 平行，H 是其平分面，H1 上的樣本是第一類樣本到 H 最近距離的點，H2 的點則是第二

22、類樣本距 H 的最近點。,43,機器學習：支持向量機,思想（續(xù)2）由于這兩種樣本點很特殊，處在間隔的邊緣上，因此再附加一個圈表示。這些點稱為支持向量，它們決定了這個間隔。,44,機器學習：支持向量機,思想（續(xù)3）顯然使 H1 與 H2 之間間隔最大的分界面 H 是最合理的選擇，因此最大間隔準則就是支持向量機的最佳準則。,45,,,,,,機器學習：支持向量機,如何找到最大間隔？在凸集合上找最近點：,46,,,,,,,,,,,,,,,

23、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,c,d,,,,,,機器學習：支持向量機,分界線：一個線性判別函數(discriminant function)是指由 x 的各個分量的線性組合而成的函數；兩類情況:對于兩類問題的決策規(guī)則為如果 g(x) > 0，則判定 x 屬于 H1，如果 g(x) < 0，則判定 x 屬于 C2，如果 g(x) = 0，則可以將 x 任意分到某一類或者拒絕判

24、定。,47,機器學習：支持向量機,方程 g(x) = 0 定義了一個判定面，它把歸類于 C1 的點與歸類于 C2 的點分開來。當 g(x) 是線性函數時，此平面被稱為超平面 (hyperplane)。方程 g(x) = 0 實際上是 n - 1維的線性子空間；,48,機器學習：支持向量機,如何找到最大間隔？為了將這個準則具體化，需要用數學式子表達。為了方便，將訓練樣本集表示成 {xi, yi}，i = 1, …, N，其中 xi

25、為 d 維向量也就是特征向量，而 yi ∈{-1, +1}，即用 yi 是 +1 或 -1 表示其類別。對于分界面 H 表示成：并且滿足：故 H1到 H2 的間隔為：目標：在滿足約束條件的前提下達到間隔最大；前提：線性可分；,49,機器學習：支持向量機,轉化為帶約束的極值問題，或規(guī)劃問題；對于這樣一個帶約束條件為不等式的條件極值問題，需要引用擴展的拉格朗日乘子理論，按這個理論構造拉格朗日函數的原則為：,50,(3)

26、,機器學習：支持向量機,上述方法線性可分條件為基本前提；可否將不可分問題轉化為可分？,51,機器學習：支持向量機,異或問題是最簡單的一個無法直接對特征采用線性判別函數解決的問題。如圖所示的四個樣本點。利用 SVM 將他們映射到一個更高維的空間，使之線性可分。,52,機器學習：支持向量機,采用最簡單且展開不超過二次的展開將上述問題的點映射到六維空間：最佳超平面是：其二維空間投影如圖所示,53,,機器學習：支持向量

27、機,特點：對特征空間劃分的最優(yōu)超平面是SVM的目標,最大化分類邊際的思想是SVM方法的核心；支持向量是SVM的訓練結果,在SVM分類決策中起決定作用的是支持向量；模型為凸二次規(guī)劃模型，沒有陷入局部最優(yōu)解的問題，任何局部最優(yōu)解都是全局最優(yōu)解；SVM 的最終決策函數只由少數的支持向量所確定,計算的復雜性取決于支持向量的數目,而不是樣本空間的維數,這在某種意義上避免了“維數災難”。少數支持向量決定了最終結果,這不但可以幫助我們抓住關

28、鍵樣本、“剔除”大量冗余樣本,而且注定了該方法不但算法簡單,而且具有較好的“魯棒”性。,54,機器學習：分類結果的衡量,靈敏度（Sensitivity）與特異度（Specificity）假陽性（FP）、真陽性（TP）；假陰性（FN）、真陰性（FN）；,55,機器學習：分類結果的衡量,Test!,56,機器學習：分類結果的衡量,ROC曲線接收者操作特征（receiver operating characteristic）真陽性率（