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

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

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

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

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

  1.png

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

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

  系統(tǒng)聚類適用于小樣本艘希。

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

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

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


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

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

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

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

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

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

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

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

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

  
  
  圖片發(fā)自簡書App
  
  

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

  對(duì)于不平衡類的分類器評(píng)價(jià)埂蕊，使用ROC和AUC作為評(píng)價(jià)分類器的指標(biāo)
  3）ROC曲線：
  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曲線下的面積顿天，顯然這個(gè)面積的數(shù)值不會(huì)大于1堂氯。又由于ROC曲線一般都處于y=x這條直線的上方，所以AUC的取值范圍在0.5和1之間牌废。使用AUC值作為評(píng)價(jià)標(biāo)準(zhǔn)是因?yàn)楹芏鄷r(shí)候ROC曲線并不能清晰的說明哪個(gè)分類器的效果更好咽白，而AUC作為數(shù)值可以直觀的評(píng)價(jià)分類器的好壞，值越大越好鸟缕。

5）**如何避免過擬合晶框？**

過擬合表現(xiàn)在訓(xùn)練數(shù)據(jù)上的誤差非常小排抬，而在測試數(shù)據(jù)上誤差反而增大。其原因一般是模型過于復(fù)雜授段，過分得去擬合數(shù)據(jù)的噪聲和outliers蹲蒲。
常見的解決辦法是正則化是：增大數(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）的過程中卡睦，當(dāng)某一維的特征所對(duì)應(yīng)的權(quán)重過大時(shí)，而此時(shí)模型的預(yù)測和真實(shí)數(shù)據(jù)之間距離很小漱抓，通過規(guī)則化項(xiàng)就可以使整體的cost取較大的值表锻，從而在訓(xùn)練的過程中避免了去選擇那些某一維（或幾維）特征的權(quán)重過大的情況，即過分依賴某一維（或幾維）的特征辽旋。
L1正則與L2正則區(qū)別：
L1：計(jì)算絕對(duì)值之和浩嫌，用以產(chǎn)生稀疏性（使參數(shù)矩陣中大部分元素變?yōu)?），因?yàn)樗荓0范式的一個(gè)最優(yōu)凸近似补胚，容易優(yōu)化求解码耐；
L2：計(jì)算平方和再開根號(hào)，L2范數(shù)更多是防止過擬合溶其，并且讓優(yōu)化求解變得穩(wěn)定很快速骚腥；
所以優(yōu)先使用L2 norm是比較好的選擇。

• 知識(shí)點(diǎn)6：二叉樹（前瓶逃、中束铭、后遍歷）
  （這里的前中后是指的根節(jié)點(diǎn)的遍歷次序）
  1）前序遍歷（DLR），首先訪問根結(jié)點(diǎn)厢绝，然后遍歷左子樹契沫，最后遍歷右子樹；
  2）中序遍歷（LDR）昔汉，首先遍歷左子樹懈万，然后訪問根結(jié)點(diǎn)，最后遍歷右子樹靶病；
  3）后序遍歷（LRD）会通，首先遍歷左子樹，然后訪問遍歷右子樹娄周，最后訪問根結(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）從兩端開始分別找：從右往左冯吓，尋找比key值小的元素交換位置倘待；再從左往右，尋找比key值大的元素交換位置组贺；
    （3）如此依次循環(huán)步驟1.2
  
    4）堆排序 
    堆排序是一種樹形選擇排序凸舵。
    堆排序是不穩(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)，基本思想是：通過分析研究不同來源的變異對(duì)總變異的貢獻(xiàn)大小整以，從而確定控制變量對(duì)研究結(jié)果影響力的大小胧辽。
  3）主成分分析：是一種統(tǒng)計(jì)方法。通過正交變換將一組可能存在相關(guān)性的變量轉(zhuǎn)換為一組線性不相關(guān)的變量公黑，轉(zhuǎn)換后的這組變量叫主成分邑商。
  4）幸存者偏差：意思是指摄咆，當(dāng)取得資訊的渠道，僅來自于幸存者時(shí)（因?yàn)樗廊瞬粫?huì)說話）人断，此資訊可能會(huì)存在與實(shí)際情況不同的偏差吭从。