【算法崗面試】某小廠E機(jī)器學(xué)習(xí)

文章目錄

1.deepFM的FM特點(diǎn)，deep部分設(shè)置了多少層，依據(jù)

2.算法題：爬樓梯

3.算法題：最大子數(shù)組和

4.sql題：商品id、類別、價(jià)格，mysql找出找出每類前10大的商品

5.1000個(gè)學(xué)生成績(jī)排序，比快排更快的方法

6.常用的數(shù)據(jù)預(yù)處理有哪些操作

7.transformer的文本抽取

8.反欺詐（風(fēng)控）的分類算法

9.大數(shù)據(jù)spark和hadoop

（1）Scala和PySpark

（2）Spark原理

（3）一個(gè)具體栗子

Reference

1.deepFM的FM特點(diǎn)，deep部分設(shè)置了多少層，依據(jù)

FM模型的FM使用了隱向量特征交叉。

為了解決POLY2模型的缺陷，2010年提出FM模型。如下式子是FM（Factor Machine，因子分解機(jī)）二階部分的數(shù)學(xué)表達(dá)式 ? FM ? ( w , x ) = ∑ j 1 = 1 n ∑ j 2 = j 1 + 1 n ( w j 1 ? w j 2 ) x j 1 x j 2 \emptyset \operatorname{FM}(\boldsymbol{w}, \boldsymbol{x})=\sum_{j_{1}=1}^{n} \sum_{j_{2}=j_{1}+1}^{n}\left(\boldsymbol{w}_{j_{1}} \cdot \boldsymbol{w}_{j_{2}}\right) x_{j_{1}} x_{j_{2}} ?FM(w,x)=j1 =1∑n j2 =j1 +1∑n (wj1 ?wj2 )xj1 xj2

FM和POLY2的區(qū)別是，F(xiàn)M用兩個(gè)向量的內(nèi)積 ( w j 1 ? w j 2 ) \left(\boldsymbol{w}_{j_{1}} \cdot \boldsymbol{w}_{j_{2}}\right) (wj1 ?wj2 )取代了單一的權(quán)重系數(shù) W h ( j 1 , j 2 ) W_{h\left(j_{1}, j_{2}\right)} Wh(j1 ,j2 ) 。

FM權(quán)重參數(shù)量少了，降低訓(xùn)練開銷；

FM雖然丟失了某些具體特征組合的精確記憶能力，但泛化能力大大提高。

FM的二階以上交叉沒有很強(qiáng)的意義，因?yàn)闆]法加速。

FM為每個(gè)特征學(xué)習(xí)了一個(gè)隱權(quán)重向量

（和矩陣分解，用隱向量代表 user 和 item 思想一樣，

從單純的 user、item隱向量擴(kuò)展到了所有特征上）。在特征交叉時(shí)，使用兩個(gè)特征隱向量的內(nèi)積作為交叉特征的權(quán)重

。

FM引入隱向量，更好解決數(shù)據(jù)稀疏性問(wèn)題，ex：

商品推薦場(chǎng)景，樣本有兩個(gè)特征：頻道（channel）和品牌（brand），某訓(xùn)練樣本的特征組合是（ESPN, Adidas）。

在POLY2中，只有當(dāng)ESPN和Adidas同時(shí)出現(xiàn)在一個(gè)訓(xùn)練樣本時(shí)，模型才能學(xué)習(xí)到這個(gè)組合特征對(duì)應(yīng)的權(quán)重；

在FM中，ESPN的隱向量也可以通過(guò)（ESPN, Gucci）樣本進(jìn)行更新，Adidas的隱向量也可以通過(guò)（NBC, Adidas）樣本進(jìn)行更新，即大幅降低模型，對(duì)數(shù)據(jù)稀疏性的要求。

deep設(shè)置了3層。層數(shù)要根據(jù)具體網(wǎng)絡(luò)，如GCN就不能太深，否則會(huì)導(dǎo)致拉普拉斯平滑問(wèn)題。這里設(shè)置3層解決非線性的問(wèn)題。

2.算法題：爬樓梯

其實(shí)就是青蛙跳臺(tái)階的題目：

d p [ i ] dp[i] dp[i]是青蛙跳上一個(gè)n級(jí)的臺(tái)階總共跳法數(shù)。

class Solution { public: int numWays(int n) { vectordp(n+1,0); if(n==0) return 1;//否則當(dāng)n=0時(shí)下面這句的dp[1]就訪問(wèn)越界了 dp[0]=dp[1]=1; for(int i=2;i<=n;i++){ dp[i]=(dp[i-1]+dp[i-2])% 1000000007; } return dp[n]; } };

1

2

3

4

5

6

7

8

9

10

11

12

遞歸寫法：

int fib(int N) { if (N == 1 || N == 2) return 1; return fib(N - 1) + fib(N - 2); }

1

2

3

4

3.算法題：最大子數(shù)組和

定義狀態(tài)：dp[i]表示nums中以nums[i]結(jié)尾子數(shù)組的最大子序和。

確定狀態(tài)轉(zhuǎn)移方程：對(duì)dp[i - 1]進(jìn)行分類討論：

大于0則將當(dāng)前的nums[i]加到dp[i - 1]上（因?yàn)椴还躰ums[i]是大于0還是小于0，以nums[i]為結(jié)尾的子數(shù)組的最大子序和，都是要加上這個(gè)數(shù)的，注意定義好的狀態(tài)）。

小于0則另起爐灶，即dp[i] = nums[i]。

d p [ i ] = { d p [ i ? 1 ] + n u m s [ i ] , ?if? d p [ i ? 1 ] > 0 ?nums? [ i ] , ?if? d p [ i ? 1 ] ≤ 0 d p[i]=\left\{\begin{array}{lll} d p[i-1]+n u m s[i], & \text { if } & d p[i-1]>0 \ \text { nums }[i], & \text { if } & d p[i-1] \leq 0 \end{array}\right. dp[i]={dp[i?1]+nums[i],?nums?[i], ?if??if? dp[i?1]>0dp[i?1]≤0 寫成max的形式就不用分類討論了： d p [ i ] = max ? { n u m s [ i ] , d p [ i ? 1 ] + n u m s [ i ] } d p[i]=\max \{n u m s[i], d p[i-1]+n u m s[i]\} dp[i]=max{nums[i],dp[i?1]+nums[i]}

邊界+初始條件：只有一個(gè)數(shù)字時(shí)dp[0] = nums[0]。

計(jì)算順序：從小到大。

4.sql題：商品id、類別、價(jià)格，mysql找出找出每類前10大的商品

建表：

START TRANSACTION; CREATE TABLE employee ( name text, department text, salary bigint ); INSERT INTO employee VALUES ( 'alice', 'it', 1000 ); INSERT INTO employee VALUES ( 'bob', 'it', 2000 ); INSERT INTO employee VALUES ( 'david', 'it', 3000 ); INSERT INTO employee VALUES ( 'john', 'it', 2000 ); INSERT INTO employee VALUES ( 'mike', 'it', 9000 ); INSERT INTO employee VALUES ( 'henry', 'sales', 500000 ); INSERT INTO employee VALUES ( 'jason', 'sales', 9999999 ); COMMIT;

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

給每個(gè)部門的人，根據(jù)薪資進(jìn)行部門內(nèi)排序，可以使用窗口函數(shù)，對(duì)部門分類，對(duì)部門內(nèi)排序DENSE_RANK（無(wú)間隔的分級(jí)）：

SELECT *, DENSE_RANK() OVER( PARTITION BY department ORDER BY salary DESC ) AS innerrank FROM employee;

1

2

3

4

5

最后：

SELECT * FROM ( SELECT *, DENSE_RANK() OVER( PARTITION BY department ORDER BY salary DESC ) AS innerrank FROM employee ) AS t WHERE innerrank <= 3;

1

2

3

4

5

6

7

5.1000個(gè)學(xué)生成績(jī)排序，比快排更快的方法

面試官說(shuō)沒有學(xué)生ID，最后輸出排序后的學(xué)生成績(jī)就好。

聽了就懵了，還有比快排更快的方法？！說(shuō)了一個(gè)哈希表的方法（不太確定）， 以學(xué)生成績(jī)?yōu)閗ey值，以key為成績(jī)的學(xué)生個(gè)數(shù)作為哈希表的value值。然后因?yàn)镃++的STL中的map底層用了紅黑樹，排序一波會(huì)更快。

6.常用的數(shù)據(jù)預(yù)處理有哪些操作

去除唯一屬性、處理缺失值、屬性編碼、數(shù)據(jù)標(biāo)準(zhǔn)化正則化、特征選擇、主成分分析。

缺失值處理：

直接使用含有缺失值的特征

刪除含有缺失值的特征（該方法在包含缺失值的屬性含有大量缺失值而僅僅包含極少量有效值時(shí)是有效的）

缺失值補(bǔ)全：如果樣本屬性的距離是可度量的，則使用該屬性有效值的平均值來(lái)插補(bǔ)缺失的值

高維映射（最精確）：將屬性映射到高維空間，采用獨(dú)熱碼編碼（one-hot）。

將包含K個(gè)離散取值范圍的屬性值擴(kuò)展為K+1個(gè)屬性值

，若該屬性值缺失，則擴(kuò)展后的第K+1個(gè)屬性值置為1。

建模預(yù)測(cè)：將缺失的屬性作為預(yù)測(cè)目標(biāo)來(lái)預(yù)測(cè)，將數(shù)據(jù)集按照是否含有特定屬性的缺失值分為兩類，利用現(xiàn)有的機(jī)器學(xué)習(xí)算法對(duì)待預(yù)測(cè)數(shù)據(jù)集的缺失值進(jìn)行預(yù)測(cè)。

數(shù)據(jù)標(biāo)準(zhǔn)化（歸一化）：樣本屬性值縮放為一定范圍，如min-max標(biāo)準(zhǔn)化映射結(jié)果為0到1的區(qū)間中。

正則化

特征選擇（降維）：從給定的特征集合中選出相關(guān)特征子集。這是為了減輕維數(shù)災(zāi)難問(wèn)題，降低學(xué)習(xí)任務(wù)的難度。常見降維方法：SVD、PCA、LDA。

7.transformer的文本抽取

類似作QA的bert模型可以。

8.反欺詐（風(fēng)控）的分類算法

LR、GBDT / XGBoost分類

9.大數(shù)據(jù)spark和hadoop

（1）Scala和PySpark

（1）Scala 是一門多范式（multi-paradigm）的編程語(yǔ)言，設(shè)計(jì)初衷是要集成面向?qū)ο缶幊毯秃瘮?shù)式編程的各種特性。

Scala 運(yùn)行在 Java 虛擬機(jī)上，并兼容現(xiàn)有的 Java 程序。

Scala 源代碼被編譯成 Java 字節(jié)碼，所以它可以運(yùn)行于 JVM 之上，并可以調(diào)用現(xiàn)有的 Java 類庫(kù)。

（2）Apache Spark是用 Scala編程語(yǔ)言 編寫的。為了用Spark支持Python，Apache Spark社區(qū)發(fā)布了一個(gè)工具PySpark。使用PySpark，也可以使用Python編程語(yǔ)言中的 RDD 。

（3）PySpark提供了 PySpark Shell，它將Python API鏈接到spark核心并初始化Spark上下文。將Python與Spark集成就對(duì)數(shù)據(jù)科學(xué)研究更加方便。

Spark的開發(fā)語(yǔ)言是Scala，這是Scala在并行和并發(fā)計(jì)算方面優(yōu)勢(shì)的體現(xiàn)，這是微觀層面函數(shù)式編程思想的一次勝利。此外，Spark在很多宏觀設(shè)計(jì)層面都借鑒了函數(shù)式編程思想，如接口、惰性求值和容錯(cuò)等。

（2）Spark原理

Spark是業(yè)界主流的大數(shù)據(jù)處理利器。

分布式：指的是計(jì)算節(jié)點(diǎn)之間不共享內(nèi)存，需要通過(guò)網(wǎng)絡(luò)通信的方式交換數(shù)據(jù)。

Spark 是一個(gè)分布式計(jì)算平臺(tái)。Spark 最典型的應(yīng)用方式就是建立在大量廉價(jià)的計(jì)算節(jié)點(diǎn)上，

這些節(jié)點(diǎn)可以是廉價(jià)主機(jī)，也可以是虛擬的 Docker Container（Docker 容器）

。

Spark 的架構(gòu)圖中：

Spark 程序由 Manager Node（管理節(jié)點(diǎn)）進(jìn)行調(diào)度組織

由 Worker Node（工作節(jié)點(diǎn)）進(jìn)行具體的計(jì)算任務(wù)執(zhí)行

最終將結(jié)果返回給 Drive Program（驅(qū)動(dòng)程序）。

在物理的 Worker Node 上，數(shù)據(jù)還會(huì)分為不同的 partition（數(shù)據(jù)分片），可以說(shuō) partition 是 Spark 的基礎(chǔ)數(shù)據(jù)單元。

Spark 計(jì)算集群能夠比傳統(tǒng)的單機(jī)高性能服務(wù)器具備更強(qiáng)大的計(jì)算能力，就是由這些成百上千，甚至達(dá)到萬(wàn)以上規(guī)模的工作節(jié)點(diǎn)并行工作帶來(lái)的。

（3）一個(gè)具體栗子

那在執(zhí)行一個(gè)具體任務(wù)的時(shí)候，Spark 是怎么協(xié)同這么多的工作節(jié)點(diǎn)，通過(guò)并行計(jì)算得出最終的結(jié)果呢？這里我們用一個(gè)任務(wù)來(lái)解釋一下 Spark 的工作過(guò)程。

一個(gè)具體任務(wù)過(guò)程：

（1）先從本地硬盤讀取文件 textFile；

（2）再?gòu)姆植际轿募到y(tǒng) HDFS 讀取文件 hadoopFile；

（3）然后分別對(duì)它們進(jìn)行處理；

（4）再把兩個(gè)文件按照 ID 都 join 起來(lái)得到最終的結(jié)果。

在 Spark 平臺(tái)上處理這個(gè)任務(wù)的時(shí)候，會(huì)將這個(gè)任務(wù)拆解成一個(gè)子任務(wù) DAG（Directed Acyclic Graph，有向無(wú)環(huán)圖），再根據(jù) DAG 決定程序各步驟執(zhí)行的方法。從圖 2 中可以看到，這個(gè) Spark 程序分別從 textFile 和 hadoopFile 讀取文件，再經(jīng)過(guò)一系列 map、filter 等操作后進(jìn)行 join，最終得到了處理結(jié)果。

最關(guān)鍵的過(guò)程是要理解

哪些是可以純并行處理的部分，哪些是必須 shuffle（混洗）和 reduce 的部分

：這里的 shuffle 指的是所有 partition 的數(shù)據(jù)必須進(jìn)行洗牌后才能得到下一步的數(shù)據(jù)，最典型的操作就是圖 2 中的 groupByKey 操作和 join 操作。以 join 操作為例，必須對(duì) textFile 數(shù)據(jù)和 hadoopFile 數(shù)據(jù)做全量的匹配才可以得到 join 后的 dataframe（Spark 保存數(shù)據(jù)的結(jié)構(gòu)）。而 groupByKey 操作則需要對(duì)數(shù)據(jù)中所有相同的 key 進(jìn)行合并，也需要全局的 shuffle 才能完成。

與之相比，map、filter 等操作僅需要逐條地進(jìn)行數(shù)據(jù)處理和轉(zhuǎn)換，不需要進(jìn)行數(shù)據(jù)間的操作，因此各 partition 之間可以完全并行處理。

在得到最終的計(jì)算結(jié)果之前，程序需要進(jìn)行 reduce 的操作，從各 partition 上匯總統(tǒng)計(jì)結(jié)果，隨著 partition 的數(shù)量逐漸減小，reduce 操作的并行程度逐漸降低，直到將最終的計(jì)算結(jié)果匯總到 master 節(jié)點(diǎn)（主節(jié)點(diǎn)）上。可以說(shuō)，shuffle 和 reduce 操作的觸發(fā)決定了純并行處理階段的邊界。

注意：

（1）

shuffle 操作需要在不同計(jì)算節(jié)點(diǎn)之間進(jìn)行數(shù)據(jù)交換，非常消耗計(jì)算、通信及存儲(chǔ)資源

，因此 shuffle 操作是 spark 程序應(yīng)該盡量避免的。shuffle可以理解為一個(gè)串行操作，需要等到在此之前的并行工作完成之后才可以順序開始。

（2）簡(jiǎn)述Spark 的計(jì)算過(guò)程：Stage 內(nèi)部數(shù)據(jù)高效并行計(jì)算，Stage 邊界處進(jìn)行消耗資源的 shuffle 操作或者最終的 reduce 操作。

Reference

[1] https://zhuanlan.zhihu.com/p/341148358

[2] 一篇文章搞懂機(jī)器學(xué)習(xí)風(fēng)控建模過(guò)程

[3] 風(fēng)控8個(gè)場(chǎng)景中的機(jī)器學(xué)習(xí)應(yīng)用

[4] 機(jī)器學(xué)習(xí)算法原理系列篇1：金融風(fēng)控中的機(jī)器學(xué)習(xí)

[5] 數(shù)據(jù)預(yù)處理（方法總結(jié)）

機(jī)器學(xué)習(xí)

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實(shí)的內(nèi)容，請(qǐng)聯(lián)系我們jiasou666@gmail.com 處理，核實(shí)后本網(wǎng)站將在24小時(shí)內(nèi)刪除侵權(quán)內(nèi)容。

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實(shí)的內(nèi)容，請(qǐng)聯(lián)系我們jiasou666@gmail.com 處理，核實(shí)后本網(wǎng)站將在24小時(shí)內(nèi)刪除侵權(quán)內(nèi)容。