随着網際網路技術的發展，特别是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等）涉及的思想。
圖2 機器學習過程
上圖就是一個學習訓練過程。當通過訓練資料訓練得到分類器之後，我們将測試資料或是待分類資料輸入到分類器中，上圖藍色線所标注的過程就是一個學以緻用的過程。而藍色線和紅色線标注的整個過程就是一個擷取經驗知識的過程，這個過程是在邊學習邊實踐。
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算法涉及為找到分類超平面本是一種線性分類，為了解決非線性分類問題，其引入了核函數的方法。因為本人對這塊不是很了解，具體大家可以參見資料
<a target="_blank" href="http://www.blogjava.net/images/blogjava_net/zhenandaci/windowslivewriter/svmrefresh_9b92/image_2.png"></a>
圖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)。我們以下面的圖表為例子來進行計算。
圖6 病例表
我們就一計算顯現symptoma 症狀，為患disease2的機率p(disease2 | 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章的決策樹模組化。
由于決策樹具有解釋的特點，因為它是商務分析、醫療決策和政策制定領域裡應用最為廣泛的資料挖掘方法之一。通常，決策樹的構造是自動進行的，專家們可以利用形成的決策樹來了解問題的某些關鍵因素，然後對其加以改進，以便更好地與他的觀點相比對。這一過程允許機器協助專家進行決策，并清晰地展示出推導的路徑，進而我們可以據此來判斷預測的品質。
如今，決策樹以這樣的形式廣泛運用于衆多應用系統之中，其中包括了顧客調查、金融風險分析、輔助診斷和交通預測。
各監督分類算法特點比較
圖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中文論壇
[7] 後驗機率_百度百科
<a target="_blank" href="http://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">http://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</a>
[9] 機器學習(美)tom mitchell
介紹兩本比較好的書籍
集體智慧程式設計toby segaran
機器學習(美)tom mitchell