大數(shù)據(jù)挖掘主要算法

1、樸素貝葉斯:有以下幾個(gè)地方需要注意：如果給出的特征向量長度可能不同，這是需要?dú)w一化為通長度的向量（這里以文本分類 為例），比如說是句子單詞的話，則長度為整個(gè)詞匯量的長度，對(duì)應(yīng)位置是該單詞出現(xiàn)的次數(shù)。計(jì)算公式如下：1“ I、0q)p(q)心網(wǎng)二士 “一、* * 口 P（w|c：i）其中一項(xiàng)條件概率可以通過樸素貝葉斯條件獨(dú)立展開。要注意一點(diǎn)就是的計(jì)算方法，而由樸素貝葉斯的前提假設(shè)可知，-.-.-.-=c，因此一般有兩種，一種 是在類別為ci的那些樣本集中，找到wj出現(xiàn)次數(shù)的總和，然后除以該樣本的總和；第二種方法 是類別為ci的那些樣本集中，找到wj出現(xiàn)次數(shù)的總和，然后除以該樣本中所有特征出現(xiàn)次數(shù)的

2、 總和。（m p （wl Ci） _ 工一“如果-中的某一項(xiàng)為0，則其聯(lián)合概率的乘積也可能為0，即2中公式的分子為0，為了避免這種現(xiàn)象出現(xiàn)，一般情況下會(huì)將這一項(xiàng)初始化為1，當(dāng)然為了保證概率相等， 分母應(yīng)對(duì)應(yīng)初始化為2（這里因?yàn)槭?類，所以加2,如果是k類就需要加k，術(shù)語上叫做laplace 光滑,分母加k的原因是使之滿足全概率公式）。樸素貝葉斯的優(yōu)點(diǎn)：對(duì)小規(guī)模的數(shù)據(jù)表現(xiàn)很好，適合多分類任務(wù)，適合增量式訓(xùn)練。缺點(diǎn)：對(duì)輸入數(shù)據(jù)的表達(dá)形式很敏感。決策樹：決策樹中很重要的一點(diǎn)就是選擇一個(gè)屬性進(jìn)行分枝，因此要注意一下信息增益的計(jì)算公式， 并深入理解它。信息熵的計(jì)算公式如下:H = -芯）她*（%）其中的

3、n代表有n個(gè)分類類別（比如假設(shè)是2類問題，那么n = 2）。分別計(jì)算這2類樣本 在總樣本中出現(xiàn)的概率pl和p2,這樣就可以計(jì)算出未選中屬性分枝前的信息熵?，F(xiàn)在選中一個(gè)屬性xi用來進(jìn)行分枝，此時(shí)分枝規(guī)則是：如果xi=vx的話，將樣本分到樹的 一個(gè)分支；如果不相等則進(jìn)入另一個(gè)分支。很顯然，分支中的樣本很有可能包括2個(gè)類別，分 別計(jì)算這2個(gè)分支的熵H1和H2,計(jì)算出分枝后的總信息熵H=p1*H1 + p2*H2.，則此時(shí)的信 息增益AH = H-H。以信息增益為原則，把所有的屬性都測(cè)試一邊，選擇一個(gè)使增益最大的屬性 作為本次分枝屬性。決策樹的優(yōu)點(diǎn)：計(jì)算量簡單，可解釋性強(qiáng)，比較適合處理有缺失屬性值的樣

4、本，能夠處理不相關(guān)的特征；缺點(diǎn)：容易過擬合（后續(xù)出現(xiàn)了隨機(jī)森林，減小了過擬合現(xiàn)象）；Logistic 回歸：Logistic是用來分類的，是一種線性分類器，需要注意的地方有:1. logistic函數(shù)表達(dá)式為：I）=。伊&） = i +where其導(dǎo)數(shù)形式為：=（1 +9邛廣）=-J.fl一1（1 + k （1 + ez）=9（#）（1 一如）.logsitc回歸方法主要是用最大似然估計(jì)來學(xué)習(xí)的，所以單個(gè)樣本的后驗(yàn)概率為:p（y I 丁;/ =（新（對(duì)）（1 一知（心）1一到整個(gè)樣本的后驗(yàn)概率:其中：P（y = lx：e）=五次無）尸（y = o| 礦”）=1 一輔（%）通過對(duì)數(shù)進(jìn)一步化簡為：

5、J雄）=1%碓）m= 舟 log（M） + （1 -舟）1理（1 -雄）=13.其實(shí)它的loss function為-1（8）,因此我們需使loss function最小，可采用梯度下降 法得到。梯度下降法公式為：亮雄）=Ti） _ 扁）翕司=（焉-切1一；（皿）奸皿-那%瀚烏=（v（l 頊斜）-（1 g）g（伊司）叼=（。知（二）叼6j :=們+ a （儼）-&（工）矽）Logistic回歸優(yōu)點(diǎn)：1、實(shí)現(xiàn)簡單；2、分類時(shí)計(jì)算量非常小，速度很快，存儲(chǔ)資源低；缺點(diǎn)：1、容易欠擬合，一般準(zhǔn)確度不太高2、只能處理兩分類問題（在此基礎(chǔ)上衍生出來的softmax可以用于多分類），且必須線 性可分；線性回

6、歸:線性回歸才是真正用于回歸的，而不像logistic回歸是用于分類，其基本思想是用梯度下降 法對(duì)最小二乘法形式的誤差函數(shù)進(jìn)行優(yōu)化，當(dāng)然也可以用normal equation直接求得參數(shù)的解， 結(jié)果為：而在LWLR （局部加權(quán)線性回歸）中，參數(shù)的計(jì)算表達(dá)式為：w = （X，WX） x%因?yàn)榇藭r(shí)優(yōu)化的是：L Fit 9 to minimize 二 出。工）2. Output x,由此可見LWLR與LR不同，LWLR是一個(gè)非參數(shù)模型，因?yàn)槊看芜M(jìn)行回歸計(jì)算都要遍歷 訓(xùn)練樣本至少一次。線性回歸優(yōu)點(diǎn)：實(shí)現(xiàn)簡單，計(jì)算簡單；缺點(diǎn)：不能擬合非線性數(shù)據(jù)；KNN算法：KNN即最近鄰算法，其主要過程為：計(jì)算訓(xùn)練樣本

7、和測(cè)試樣本中每個(gè)樣本點(diǎn)的距離（常見的距離度量有歐式距離，馬氏距離 等）；對(duì)上面所有的距離值進(jìn)行排序；選前k個(gè)最小距離的樣本；根據(jù)這k個(gè)樣本的標(biāo)簽進(jìn)行投票，得到最后的分類類別；如何選擇一個(gè)最佳的K值，這取決于數(shù)據(jù)。一般情況下，在分類時(shí)較大的K值能夠減小噪 聲的影響。但會(huì)使類別之間的界限變得模糊。一個(gè)較好的K值可通過各種啟發(fā)式技術(shù)來獲取， 比如，交叉驗(yàn)證。另外噪聲和非相關(guān)性特征向量的存在會(huì)使K近鄰算法的準(zhǔn)確性減小。近鄰算法具有較強(qiáng)的一致性結(jié)果。隨著數(shù)據(jù)趨于無限，算法保證錯(cuò)誤率不會(huì)超過貝葉斯算法 錯(cuò)誤率的兩倍。對(duì)于一些好的K值，K近鄰保證錯(cuò)誤率不會(huì)超過貝葉斯理論誤差率。注：馬氏距離一定要先給出樣本集

8、的統(tǒng)計(jì)性質(zhì)，比如均值向量，協(xié)方差矩陣等。關(guān)于馬氏距 離的介紹如下：馬氏距離是由印度統(tǒng)計(jì)學(xué)家巨哈拉諾比斯（P. 3. Kahalanoois：提出的，表示數(shù)據(jù)的協(xié)方差距離。它是一科有池的t 同色是它考慮到冬種特性之間豹聯(lián)系（例如：一條關(guān)于身高的信息會(huì)帶來一條關(guān)于體重的信息，因?yàn)閮烧呤怯嘘P(guān)聯(lián)豹） 丁測(cè)量尺度。交于一個(gè)均值為卜=（四1,聞,:岫匚協(xié)方差x巨降為習(xí)的全芟量向量也=（明，此？均，（x） = /（$ 閔丁習(xí)-七責(zé)p）馬氏距也可以定義為兩個(gè)服從同一分布并且其協(xié)方差拒陣為；的隨機(jī)變量與鄉(xiāng)的差異程度：d（W y） = x - y）如具協(xié)方差拒陣為單位矩陣，馬氏距離就簡化為欣氏距陶：如果協(xié)方差矩降

9、為對(duì)角降，其也可稱K正魂化豹?dú)W氐距離。站，切=、色目其中外是M的標(biāo)準(zhǔn)差。KNN算法的優(yōu)點(diǎn)：思想簡單，理論成熟，既可以用來做分類也可以用來做回歸；可用于非線性分類；訓(xùn)練時(shí)間復(fù)雜度為O（n）；準(zhǔn)確度高，對(duì)數(shù)據(jù)沒有假設(shè)，對(duì)outlier不敏感；缺點(diǎn)：計(jì)算量大；樣本不平衡問題（即有些類別的樣本數(shù)量很多，而其它樣本的數(shù)量很少）；需要大量的內(nèi)存；SVM :要學(xué)會(huì)如何使用libsvm以及一些參數(shù)的調(diào)節(jié)經(jīng)驗(yàn)，另外需要理清楚svm算法的一些思路：svm中的最優(yōu)分類面是對(duì)所有樣本的幾何裕量最大（為什么要選擇最大間隔分類器，請(qǐng)從數(shù)學(xué)角度上說明？網(wǎng)易深度學(xué)習(xí)崗位面試過程中有被問到。答案就是幾何間隔與樣本的誤分次誤分次

10、數(shù)聆丫數(shù)間存在關(guān)系：，其中的分母就是樣本到分類間隔距離，分子中的R是所有樣本中的最長向量值），即：經(jīng)過一系列推導(dǎo)可得為優(yōu)化下面原始目標(biāo)：s.t 15 i = L., m下面來看看拉格朗日理論：miiy, f(w) TOC o 1-5 h z HYPERLINK l bookmark85 o Current Document 泌.gi(ttJ) 0, i = 1mi=l而這個(gè)函數(shù)可以用常用的優(yōu)化方法求得a，進(jìn)而求得w和b。按照道理，svm簡單理論應(yīng)該到此結(jié)束。不過還是要補(bǔ)充一點(diǎn)，即在預(yù)測(cè)時(shí)有：m a/噂 x) + b=1那個(gè)尖括號(hào)我們可以用核函數(shù)代替，這也是svm經(jīng)常和核函數(shù)扯在一起的原因。最后

11、是關(guān)于松弛變量的引入，因此原始的目標(biāo)優(yōu)化公式為：min” ；|叫|/ +。丈&s.t. g(也& + 6) 1 fij i = 1,.,m 0, i = 1,.)此時(shí)對(duì)應(yīng)的對(duì)偶優(yōu)化公式為:m1 mma3(Q W(a) = 四_ 5 /如mW。) i=l ij=Ls.t. 0 ct： C, i = 1,. m工=0： i=i與前面的相比只是a多了個(gè)上界。SVM算法優(yōu)點(diǎn)：可用于線性/非線性分類，也可以用于回歸;低泛化誤差；容易解釋；計(jì)算復(fù)雜度較低；缺點(diǎn)：對(duì)參數(shù)和核函數(shù)的選擇比較敏感；原始的SVM只比較擅長處理二分類問題;Boosting :主要以Adaboost為例，首先來看看Adaboost的流

12、程圖，如下:從圖中可以看到，在訓(xùn)練過程中我們需要訓(xùn)練出多個(gè)弱分類器（圖中為3個(gè)），每個(gè)弱分 類器是由不同權(quán)重的樣本（圖中為5個(gè)訓(xùn)練樣本）訓(xùn)練得到（其中第一個(gè)弱分類器對(duì)應(yīng)輸入樣 本的權(quán)值是一樣的），而每個(gè)弱分類器對(duì)最終分類結(jié)果的作用也不同，是通過加權(quán)平均輸出的， 權(quán)值見上圖中三角形里面的數(shù)值。那么這些弱分類器和其對(duì)應(yīng)的權(quán)值是怎樣訓(xùn)練出來的呢？下面通過一個(gè)例子來簡單說明。書中（machine learning in action）假設(shè)的是5個(gè)訓(xùn)練樣本，每個(gè)訓(xùn)練樣本的維度為2， 在訓(xùn)練第一個(gè)分類器時(shí)5個(gè)樣本的權(quán)重各為0.2.注意這里樣本的權(quán)值和最終訓(xùn)練的弱分類器組 對(duì)應(yīng)的權(quán)值a是不同的，樣本的權(quán)重只

13、在訓(xùn)練過程中用到，而a在訓(xùn)練過程和測(cè)試過程都有用 到?，F(xiàn)在假設(shè)弱分類器是帶一個(gè)節(jié)點(diǎn)的簡單決策樹，該決策樹會(huì)選擇2個(gè)屬性（假設(shè)只有2個(gè) 屬性）的一個(gè)，然后計(jì)算出這個(gè)屬性中的最佳值用來分類。Adaboost的簡單版本訓(xùn)練過程如下：訓(xùn)練第一個(gè)分類器，樣本的權(quán)值D為相同的均值。通過一個(gè)弱分類器，得到這5個(gè)樣本 （請(qǐng)對(duì)應(yīng)書中的例子來看，依舊是machine learning in action）的分類預(yù)測(cè)標(biāo)簽。與給出的樣本真實(shí)標(biāo)簽對(duì)比，就可能出現(xiàn)誤差（即錯(cuò)誤）。如果某個(gè)樣本預(yù)測(cè)錯(cuò)誤，則它對(duì)應(yīng)的錯(cuò)誤值為該 樣本的權(quán)重，如果分類正確，則錯(cuò)誤值為0.最后累加5個(gè)樣本的錯(cuò)誤率之和，記為&通過e來計(jì)算該弱分類器的

14、權(quán)重a，公式如下：通過a來計(jì)算訓(xùn)練下一個(gè)弱分類器樣本的權(quán)重D，如果對(duì)應(yīng)樣本分類正確，則減小該樣 本的權(quán)重，公式為：Sum(D)Sum(D)如果樣本分類錯(cuò)誤，則增加該樣本的權(quán)重，公式為:循環(huán)步驟1,2,3來繼續(xù)訓(xùn)練多個(gè)分類器，只是其D值不同而已。測(cè)試過程如下：輸入一個(gè)樣本到訓(xùn)練好的每個(gè)弱分類中，則每個(gè)弱分類都對(duì)應(yīng)一個(gè)輸出標(biāo)簽，然后該標(biāo)簽乘 以對(duì)應(yīng)的a，最后求和得到值的符號(hào)即為預(yù)測(cè)標(biāo)簽值。Boosting算法的優(yōu)點(diǎn)：低泛化誤差；容易實(shí)現(xiàn)，分類準(zhǔn)確率較高，沒有太多參數(shù)可以調(diào)；缺點(diǎn)：對(duì)outlier比較敏感；聚類：根據(jù)聚類思想劃分：1.基于劃分的聚類：K-means, k-medoids（每一個(gè)類別中

15、找一個(gè)樣本點(diǎn)來代表）,CLARANS.k-means是使下面的表達(dá)式值最?。簁-means 算法的優(yōu)點(diǎn)：（1）k-means算法是解決聚類問題的一種經(jīng)典算法，算法簡單、快速。（2）對(duì)處理大數(shù)據(jù)集，該算法是相對(duì)可伸縮的和高效率的，因?yàn)樗膹?fù)雜度大約是O（nkt）， 其中n是所有對(duì)象的數(shù)目，k是簇的數(shù)目,七是迭代的次數(shù)。通常kgp（Z;。）史臉工此次）；9）ii ” HYPERLINK l bookmark176 o Current Document =?咚Q，風(fēng)喘辯蘭移將皿，嶗群EM算法一個(gè)常見的例子就是GMM模型，每個(gè)樣本都有可能由k個(gè)高斯產(chǎn)生，只不過由每 個(gè)高斯產(chǎn)生的概率不同而已，因此每個(gè)樣

16、本都有對(duì)應(yīng)的高斯分布（k個(gè)中的某一個(gè)），此時(shí)的隱 含變量就是每個(gè)樣本對(duì)應(yīng)的某個(gè)高斯分布。GMM的E步公式如下（計(jì)算每個(gè)樣本對(duì)應(yīng)每個(gè)高斯的概率）：II：Estep） For each i. j, set姑：=p（=如）更具體的計(jì)算公式為:成事=J|必）;取尸足）= ,j；北 也修=丈：_1 p（工國 |M）=如 p,、二套時(shí)M步公式如下（計(jì)算每個(gè)高斯的比重，均值，方差這3個(gè)參數(shù)）：（M-stcp） Update the parameters:EZXiWW-巧）（那）-為）關(guān)于EM算法可以參考Ng的cs229課程資料或者網(wǎng)易公開課：斯坦福大學(xué)公開課：機(jī)器 學(xué)習(xí)課程。Apriori:Apriori是

17、關(guān)聯(lián)分析中比較早的一種方法，主要用來挖掘那些頻繁項(xiàng)集合。其思想是：如果一個(gè)項(xiàng)目集合不是頻繁集合，那么任何包含它的項(xiàng)目集合也一定不是頻繁集合；如果一個(gè)項(xiàng)目集合是頻繁集合，那么它的任何非空子集也是頻繁集合；Aprioir需要掃描項(xiàng)目表多遍，從一個(gè)項(xiàng)目開始掃描，舍去掉那些不是頻繁的項(xiàng)目，得到的 集合稱為L，然后對(duì)L中的每個(gè)元素進(jìn)行自組合，生成比上次掃描多一個(gè)項(xiàng)目的集合，該集合稱 為C，接著又掃描去掉那些非頻繁的項(xiàng)目，重復(fù)看下面這個(gè)例子：元素項(xiàng)目表格：Tran寫sictiQn numberI加msAgurf U.l Ainnple of transitions from A natural foods

18、 otety dijcre called 博Foodssoy milk, lettucelettuce, diapers, wjnc, chardsoy milk, diapers, wine, orange juice lettuce, scy milk, diaper$T wine 論ttug soy milk, diapers, orange juice如果每個(gè)步驟不去掉非頻繁項(xiàng)目集，則其掃描過程的樹形結(jié)構(gòu)如下:0123在其中某個(gè)過程中，可能出現(xiàn)非頻繁的項(xiàng)目集，將其去掉（用陰影表示）為:上面的內(nèi)容主要參考的是 machine learning in action這本書。FP Growth:FP Growth是一種比Apriori更高效的頻繁項(xiàng)挖掘方法，它只需要掃描項(xiàng)目表2次。其中 第1次掃描獲得當(dāng)個(gè)項(xiàng)目的頻率，去掉不符合支持度要求的項(xiàng)，并對(duì)剩下的項(xiàng)排序。第2遍掃 描是建立一顆 FP-Tree(frequent-patten tree)。接下來的工作就是在FP-Tree上進(jìn)行挖掘。比如說有下表：TIDHems houjjluIktiueiU items00/, fl, ti.g,