2017校招正在火熱的進(jìn)行，后面會(huì)不斷更新涉及到的相關(guān)知識(shí)點(diǎn)。

盡管聽(tīng)說(shuō)今年幾個(gè)大互聯(lián)網(wǎng)公司招的人超少，但好像哪一年都說(shuō)是就業(yè)困難，能夠進(jìn)去當(dāng)然最好，不能進(jìn)去是不是應(yīng)該也抱著好的期望去找自己滿(mǎn)意的呢？

最近筆試了很多家公司校招的數(shù)據(jù)分析和數(shù)據(jù)挖掘崗位，今天(9.18r)晚上做完唯品會(huì)的筆試題，才忽然意識(shí)過(guò)來(lái)，不管題目簡(jiǎn)單也好、難也好，都要去切切實(shí)實(shí)的去掌握。畢竟不能永遠(yuǎn)眼高手低，否則最后吃虧的一定是自己。

• 知識(shí)點(diǎn)1：貝葉斯公式
  貝葉斯公式：P(B|A)=P(A|B)\P(B)/P(A)
  其中P(A)可以展開(kāi)為
  P(A)=P(A|B1)\P(B1)+P(A|B2)\P(B2)+...+P(A|Bn)\P(Bn)
  (這在很多問(wèn)答題或者選擇題中都有用到)

• 知識(shí)點(diǎn)2：關(guān)聯(lián)規(guī)則分析
  主要考的是支持度和置信度。
  

  1.png

• 知識(shí)點(diǎn)3：聚類(lèi)
  聚類(lèi)之間類(lèi)的度量是分距離和相似系數(shù)來(lái)度量的，距離用來(lái)度量樣品之間的相似性（K-means聚類(lèi)，系統(tǒng)聚類(lèi)中的Q型聚類(lèi)），相似系數(shù)用來(lái)度量變量之間的相似性（系統(tǒng)聚類(lèi)中的R型聚類(lèi)）。

  最常用的是K-means聚類(lèi)，適用于大樣本，但需要事先指定分為K個(gè)類(lèi)。
  處理步驟：
  1）、從n個(gè)數(shù)據(jù)對(duì)象中任意選出k個(gè)對(duì)象作為初始的聚類(lèi)中心
  2）、計(jì)算剩余的各個(gè)對(duì)象到聚類(lèi)中心的距離，將它劃分給最近的簇
  3）、重新計(jì)算每一簇的平均值（中心對(duì)象）
  4）、循環(huán)2-3直到每個(gè)聚類(lèi)不再發(fā)生變化為止。

  系統(tǒng)聚類(lèi)適用于小樣本。

• 知識(shí)點(diǎn)4：分類(lèi)

有監(jiān)督就是給的樣本都有標(biāo)簽，分類(lèi)的訓(xùn)練樣本必須有標(biāo)簽，所以分類(lèi)算法都是有監(jiān)督算法。
監(jiān)督機(jī)器學(xué)習(xí)問(wèn)題無(wú)非就是“minimizeyour error while regularizing your parameters”，也就是在規(guī)則化參數(shù)的同時(shí)最小化誤差。最小化誤差是為了讓我們的模型擬合我們的訓(xùn)練數(shù)據(jù)，而規(guī)則化參數(shù)是防止我們的模型過(guò)分?jǐn)M合我們的訓(xùn)練數(shù)據(jù)，提高泛化能力。

#1.樸素貝葉斯
    1）基礎(chǔ)思想：對(duì)于給出的待分類(lèi)項(xiàng)，求解在此項(xiàng)出現(xiàn)的條件下各個(gè)類(lèi)別出現(xiàn)的概率，哪個(gè)最大，就認(rèn)為此分類(lèi)項(xiàng)屬于哪個(gè)類(lèi)別。
    2）優(yōu)點(diǎn)： 
    可以和決策樹(shù)、神經(jīng)網(wǎng)絡(luò)分類(lèi)算法相媲美，能運(yùn)用于大型數(shù)據(jù)庫(kù)中。
    方法簡(jiǎn)單，分類(lèi)準(zhǔn)確率高，速度快，所需估計(jì)的參數(shù)少，對(duì)于缺失數(shù)據(jù)不敏感。
    3）缺點(diǎn)： 
    假設(shè)一個(gè)屬性對(duì)定類(lèi)的影響?yīng)毩⒂谄渌膶傩灾?，這往往并不成立。（喜歡吃番茄、雞蛋，卻不喜歡吃番茄炒蛋）。
    需要知道先驗(yàn)概率。


#2.決策樹(shù)
    1）基礎(chǔ)思想：決策樹(shù)是一種簡(jiǎn)單但廣泛使用的分類(lèi)器，它通過(guò)訓(xùn)練數(shù)據(jù)構(gòu)建決策樹(shù)，對(duì)未知的數(shù)據(jù)進(jìn)行分類(lèi)。決策樹(shù)的每個(gè)內(nèi)部節(jié)點(diǎn)表示在一個(gè)屬性上的測(cè)試，每個(gè)分枝代表該測(cè)試的一個(gè)輸出，而每個(gè)葉結(jié)點(diǎn)存放著一個(gè)類(lèi)標(biāo)號(hào)。 

    在決策樹(shù)算法中，ID3基于**信息增益**作為屬性選擇的度量，C4.5基于**信息增益比**作為屬性選擇的度量，CART基于**基尼指數(shù)**作為屬性選擇的度量。

    2）優(yōu)點(diǎn) ：
    不需要任何領(lǐng)域知識(shí)或參數(shù)假設(shè)。
    適合高維數(shù)據(jù)。
    簡(jiǎn)單易于理解。
    短時(shí)間內(nèi)處理大量數(shù)據(jù)，得到可行且效果較好的結(jié)果。
    3）缺點(diǎn)： 
    對(duì)于各類(lèi)別樣本數(shù)量不一致數(shù)據(jù)，信息增益偏向于那些具有更多數(shù)值的特征。
    易于過(guò)擬合。
    忽略屬性之間的相關(guān)性。

#3.支持向量機(jī)
    1）基礎(chǔ)思想：支持向量機(jī)把分類(lèi)問(wèn)題轉(zhuǎn)化為尋找分類(lèi)平面的問(wèn)題，并通過(guò)最大化分類(lèi)邊界點(diǎn)距離分類(lèi)平面的距離來(lái)實(shí)現(xiàn)分類(lèi)。

    2）優(yōu)點(diǎn) ：
    可以解決小樣本下機(jī)器學(xué)習(xí)的問(wèn)題。
    提高泛化性能。
    可以解決**文本分類(lèi)、文字識(shí)別、圖像分類(lèi)**等方面仍受歡迎。
    避免神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)選擇和局部極小的問(wèn)題。
    3）缺點(diǎn)：
    缺失數(shù)據(jù)敏感。
    內(nèi)存消耗大，難以解釋。

#4.K近鄰
    1）基礎(chǔ)思想：通過(guò)計(jì)算每個(gè)訓(xùn)練樣例到待分類(lèi)樣品的距離，取和待分類(lèi)樣品距離最近的K個(gè)訓(xùn)練樣例，K個(gè)樣品中哪個(gè)類(lèi)別的訓(xùn)練樣例占多數(shù)，則待分類(lèi)樣品就屬于哪個(gè)類(lèi)別。
    2）優(yōu)點(diǎn) ：
    適用于樣本容量比較大的分類(lèi)問(wèn)題
    3）缺點(diǎn)： 
    計(jì)算量太大
    對(duì)于樣本量較小的分類(lèi)問(wèn)題，會(huì)產(chǎn)生誤分。

#5.邏輯回歸（LR）
    1）基礎(chǔ)思想：回歸模型中，y是一個(gè)定型變量，比如y=0或1，logistic方法主要應(yīng)用于研究某些事件發(fā)生的概率。
    2）優(yōu)點(diǎn) ：
    速度快，**適合二分類(lèi)問(wèn)題。**
    簡(jiǎn)單易于理解，直接看到各個(gè)特征的權(quán)重。
    能容易地更新模型吸收新的數(shù)據(jù)。
    3）缺點(diǎn)： 
    對(duì)數(shù)據(jù)和場(chǎng)景的適應(yīng)能力有局限，不如決策樹(shù)算法適應(yīng)性那么強(qiáng)

• 知識(shí)點(diǎn)5：分類(lèi)的評(píng)判指標(biāo)
  準(zhǔn)確率和召回率經(jīng)常用于比較分類(lèi)器的性能，但不適合用來(lái)分析不平衡數(shù)據(jù)集。

  對(duì)于二元分類(lèi)，稀有類(lèi)通常記為正類(lèi)，而多數(shù)類(lèi)被認(rèn)為是負(fù)類(lèi)，下表匯總了分類(lèi)模型正確和不正確預(yù)測(cè)的實(shí)例數(shù)目的混淆矩陣。

  
  
  圖片發(fā)自簡(jiǎn)書(shū)App
  
  

  1）準(zhǔn)確率（precision rate）：TP/(TP+FP)
  2）召回率（recall rate）：TP/(TP+FN)

  對(duì)于不平衡類(lèi)的分類(lèi)器評(píng)價(jià)，使用ROC和AUC作為評(píng)價(jià)分類(lèi)器的指標(biāo)
  3）ROC曲線(xiàn)：
  ROC關(guān)注兩個(gè)指標(biāo)

  • True Positive Rate ( TPR，真正率 ) = TP / [ TP + FN] ，TPR與召回率大小相等。
  • False Positive Rate( FPR，假正率 ) = FP / [ FP + TN] ，
    在ROC 空間中，每個(gè)點(diǎn)的橫坐標(biāo)是FPR，縱坐標(biāo)是TPR

4）AUC值：AUC（Area Under Curve）被定義為ROC曲線(xiàn)下的面積，顯然這個(gè)面積的數(shù)值不會(huì)大于1。又由于ROC曲線(xiàn)一般都處于y=x這條直線(xiàn)的上方，所以AUC的取值范圍在0.5和1之間。使用AUC值作為評(píng)價(jià)標(biāo)準(zhǔn)是因?yàn)楹芏鄷r(shí)候ROC曲線(xiàn)并不能清晰的說(shuō)明哪個(gè)分類(lèi)器的效果更好，而AUC作為數(shù)值可以直觀(guān)的評(píng)價(jià)分類(lèi)器的好壞，值越大越好。

5）**如何避免過(guò)擬合？**

過(guò)擬合表現(xiàn)在訓(xùn)練數(shù)據(jù)上的誤差非常小，而在測(cè)試數(shù)據(jù)上誤差反而增大。其原因一般是模型過(guò)于復(fù)雜，過(guò)分得去擬合數(shù)據(jù)的噪聲和outliers。
常見(jiàn)的解決辦法是正則化是：增大數(shù)據(jù)集，正則化

正則化方法是指在進(jìn)行目標(biāo)函數(shù)或代價(jià)函數(shù)優(yōu)化時(shí)，在目標(biāo)函數(shù)或代價(jià)函數(shù)后面加上一個(gè)正則項(xiàng)，一般有L1正則與L2正則等。規(guī)則化項(xiàng)的引入，在訓(xùn)練（最小化cost）的過(guò)程中，當(dāng)某一維的特征所對(duì)應(yīng)的權(quán)重過(guò)大時(shí)，而此時(shí)模型的預(yù)測(cè)和真實(shí)數(shù)據(jù)之間距離很小，通過(guò)規(guī)則化項(xiàng)就可以使整體的cost取較大的值，從而在訓(xùn)練的過(guò)程中避免了去選擇那些某一維（或幾維）特征的權(quán)重過(guò)大的情況，即過(guò)分依賴(lài)某一維（或幾維）的特征。
L1正則與L2正則區(qū)別：
L1：計(jì)算絕對(duì)值之和，用以產(chǎn)生稀疏性（使參數(shù)矩陣中大部分元素變?yōu)?），因?yàn)樗荓0范式的一個(gè)最優(yōu)凸近似，容易優(yōu)化求解；
L2：計(jì)算平方和再開(kāi)根號(hào)，L2范數(shù)更多是防止過(guò)擬合，并且讓優(yōu)化求解變得穩(wěn)定很快速；
所以?xún)?yōu)先使用L2 norm是比較好的選擇。

• 知識(shí)點(diǎn)6：二叉樹(shù)（前、中、后遍歷）
  （這里的前中后是指的根節(jié)點(diǎn)的遍歷次序）
  1）前序遍歷（DLR），首先訪(fǎng)問(wèn)根結(jié)點(diǎn)，然后遍歷左子樹(shù)，最后遍歷右子樹(shù)；
  2）中序遍歷（LDR），首先遍歷左子樹(shù)，然后訪(fǎng)問(wèn)根結(jié)點(diǎn)，最后遍歷右子樹(shù)；
  3）后序遍歷（LRD），首先遍歷左子樹(shù)，然后訪(fǎng)問(wèn)遍歷右子樹(shù)，最后訪(fǎng)問(wèn)根結(jié)點(diǎn)。

3.png

• 知識(shí)點(diǎn)7：幾種基本排序算法

    1）冒泡排序（Bubble Sort） 
    相鄰兩個(gè)元素作比較，冒泡排序是穩(wěn)定的。算法時(shí)間復(fù)雜度是O(n^2)。
    基本思想：
    （1）第一輪比較，找出最大的元素；第二輪找出次大的元素......
    （2）若有N個(gè)元素進(jìn)行排序，一共比較N-1輪，第M輪要進(jìn)行N-M次比較。
    （3）代碼實(shí)現(xiàn)：
    static void BubbleSort(int[] arr){
          for (int times=1,times<=arr.length-1,times++)  //比較arr.length-1輪
          {
                for (int i=1,i<=arr.length-times,i++)  //每一輪比較arr.length-times次
                {
                      if (arr[i-1]>arr[i]){
                          temp=arr[i-1]
                          arr[i-1]=arr[i] 
                          arr[i]=temp
                      }
                }
          }
    }
  
    2）選擇排序（Select Sort） 
    用某一位置的元素依次與其它位置元素相比較。直接選擇排序是不穩(wěn)定的，算法平均時(shí)間復(fù)雜度是O(n^2)。
    基本思想：
    （1）第一輪比較完畢，出現(xiàn)最小值，第二輪比較完畢，出現(xiàn)次小值......
    （2）與冒泡算法一樣，若有N個(gè)元素進(jìn)行排序，一共比較N-1輪，第M輪要進(jìn)行N-M次比較。
    但是每一輪只交換一次數(shù)值
    （3）代碼實(shí)現(xiàn)：
       static void SelectSort(int[] arr){
          for (int times=0,times<=arr.length-1,times++)  //以索引為0的元素作為第一個(gè)元素，依次與其它元素進(jìn)行比較。
          {
                int minindex=times
                for (int i=times+1,i<=arr.length,i++)  //i代表索引為i的被比較元素，可以取到arr.length。
                {
                      if (arr[i]<arr[minindex]){
                          minindex=i             }
                }
                temp=arr[times]
                arr[times]=arr[minindex] 
                arr[minindex]=temp
          }
    }
    
    3）快速排序
    快速排序是對(duì)冒泡排序的一種改進(jìn)。
    快速排序是不穩(wěn)定的。最理想情況算法時(shí)間復(fù)雜度O(nlog2n)，最壞O(n ^2)。
    基本思想：
    （1）首先任意選擇一個(gè)元素作為初始元素key（一般取第一個(gè)元素）
    （2）從兩端開(kāi)始分別找：從右往左，尋找比key值小的元素交換位置；再?gòu)淖笸?，尋找比key值大的元素交換位置；
    （3）如此依次循環(huán)步驟1.2
  
    4）堆排序 
    堆排序是一種樹(shù)形選擇排序。
    堆排序是不穩(wěn)定的。算法時(shí)間復(fù)雜度O(nlog n)。
    基本思想：分為最大化堆和最小化堆。
  

Paste_Image.png

• 知識(shí)點(diǎn)8：統(tǒng)計(jì)學(xué)基礎(chǔ)知識(shí)
  1）四分位極差、左右偏分布、p值
  2）方差分析：用于兩個(gè)及兩個(gè)以上樣本均數(shù)差別的顯著性檢驗(yàn)，基本思想是：通過(guò)分析研究不同來(lái)源的變異對(duì)總變異的貢獻(xiàn)大小，從而確定控制變量對(duì)研究結(jié)果影響力的大小。
  3）主成分分析：是一種統(tǒng)計(jì)方法。通過(guò)正交變換將一組可能存在相關(guān)性的變量轉(zhuǎn)換為一組線(xiàn)性不相關(guān)的變量，轉(zhuǎn)換后的這組變量叫主成分。
  4）幸存者偏差：意思是指，當(dāng)取得資訊的渠道，僅來(lái)自于幸存者時(shí)（因?yàn)樗廊瞬粫?huì)說(shuō)話(huà)），此資訊可能會(huì)存在與實(shí)際情況不同的偏差。