首頁 > 其他 > 詳細

數據挖掘面試筆試 (8)

時間:2019-02-06 22:14:46      閱讀:2851      評論:0      收藏:0      [點我收藏+]

標簽:csdn   經驗   集合   輸入   rfi   最大的   問題:   edi   名稱   

【校招面經】機器學習與數據挖掘常見面試題整理 part3

四十一、請簡要說說EM算法

有時候因為樣本的產生和隱含變量有關(隱含變量是不能觀察的),而求模型的參數時一般采用最大似然估計,由于含有了隱含變量,所以對似然函數參數求導是求不出來的,這時可以采用EM算法來求模型的參數的(對應模型參數個數可能有多個),EM算法一般分為2步:   E步:選取一組參數,求出在該參數下隱含變量的條件概率值;   M步:結合E步求出的隱含變量條件概率,求出似然函數下界函數(本質上是某個期望函數)的最大值。   重復上面2步直至收斂。作者:史興

 

鏈接:https://www.zhihu.com/question/27976634/answer/39132183

 

理論:

簡版:猜(E-step),反思(M-step),重復;

啰嗦版:

你知道一些東西(觀察的到的數據), 你不知道一些東西(觀察不到的),你很好奇,想知道點那些不了解的東西。怎么辦呢,你就根據一些假設(parameter)先猜(E-step),把那些不知道的東西都猜出來,假裝你全都知道了; 然后有了這些猜出來的數據,你反思一下,更新一下你的假設(parameter), 讓你觀察到的數據更加可能(Maximize likelihood; M-stemp); 然后再猜,在反思,最后,你就得到了一個可以解釋整個數據的假設了。

1. 注意,你猜的時候,要盡可能的猜遍所有情況,然后求期望(Expected);就是你不能僅僅猜一個個例,而是要猜出來整個宇宙;

2. 為什么要猜,因為反思的時候,知道全部的東西比較好。(就是P(X,Z)要比P(X)好優化一些。Z是hidden states)

3. 最后你得到什么了?你得到了一個可以解釋數據的假設,可能有好多假設都能解釋數據,可能別的假設更好。不過沒關系,有總比沒有強,知足吧。(你陷入到local minimum了)

====

實踐:

背景:公司有很多領導=[A總,劉總,C總],同時有很多漂亮的女職員=[小甲,小章,小乙]。(請勿對號入座)你迫切的懷疑這些老總跟這些女職員有問題。為了科學的驗證你的猜想,你進行了細致的觀察。于是,

觀察數據:

1)A總,小甲,小乙一起出門了;

2)劉總,小甲,小章一起出門了;

3)劉總,小章,小乙一起出門了;

4)C總,小乙一起出門了;

收集到了數據,你開始了神秘的EM計算:

初始化,你覺得三個老總一樣帥,一樣有錢,三個美女一樣漂亮,每個人都可能跟每個人有關系。所以,每個老總跟每個女職員“有問題”的概率都是1/3;

這樣,(E step)借用我之前看到的一個例子來講一下EM算法吧。

現在一個班里有50個男生,50個女生,且男生站左,女生站右。我們假定男生的身高服從正態分布

技術分享圖片

,女生的身高則服從另一個正態分布:

技術分享圖片

。這時候我們可以用極大似然法(MLE),分別通過這50個男生和50個女生的樣本來估計這兩個正態分布的參數。

但現在我們讓情況復雜一點,就是這50個男生和50個女生混在一起了。我們擁有100個人的身高數據,卻不知道這100個人每一個是男生還是女生。

這時候情況就有點尷尬,因為通常來說,我們只有知道了精確的男女身高的正態分布參數我們才能知道每一個人更有可能是男生還是女生。但從另一方面去考量,我們只有知道了每個人是男生還是女生才能盡可能準確地估計男女各自身高的正態分布的參數。

這個時候有人就想到我們必須從某一點開始,并用迭代的辦法去解決這個問題:我們先設定男生身高和女生身高分布的幾個參數(初始值),然后根據這些參數去判斷每一個樣本(人)是男生還是女生,之后根據標注后的樣本再反過來重新估計參數。之后再多次重復這個過程,直至穩定。這個算法也就是EM算法。

 

作者:文兄

來源:https://www.zhihu.com/question/27976634/answer/154998358

1) A總跟小甲出去過了 1/2 * 1/3 = 1/6 次,跟小乙也出去了1/6次;(所謂的fractional count)

2)劉總跟小甲,小章也都出去了1/6次

3)劉總跟小乙,小章又出去了1/6次

4)C總跟小乙出去了1/3次

總計,A總跟小甲出去了1/6次,跟小乙也出去了1/6次 ; 劉總跟小甲,小乙出去了1/6次,跟小章出去了1/3次;C總跟小章出去了1/3次;

你開始跟新你的八卦了(M step),

A總跟小甲,小乙有問題的概率都是1/6 / (1/6 + 1/6) = 1/2;

劉總跟小甲,小乙有問題的概率是1/6 / (1/6+1/6+1/6+1/6) = 1/4; 跟小章有問題的概率是(1/6+1/6)/(1/6 * 4) = 1/2;

C總跟小乙有問題的概率是 1。

然后,你有開始根據最新的概率計算了;(E-step)

1)A總跟小甲出去了 1/2 * 1/2 = 1/4 次,跟小乙也出去 1/4 次;

2)劉總跟小甲出去了1/2 * 1/4 = 1/12 次, 跟小章出去了 1/2 * 1/2 = 1/4 次;

3)劉總跟小乙出去了1/2 * 1/4 = 1/12 次, 跟小章又出去了 1/2 * 1/2 = 1/4 次;

4)C總跟小乙出去了1次;

重新反思你的八卦(M-step):

A總跟小甲,小乙有問題的概率都是1/4/ (1/4 + 1/4) = 1/2;

B總跟小甲,小乙是 1/12 / (1/12 + 1/4 + 1/4 + 1/12) = 1/8 ; 跟小章是 3/4 ;

C總跟小乙的概率是1。

你繼續計算,反思,總之,最后,你得到了真相!(馬總表示我早就知道真相了)

你知道了這些老總的真相,可以開始學習機器翻譯了。

 

四十二、密度聚類

來源:https://www.cnblogs.com/pinard/p/6208966.html

DBSCAN的聚類定義很簡單:由密度可達關系導出的最大密度相連的樣本集合,即為我們最終聚類的一個類別,或者說一個簇。

這個DBSCAN的簇里面可以有一個或者多個核心對象。如果只有一個核心對象,則簇里其他的非核心對象樣本都在這個核心對象的?-鄰域里;如果有多個核心對象,則簇里的任意一個核心對象的?-鄰域中一定有一個其他的核心對象,否則這兩個核心對象無法密度可達。這些核心對象的?-鄰域里所有的樣本的集合組成的一個DBSCAN聚類簇。

那么怎么才能找到這樣的簇樣本集合呢?DBSCAN使用的方法很簡單,它任意選擇一個沒有類別的核心對象作為種子,然后找到所有這個核心對象能夠密度可達的樣本集合,即為一個聚類簇。接著繼續選擇另一個沒有類別的核心對象去尋找密度可達的樣本集合,這樣就得到另一個聚類簇。一直運行到所有核心對象都有類別為止。

 

四十三、決策樹計算樣例

注意信息增益率的計算:https://www.cnblogs.com/hermione1985/p/6750209.html

 

四十四、聚類數量的確定

https://blog.csdn.net/qq_15738501/article/details/79036255

確定聚類數k的方法有以下兩類。

1.手肘法

1.1 理論

手肘法的核心指標是SSE(sum of the squared errors,誤差平方和),

技術分享圖片

 

其中,Ci是第i個簇,p是Ci中的樣本點,mi是Ci的質心(Ci中所有樣本的均值),SSE是所有樣本的聚類誤差,代表了聚類效果的好壞。

       手肘法的核心思想是:隨著聚類數k的增大,樣本劃分會更加精細,每個簇的聚合程度會逐漸提高,那么誤差平方和SSE自然會逐漸變小。并且,當k小于真實聚類數時,由于k的增大會大幅增加每個簇的聚合程度,故SSE的下降幅度會很大,而當k到達真實聚類數時,再增加k所得到的聚合程度回報會迅速變小,所以SSE的下降幅度會驟減,然后隨著k值的繼續增大而趨于平緩,也就是說SSE和k的關系圖是一個手肘的形狀,而這個肘部對應的k值就是數據的真實聚類數。當然,這也是該方法被稱為手肘法的原因。

1.2 實踐

我們對預處理后數據.csv 中的數據利用手肘法選取最佳聚類數k。具體做法是讓k從1開始取值直到取到你認為合適的上限(一般來說這個上限不會太大,這里我們選取上限為8),對每一個k值進行聚類并且記下對于的SSE,然后畫出k和SSE的關系圖(毫無疑問是手肘形),最后選取肘部對應的k作為我們的最佳聚類數。python實現如下:

[python] view plain copy

  1. import pandas as pd  
  2. from sklearn.cluster import KMeans  
  3. import matplotlib.pyplot as plt  
  4.   
  5. df_features = pd.read_csv(r‘C:\預處理后數據.csv‘,encoding=‘gbk‘) # 讀入數據  
  6. ‘利用SSE選擇k‘  
  7. SSE = []  # 存放每次結果的誤差平方和  
  8. for k in range(1,9):  
  9.     estimator = KMeans(n_clusters=k)  # 構造聚類器  
  10.     estimator.fit(df_features[[‘R‘,‘F‘,‘M‘]])  
  11.     SSE.append(estimator.inertia_)  
  12. X = range(1,9)  
  13. plt.xlabel(‘k‘)  
  14. plt.ylabel(‘SSE‘)  
  15. plt.plot(X,SSE,‘o-‘)  
  16. plt.show()  

畫出的k與SSE的關系圖如下:

技術分享圖片

 

顯然,肘部對于的k值為4,故對于這個數據集的聚類而言,最佳聚類數應該選4

2. 輪廓系數法

2.1 理論

該方法的核心指標是輪廓系數(Silhouette Coefficient),某個樣本點Xi的輪廓系數定義如下:

                                                            

技術分享圖片

其中,a是Xi與同簇的其他樣本的平均距離,稱為凝聚度,b是Xi與最近簇中所有樣本的平均距離,稱為分離度。而最近簇的定義是

                                                     

技術分享圖片

 

其中p是某個簇Ck中的樣本。事實上,簡單點講,就是用Xi到某個簇所有樣本平均距離作為衡量該點到該簇的距離后,選擇離Xi最近的一個簇作為最近簇。

       求出所有樣本的輪廓系數后再求平均值就得到了平均輪廓系數。平均輪廓系數的取值范圍為[-1,1],且簇內樣本的距離越近,簇間樣本距離越遠,平均輪廓系數越大,聚類效果越好。那么,很自然地,平均輪廓系數最大的k便是最佳聚類數。

2.2 實踐

我們同樣使用2.1中的數據集,同樣考慮k等于1到8的情況,對于每個k值進行聚類并且求出相應的輪廓系數,然后做出k和輪廓系數的關系圖,選取輪廓系數取值最大的k作為我們最佳聚類系數,python實現如下:

[python] view plain copy

  1. import pandas as pd  
  2. from sklearn.cluster import KMeans  
  3. from sklearn.metrics import silhouette_score  
  4. import matplotlib.pyplot as plt  
  5.   
  6. df_features = pd.read_csv(r‘C:\Users\61087\Desktop\項目\爬蟲數據\預處理后數據.csv‘,encoding=‘gbk‘)  
  7. Scores = []  # 存放輪廓系數  
  8. for k in range(2,9):  
  9.     estimator = KMeans(n_clusters=k)  # 構造聚類器  
  10.     estimator.fit(df_features[[‘R‘,‘F‘,‘M‘]])  
  11.     Scores.append(silhouette_score(df_features[[‘R‘,‘F‘,‘M‘]],estimator.labels_,metric=‘euclidean‘))  
  12. X = range(2,9)  
  13. plt.xlabel(‘k‘)  
  14. plt.ylabel(‘輪廓系數‘)  
  15. plt.plot(X,Scores,‘o-‘)  
  16. plt.show()  

 

得到聚類數k與輪廓系數的關系圖:

                             

技術分享圖片

 

可以看到,輪廓系數最大的k值是2,這表示我們的最佳聚類數為2。但是,值得注意的是,從k和SSE的手肘圖可以看出,當k取2時,SSE還非常大,所以這是一個不太合理的聚類數,我們退而求其次,考慮輪廓系數第二大的k值4,這時候SSE已經處于一個較低的水平,因此最佳聚類系數應該取4而不是2。

       但是,講道理,k=2時輪廓系數最大,聚類效果應該非常好,那為什么SSE會這么大呢?在我看來,原因在于輪廓系數考慮了分離度b,也就是樣本與最近簇中所有樣本的平均距離。為什么這么說,因為從定義上看,輪廓系數大,不一定是凝聚度a(樣本與同簇的其他樣本的平均距離)小,而可能是b和a都很大的情況下b相對a大得多,這么一來,a是有可能取得比較大的。a一大,樣本與同簇的其他樣本的平均距離就大,簇的緊湊程度就弱,那么簇內樣本離質心的距離也大,從而導致SSE較大。所以,雖然輪廓系數引入了分離度b而限制了聚類劃分的程度,但是同樣會引來最優結果的SSE比較大的問題,這一點也是值得注意的。

總結

從以上兩個例子可以看出,輪廓系數法確定出的最優k值不一定是最優的,有時候還需要根據SSE去輔助選取,這樣一來相對手肘法就顯得有點累贅。因此,如果沒有特殊情況的話,我還是建議首先考慮用手肘法。

 

四十五、解決lr非線性問題

1. 分箱+one-hot+交叉相乘

2. 特征項加平方

3. gbdt+lr

 

四十六、集成決策樹與神經網絡

技術分享圖片

 

四十七、更多聚類算法

http://blog.chinaunix.net/uid-10289334-id-3758310.html

基于劃分聚類算法(partition clustering)

k-means:

是一種典型的劃分聚類算法,它用一個聚類的中心來代表一個簇,即在迭代過程中選擇的聚點不一定是聚類中的一個點,該算法只能處理數值型數據

k-modes:

K-Means算法的擴展,采用簡單匹配方法來度量分類型數據的相似度

k-prototypes:

結合了K-Means和K-Modes兩種算法,能夠處理混合型數據

k-medoids:

在迭代過程中選擇簇中的某點作為聚點,PAM是典型的k-medoids算法

CLARA:

CLARA算法在PAM的基礎上采用了抽樣技術,能夠處理大規模數據

CLARANS:

CLARANS算法融合了PAM和CLARA兩者的優點,是第一個用于空間數據庫的聚類算法

Focused CLARAN:

采用了空間索引技術提高了CLARANS算法的效率

PCM:

模糊集合理論引入聚類分析中并提出了PCM模糊聚類算法

基于層次聚類算法:

CURE:

采用抽樣技術先對數據集D隨機抽取樣本,再采用分區技術對樣本進行分區,然后對每個分區局部聚類,最后對局部聚類進行全局聚類

ROCK:

也采用了隨機抽樣技術,該算法在計算兩個對象的相似度時,同時考慮了周圍對象的影響

CHEMALOEN(變色龍算法):

首先由數據集構造成一個K-最近鄰圖Gk ,再通過一個圖的劃分算法將圖Gk 劃分成大量的子圖,每個子圖代表一個初始子簇,最后用一個凝聚的層次聚類算法反復合并子簇,找到真正的結果簇

SBAC:

SBAC算法則在計算對象間相似度時,考慮了屬性特征對于體現對象本質的重要程度,對于更能體現對象本質的屬性賦予較高的權值

BIRCH:

BIRCH算法利用樹結構對數據集進行處理,葉結點存儲一個聚類,用中心和半徑表示,順序處理每一個對象,并把它劃分到距離最近的結點,該算法也可以作為其他聚類算法的預處理過程

BUBBLE:

BUBBLE算法則把BIRCH算法的中心和半徑概念推廣到普通的距離空間

BUBBLE-FM:

BUBBLE-FM算法通過減少距離的計算次數,提高了BUBBLE算法的效率

基于密度聚類算法:

DBSCAN:

DBSCAN算法是一種典型的基于密度的聚類算法,該算法采用空間索引技術來搜索對象的鄰域,引入了“核心對象”和“密度可達”等概念,從核心對象出發,把所有密度可達的對象組成一個簇

GDBSCAN:

算法通過泛化DBSCAN算法中鄰域的概念,以適應空間對象的特點

DBLASD:

 

OPTICS:

OPTICS算法結合了聚類的自動性和交互性,先生成聚類的次序,可以對不同的聚類設置不同的參數,來得到用戶滿意的結果

FDC:

FDC算法通過構造k-d tree把整個數據空間劃分成若干個矩形空間,當空間維數較少時可以大大提高DBSCAN的效率

基于網格的聚類算法:

STING:

利用網格單元保存數據統計信息,從而實現多分辨率的聚類

WaveCluster:

在聚類分析中引入了小波變換的原理,主要應用于信號處理領域。(備注:小波算法在信號處理,圖形圖像,加密解密等領域有重要應用,是一種比較高深和牛逼的東西)

CLIQUE:

是一種結合了網格和密度的聚類算法

OPTIGRID:

 

基于神經網絡的聚類算法:

自組織神經網絡SOM:

該方法的基本思想是--由外界輸入不同的樣本到人工的自組織映射網絡中,一開始時,輸入樣本引起輸出興奮細胞的位置各不相同,但自組織后會形成一些細胞群,它們分別代表了輸入樣本,反映了輸入樣本的特征

基于統計學的聚類算法:

COBWeb:

COBWeb是一個通用的概念聚類方法,它用分類樹的形式表現層次聚類

CLASSIT:

 

AutoClass:

是以概率混合模型為基礎,利用屬性的概率分布來描述聚類,該方法能夠處理混合型的數據,但要求各屬性相互獨立

---------------------------------------------------------

幾種常用的聚類算法從可伸縮性、適合的數據類型、高維性(處理高維數據的能力)、異常數據的抗干擾度、聚類形狀和算法效率6個方面進行了綜合性能評價,評價結果如表1所示:

 

算法名稱

可伸縮性

適合的數據類型

高維性

異常數據的抗干擾性

聚類形狀

算法效率

WaveCluster

很高

數值型

很高

較高

任意形狀

很高

ROCK 

很高 

混合型 

很高

很高 

任意形狀

一般

BIRCH

較高 

數值型 

較低 

較低 

球形 

很高

CURE 

較高 

數值型 

一般 

很高 

任意形狀 

較高

K-Prototypes 

一般 

混合型 

較低 

較低 

任意形狀 

一般

DENCLUE 

較低 

數值型 

較高 

一般 

任意形狀 

較高

OptiGrid 

一般 

數值型 

較高 

一般 

任意形狀 

一般

CLIQUE 

較高 

數值型 

較高 

較高 

任意形狀 

較低

DBSCAN 

一般 

數值型 

較低 

較高 

任意形狀 

一般

CLARANS 

較低 

數值型 

較低  

較高 

球形  

較低

 

四十八、負采樣

負采樣

訓練一個神經網絡意味著使用一個訓練樣本就要稍微調整一下所有的神經網絡權重,這樣才能夠確保預測訓練樣本更加精確。換句話說,每個訓練樣本都會改變神經網絡中的權重。

正如我們上面討論的,單詞表的大小意味著我們的skip-gram神經網絡擁有非常龐大的權重數,所有權重都會被十億個樣本中的一個稍微地進行更新!

負采樣通過使每一個訓練樣本僅僅改變一小部分的權重而不是所有權重,從而解決這個問題。下面介紹它是如何進行工作的。

當通過(”fox”, “quick”)詞對來訓練神經網絡時,我們回想起這個神經網絡的“標簽”或者是“正確的輸出”是一個one-hot向量。也就是說,對于神經網絡中對應于”quick”這個單詞的神經元對應為1,而其他上千個的輸出神經元則對應為0。

使用負采樣,我們通過隨機選擇一個較少數目(比如說5個)的“負”樣本來更新對應的權重。(在這個條件下,“負”單詞就是我們希望神經網絡輸出為0的神經元對應的單詞)。并且我們仍然為我們的“正”單詞更新對應的權重(也就是當前樣本下”quick”對應的神經元)。

論文說選擇5~20個單詞對于較小的樣本比較合適,而對于大樣本,我們可以懸著2~5個單詞。

回想一下,我們模型的輸出層有大約300 x 10,000維度的權重矩陣。所以我們只需要更新正確的輸出單詞”quick”的權重,加上額外的5個其他應該輸出為0的單詞的權重。也就是總共6個輸出神經元,和總共1800個的權重值。這些總共僅僅是輸出層中3百萬個權重中的0.06%。

在隱藏層中,只更新了輸入單詞對應的權重(不論你是否使用了復采樣)。

選擇負采樣樣本

“復采樣樣本”(也就是我們需要訓練的五個輸出為0單詞)使用“一元分部”(“unigram distribution”)來進行選取。

從本質上來說,選擇一個單詞來作為負樣本的概率取決于它出現頻率,對于更經常出現的單詞,我們將更傾向于選擇它為負樣本。

在使用C語言實現的詞轉向量(word2vec)中,你可以看到這個概率公式。每個單詞都被給予一個等于它頻率的權重(單詞出現的數目)的3/4次方。選擇某個單詞的概率就是它的權重除以所有單詞權重之和。

技術分享圖片

使用頻率的3/4次方顯然是根據經驗來的;在他們的文章中,他們說到這個公式比其他函數的表現更為優秀。你可以通過在谷歌中輸入: plot y = x^(3/4) and y = x并且調整焦距為x = [0, 1]范圍。當我們增加數值一點點的時候它的圖像有一點小彎曲。

使用C語言來實現這個樣本選擇的實現很有意思。他們有一個1億元素大小的數組(每一個都相當于一個一元模型的表格)。表格中通過索引來多次記錄每一個在單詞表中出現的單詞,在這里單詞指標大小通過 P(wi) * table_size 來表達。其次,為了切實選擇一個負樣本,你僅僅只需要創造一個0到1億的隨機整數樣本,并且使用這個數字在表格中索引的單詞。由于更高概率的單詞在表格中出現的次數會更多,所以你將更傾向于選擇到它們。

 

四十九、防止過擬合的方法

1. 正則l1l2

2. dropout(或者subsample)

3. 特征選擇、特征降維

4. 增加數據

5. 早停

6. 調參(剪枝、增加分類平面等)

7. ensemble

 

五十、sigmoid的導數

技術分享圖片

數據挖掘面試筆試 (8)

標簽:csdn   經驗   集合   輸入   rfi   最大的   問題:   edi   名稱   

原文:https://www.cnblogs.com/yumoye/p/10354146.html

(0)
(0)
   
舉報
評論 一句話評論(0
登錄后才能評論!
? 2014 bubuko.com 版權所有 魯ICP備09046678號-4
打開技術之扣,分享程序人生!
             

魯公網安備 37021202000002號

湖南快乐十分钟走势图