102
機器學習與數據挖掘基本算法初步介紹
隨著互聯網技術的發展，特別是web2.0時代的到來，互聯網為我們提供了豐富的數據來源，如何充分的利用這些數據，挖掘用戶信息，是下一代互聯網急需解決的問題。
機器學習和數據挖掘主要是解決以下幾個方麵的問題，分類與預測，優化，獨立特征提取等。機器學習的很多算法都是基於以下圖1中模型來進行設計。
圖1 學習係統模型
我們應對外界環境的刺激輸入，在實踐的過程中不斷學習，獲取經驗知識，並且運用我們所學到的經驗知識指導我們日常生活實踐，通過實踐效果的反饋，也就是所獲得的經驗教訓，從而不斷更新積累我們的閱曆知識，並且在以後的生活中，將自己的經驗知識學以致用。機器學習的兩個主要步驟就是獲取經驗和學以致用。在分類中獲取經驗，其實就是設計分類器，而學以致用正是實踐和驗證分類器。在預測中，獲取經驗就是獲取事物發展的規律，從而預測事物發展的趨勢，也就是學以致用。
現在機器學習的算法多是設計一些模型（即分類器），通過導師學習來訓練出模型的參數，此處的模型參數就是我們所獲取的經驗知識，然後將測試數據或是待分類的數據輸入到模型中，既可以得到分類或預測的結果（此過程就是一個學以致用實踐的過程）。在神經網絡中，我們是要訓練各神經元之間的連接權值，而SVM，我們是要訓練分類超平麵的y=wx+b中的w，b通過帶入一個樣本代入既可以得到。x是數據的特征向量，y是分類標識。決策樹中是通過訓練出一顆決策樹作為分類器，貝葉斯模型則是通過概率模型來進行預測。
監督學習_分類與預測
分類主要是根據事物的某些屬性對其進行歸類。而預測主要是根據已有的信息對未知的某一趨勢進行預測。在第一期的討論中，如何將已知的知識和未知的問題聯係起來，利用已知的知識來解決未知的問題？分類和預測問題可能能給與你一些啟發。以下我們采用黑盒的方法來分析分類與預測問題。
通過機器學習的方法進行分類預測的時候，主要包括輸入和輸出。
輸入：訓練數據，測試數據
輸出：訓練結果，分類結果
訓練數據就是一些已知了正確答案的典型例題，而測試數據就是待分類數據，也可以理解為老師給我們的測試題，測試我們學習的結果。
訓練結果就是老師循循善誘的分析例題，每一步驟所得到的結果（試想以前數學解題中的綜合分析法），比較每一步驟的結果與正確答案還相差多遠，我們每次逐步調整我們的思路，一步一步得到正確答案。而分類結果就是我們運用老師講解例題時所傳授的解題方法解答測試題所得的答案。
各輸入輸出一般的形式化表達如下：
訓練數據：（特征向量，目標向量（即分類標識））
測試數據：特征向量
訓練結果：輸出向量
分類結果：輸出向量
特征向量其實就是對數據的抽象，抽象就是抽取本質特征的過程。當然具體抽取什麼樣的特征，視具體應用而定。比如影像數據其是包含豐富信息的，我們一般是抽象其為一個二維的亮度值矩陣。此時每一個像素點為一個數據，而特征向量就是各個波段的灰度值序列。如：（B1,B2,B3,B4, B5, B6）
目標向量在此是表征每一個像素屬於某一類地物的概率。比如將一副影像分為6類地物。則目標向量的維度則為6，每一分量表征的是屬於某一類的概率。比如在訓練數據屬於第1類的目標向量為(1,0,0,0,0,0)。目標向量的維度一般為類別數n，而若屬於第i類則，則目標向量第i分量為1，其餘為0。其意義表征該像素完全屬於第i類。
輸出向量的格式和目標向量是一樣的，其也是表征每一個像素屬於某一類地物的概率。不同的是目標向量是用於訓練數據中，而且一般是人為事先指定屬於給類別的概率。而輸出向量則是將測試數據輸入到分類器，分類器分析得到的分類結果。輸出向量的維度也是類別數n，每一分量的取值一般為[0,1]。假如輸出向量第i分量最大，我們則視其屬於第i類。
了解輸入輸出對我們使用一些分類器進行分類有很大的幫助。在決定輸入輸出，最關鍵的是樣本數據（訓練數據與測試數據）的選擇以及特征提取，還有假設評估。這些直接關係到我們學習到的經驗知識是否貨真價實，是否真的解決問題，也就是說訓練得到的分類器是否能有效正確的進行分類預測。對於樣本數據的選擇，我們要選擇足夠多的樣本，並且是比較典型的樣本數據，能夠反映總體數據或是測試數據整體特性的數據；對於特征提取算法的選擇也非常重要，因為這關係到特征向量的質量，常用的特征提取有主成分分析，以及非負矩陣因式分解等；對於假設評估就是驗證分類器分類的效果。一般用分類正確率來衡量。
神經網絡與SVM
我們以下圖介紹黑盒分類器（如神經網絡，SVM等）涉及的思想。
上圖就是一個學習訓練過程。當通過訓練數據訓練得到分類器之後，我們將測試數據或是待分類數據輸入到分類器中，上圖藍色線所標注的過程就是一個學以致用的過程。而藍色線和紅色線標注的整個過程就是一個獲取經驗知識的過程，這個過程是在邊學習邊實踐。
BP人工神經網絡
神經網絡主要由一組神經元構成，主要包括輸入層，隱層和輸出層單元。如下圖所示：
圖3 神經網絡拓撲結構
BP人工神經網絡基本原理是模擬人的大腦對外界環境接收的信息（初始輸入），進行不斷的實踐改進（激勵和傳遞函數，誤差和閾值改正函數），達到或接近預期目標（目標向量），從而獲取學習經驗方法（網絡連接權陣和結點閾值），並學以致用（網絡仿真）的過程。
如下圖所示：
圖4 神經網絡模型
BP神經網絡的主要步驟如下：
• 創建網絡——構建平台
– 輸入：神經網絡初始化信息，權值和閾值的初值
– 輸出：初始化後的神經網絡
– 處理：newff(minmax(X),[5,3],{'logsig','purelin'},'traingdx');
• 學習訓練——學習改進，獲取經驗
– 輸入：輸入向量X，目標向量Y，神經網絡
– 輸出：帶有訓練後權連接矩陣以及各神經元的閾值的神經網絡
– 處理：train(net,X,Y)
• 網絡仿真——學以致用
– 輸入：具有“方法經驗”的net，輸入數據test_input
– 輸出：學以致用的實踐結果
– 處理：sim(net,test_input)
SVM算法
SVM算法主要是訓練出一個分類超平麵。其最初是進行二分類，多分類是建立在二分類的基礎上。SVM算法和神經網絡不同的在於其采用不同的模型，但是輸入輸出機製是一樣的。SVM算法涉及為找到分類超平麵本是一種線性分類，為了解決非線性分類問題，其引入了核函數的方法。因為本人對這塊不是很了解，具體大家可以參見資料
https://www.cnblogs.com/jerrylead/archive/2011/03/13/1982639.html
圖5 SVM線性分類
圖中，H直線即我們要得到的分類超平麵，而彩色的數據點即為支持向量。
貝葉斯算法——疾病診斷
我們常常可以通過病例庫統計出患某種病的概率，以及患這種病並顯現某種症狀的概率。而我們卻難以通過症狀確診某種疾病。我們常常是通過醫生經驗，如果患A病，顯現B種症狀的概率比較高，我們則認為，當某人顯現B種症狀的時候，則判其患有A病。這個過程其實就涉及到貝葉斯定理。
P(Disease| Symptom)= P(Disease)* P(Symptom | Disease)/ P(Symptom)
上式就是求解患者顯現某種症狀Symptom，表明其患有疾病Disease的概率P(Disease|Symptom)計算方法。通過統計病例庫，了解患Disease的概率P(Disease)，以及在確診Disease情況下，顯現症狀的概率P(Symptom| Disease)。同時我們統計各種疾病顯現該種症狀Symptom的概率P (Symptom)。我們以下麵的圖表為例子來進行計算。
我們就一計算顯現SymptomA 症狀，為患Disease2的概率P(Disease2 | SymptomA)
P(Disease2)= 43/100 = 0.43; P(SymptomA | Disease2)= 25/43=0.581;
P(SymptomA)= 39/100=0.39; P(Disease2 | SymptomA)=0.43*0.581/0.39=0.64;
同理可得：
P(Disease1| SymptomA) = 0.01/0.39
P(Disease3| SymptomA) =0.05 /0.39
P(Health| SymptomA) = 0.08/0.39
從以上概率比較我們可以清楚判斷顯現症狀SymptomA的患者患有疾病Disease2。
貝葉斯定理其實是基於條件概率變換得到的（這句話大家可以通過深入學習貝葉斯有更加深入的了解），如下所示：
P(Symptom | Disease)= P(Disease | Symptom)*P(Symptom)/ P(Disease)；
在貝葉斯定理中牽涉到兩個概念，先驗概率和後驗概率（參見百度百科）：
先驗概率：是指根據以往的經驗和分析得到的概率，如全概率公式，它往往是作為“由因求果”問題中的“因”出現。
客觀先驗概率，利用過去曆史資料計算得到的先驗概率，稱為客觀先驗概率；主觀先驗概率，當曆史資料無從取得或資料不完全時，憑人們的主觀經驗來判斷而得到的先驗概率。
後驗概率：是指在得到“結果”的信息後重新修正的概率，如貝葉斯公式中的，是“執果尋因”問題中的“因”。後驗概率的計算以先驗概率為基礎。
先驗概率就是指其一般統計曆史資料以及全概率公式進行計算得來，事情可能還沒有發生，我們“由因尋果”。而後驗概率是在得到相關信息重新修正後得到的概率。即在先驗概率的基礎上，一般通過貝葉斯公式進行計算得來。後驗概率是指事情已經發生了，其是由某個原因引起的概率。也就是“執果尋因”。
上述疾病診斷例子采用的是樸素貝葉斯方法。其前提假設是各特征之間應該是相互獨立的。而不是具有依賴連帶關係。比如疾病1顯現症狀A與顯現症狀B是沒有關係的。如果疾病1顯現症狀A時，很大可能顯現症狀B，這時候症狀A、B之間就不是相互依賴的關係了。雖然特征之間完全的相互獨立基本是不可能的，但是事實證明，假設他們之間是相互獨立的，采用貝葉斯方法也是非常實用的。
決策樹算法
決策樹方法，關鍵在於構建一顆決策樹，但是如何構建一顆決策樹，我們就需要確定各結點，這就涉及到一些概念，信息增益。決策樹分類類似於層次迭代分類，對所有數據進行第一次分類分成若幹類，得到第一層聚類，然後將第一層的所有類每一類內部再次分類，從而得到第二層……，以此直至分類結果每類非常的純潔~~然而每次分類的都要保證其類間方差最大，類內方差最小，這就牽涉到信息增益的問題。具體大家可以參見集體智慧編程的第7章的決策樹建模。
由於決策樹具有解釋的特點，因為它是商務分析、醫療決策和政策製定領域裏應用最為廣泛的數據挖掘方法之一。通常，決策樹的構造是自動進行的，專家們可以利用形成的決策樹來理解問題的某些關鍵因素，然後對其加以改進，以便更好地與他的觀點相匹配。這一過程允許機器協助專家進行決策，並清晰地展示出推導的路徑，從而我們可以據此來判斷預測的質量。
如今，決策樹以這樣的形式廣泛運用於眾多應用係統之中，其中包括了顧客調查、金融風險分析、輔助診斷和交通預測。
各監督分類算法特點比較
上表主要是根據自己材料的閱讀，進行的總結，不保證權威，歡迎大家批評指正~~
非監督學習（聚類_發現群組）
非監督學習就是不需要對分類器用訓練數據訓練，也就是不需要老師講解帶有正確的答案的例題來獲取解題方法。試想在一個麵具舞會上，大家互不相識，也沒有人引薦。但是很快就會成團結簇。你會發現那些很有魅力的人，會具有強大的磁場，將與自己有共同話題的人吸引到自己的周圍。此時舞會上每個人是一個聚類點，而比較有魅力的人就會成為聚類中心，而具有共同話題就是聚類內部聚類點之間的相似性。這個過程就是所謂的“物以類聚，人以群分”。目前發現的非監督學習方法，主要是聚類方法。
聚類方法主要包括描述聚類點，相似性衡量以及聚類法則。描述聚類點其實是一個形式化表達的過程，比如將舞會上的人描述為聚類點，因為是基於喜好聚類，那麼聚類點所描述的向量即為喜好向量；相似性度量方法一般有歐式距離法，皮爾遜相關係數法， Tanimoto係數等，在此例子中就是個喜好向量之間的歐式距離來描述兩個人之間的相似性；聚類法則就是以什麼策略來進行聚類，比如層次聚類，迭代聚類。具體大家可以回憶比較kmeans算法的聚類以及係統聚類方法的不同等。
優化
優化算法主要是尋找一種最優方案。通過嚐試不同方案，尋找使得成本最低的方案。其數學描述如下：
優化的目標就是在解空間D中尋找使得成本函數f(x)最小的解x。當然也可以是取最大值，隻需要在目標函數前加一個負號就ok了。優化過程的步驟主要包括描述題解，設置目標函數，按某一搜索策略搜索使得目標函數得到最優的題解。優化算法一般用於求解最優方案，如優化參數，提供最短路線，最小交叉網絡，最大最小流網絡等。
優化算法的主要步驟為：
（1） 描述題解
題解就是我們要獲得的最優方案，比如同學會集體到武漢旅遊，要給來自各地的同學安排車次。假如每天每個地方都有6趟到武漢的火車，每趟火車的價錢不同。大家要同一天集在武漢火車站集合，一起到武漢大學來賞櫻花。由於本人較窮，無法安排住宿，所以很可惜大家要同一天離開。現在我要尋找一種最優的車次安排，使得大家的總花銷最少（時間成本與金錢花銷）此時的題解就是每個人的車次序列。如果是求解某一函數的最值，此時的題解就是解空間區域的任一值。簡單說就是候選方案的計算機描述。
（2） 搜索題解
對於解空間D中x的搜索策略有兩種，一種是窮盡搜索，一種是啟發式搜索。窮盡搜索就是將解空間中的每一個x值都帶入到f(x)中，看使得f(x)值最小或者最大的值時的解為多少。對灰度圖像進行二值化的OSTU算法就是采用這種方法（因為其搜索最佳閾值隻要在0到255的區間即可，區間小）。這種方法簡單直觀，並且保證能到最優解，不容易陷入局部極值的情況，但是它是一種暴力方法。
試想有些題解的可能性百萬個，此時窮盡搜索方法效率低下。而啟發式搜索是沿著成本較小的方向進行搜索題解。這讓我想到一個故事，一個設計師為園林設計一條小路，他不知道哪一條路是最佳方案，於是讓人們自己在草地上走，人們自然都會沿著自己認為最短最方便的一條路線來走。幾個月之後，一跳最優的路線就出來，設計師隻要在上麵鋪上石塊即可。啟發式搜索算法有很多，本文簡要介紹其中的隨機搜素，爬山法搜素，以及進化計算的進化策略。隨機搜索往往可以最大限度“普及大眾”，所以采用一定次數的隨機搜索，往往可以找到較好的題解。還有一種是爬山算法，如果我們要以最短的時間爬到最高點，我們就會沿著最陡峭的方向爬（假如我們是采用恒定勻速爬山），這樣爬山的路線最短。此時的成本函數就是花費時間，題解就是爬山路線。此種搜索方法其實是一種貪心算法。但這種搜索方法有一個缺點就是，其可能陷入局部極值的困境。在後麵會進一步進行闡述。
另外一種比較出名的搜索策略，就是進化計算的搜索策略。“物競天擇，適者生存”。我們將題解轉化為種群，我們隻保留適應度比較高的種群進行繁衍後代。在遺傳算法中，是選擇對外界環境適應度高的種群通過交叉，變異進行繁衍後代。此時的適應度函數就是目標函數，或是成本函數，而題解就是各個種群，我們需要經過若幹代繁衍之後，尋找最優種群。也就是適應度最高的種群，即目標函數取得最值的題解。如下圖8流程圖所示：
圖8 遺傳優化算法流程圖
啟發式搜索都容易陷入局部極值的結果。也就是無法達到全局最優的結果。如爬山法，若山峰如下圖9所示，我們隻在A處安排一個爬山者，按照沿最陡峭的方向往上爬，這樣就可能爬不到最高處。
圖9 局部極值困境
而進化計算中，僅僅選擇表現優異的少數幾個題解很快就會使種群變得極端同質化（近親交配），盡管種群中的題解表現得非常不錯，但是他們彼此間不會有太大的差異，因為在這些題解間進行的交叉操作最終會導致種群內的題解變得越來越相似，從而陷入局部最大化。
為防止陷入局部極值有以下幾種解決辦法：
針對爬山法容易陷入局部最優的情況，我們采用隨機重複爬山法。我們設想，多安排幾個人在山腳的不同地方，沿著該地方的最陡峭的方向往上爬。也就是多涉及幾個隨機的初始值，沿著使成本最低的方向搜索題解。如上圖所示，除了設置在A點設置一個種子點，還在B點設置了一個種子點。如果隻單單安排A點，就容易陷入局部最優，而不能達到全局最優。
針對進化計算，容易陷入近親繁殖，物種多樣性降低，遺傳算法采用DNA變異某種程度上可以緩解近親繁殖，使得種群具有多樣性。同時我們采用“最適合者+最幸運者”的方式進行繁衍後代。我們選擇那些最適應環境變化的強者繁衍後代，同時我們隨機抽獎，抽出一些幸運者進行後代繁衍。事實證明，將表現極為優異的題解和大量尚可的題解組合在一起，往往能夠得到更好的結果。
兩種搜索策略比較：
圖10 優化算法搜索策略比較
（3） 目標函數
目標函數就是f(x)，也就是有些資料中經常提到的成本函數。進化計算中的適應度函數也是“該君”。在上麵所舉的給同學提供最優乘車方案，集體來武大看櫻花。在這個例子中所謂的成本主要包括時間成本與金錢成本，主要從以下幾個方麵來考慮：
Ø 價格
同學們所乘車次的總票價，或者有可能是考慮財務因素之後的加權平均。
Ø 旅行時間
每個人在火車上花費的總時間
Ø 等待時間
在火車站等待其他同學到達的時間
Ø 出發時間
早晨太早的車次也許會產生額外的成本，因為這要求可愛的同學們減少睡眠的時間。
以上四個指標，前三個指標都是值都越大，成本越高，而出發時間越早，成本越高，我們采用24小時製，在此減去12，我們簡單認為越在靠近午夜淩晨出發，成本越高。
故我們設置的目標函數如下：
F(x)=a*價格+b*旅行時間+c*等待時間+d*（出發時間-12）
a+b+c+d=1
在上式中，a，b，c，d為對應的權重。成本函數其實質就是時間和金錢花費加權和。
在上個成本函數還涉及一個變量縮放的問題（不好意思，有點涉及細節，但是我認為這個應該不難理解，剛好這個我也知道，就跟大家show off一下~~），原因是時間與金錢成本的單位是不一樣，他們兩是不能相提並論，我們要麼將時間轉化為金錢，或是將金錢轉化為時間；要麼我們設置一個中間變量，一個時間單位是多少個成本單位，一個金錢單位是多少個成本單位，這樣單位就統一了。一般多采用後麵一種方法，該過程就是變量縮放（時間成本變量和金錢成本變量的縮放），大家會發現在實際應用中構造目標函數，經常是要考慮到變量縮放，但具體縮放多少倍，視具體情況而定~~~
優化算法一般包括描述題解，構造目標函數以及搜索題解三步驟。具體算法包括貪心算法，動態規劃，進化計算（如遺傳算法，免疫計算等），群體智能等（如蟻群算法，粒子群算法等）。有興趣的同學可以參見具體的資料。這些算法靜下心來看，沒有大家想象中那麼難。遺傳算法和蟻群算法會在圖像處理應用中會做簡要的介紹，希望沒把大家攪暈乎~~
總結
由於作者水平有限，本文隻簡略的介紹一些基本的機器學習與數據挖掘的算法，而且難免會有很多錯誤，希望大家不吝指正。本文和之前《機器學習_初次見麵請多關照》以及後麵的《這是一個神奇的網站》都隻是引發大家對機器學習的興趣，如果大家想深入學習可以參見本文後麵推薦的兩本書，其中《集體智慧編程》為入門書籍，《機器學習》則更為嚴謹，更加偏向理論。
文章寫得倉促（因為本人還有老板的任務），有很多錯誤，請大家多加見諒，也真誠希望大家能夠對錯誤進行指出，以便我改正，小女子萬分感激！
參考資料
[1] 集體智慧編程Toby Segaran
[2] 空間信息智能處理秦昆
[3] 神經網絡, matlab中文論壇
[4] SVM算法https://www.cnblogs.com/jerrylead/archive/2011/03/13/1982639.html
[6] 先驗概率_百度百科https://baike.baidu.com/view/336751.htm
[7] 後驗概率_百度百科
https://www.baidu.com/s?bs=%B1%B4%D2%B6%CB%B9&f=8&rsv_bp=1&wd=%BA%F3%D1%E9%B8%C5%C2%CA&inputT=2592
[8] 先驗概率和後驗概率的區別https://zhidao.baidu.com/question/74505693
[9] 機器學習(美)Tom Mitchell
介紹兩本比較好的書籍
集體智慧編程Toby Segaran
機器學習(美)Tom Mitchell
最後更新：2017-04-03 12:54:03