# ADL 2022 Final Project - Hahow Grand Challenge
* Team name : `team_18_waywaybaobao`
* Team member
* `傅立威 R10942078`
* `吳政彥 R10522801`
* `陳俊憲 R10246002`
* `劉智皓 R10941036`

## Task Description
Hahow是一家在台灣的教育科技公司，致力於通過網路課程的方式，幫助人們學習新技能和提升專業能力。Hahow提供了各種類型的課程，包括設計、美食、攝影、影視製作、程式設計等。而本次專題要分析Hahow提供的用戶資料、用戶於2021年1~12月的購買紀錄、線上課程的介紹等資訊來**預測未知用戶在2021年11、12月可能會購買的課程與該課程的子分類**。因此需要實作一個推薦系統，透過分析用戶與課程之間的關聯性來推薦用戶在11、12月可能感興趣並有意願購買的課程，而推薦的課程需照購買意願由高排到低。

## Related Work
由於本次專題需要實作推薦系統，因此我們經過多方蒐集資料得知有許多不同的方式，以下列舉目前常見的方法:
1. `基於內容的推薦 (Content-based Recommendation)`: 這種方法基於用戶以往的喜好或者物品的內容來推薦物品。比如，如果用戶喜歡看動作片，那麼系統就會推薦其他的動作片。
2. `基於協同過濾的推薦 (Collaborative Filtering Recommendation)`: 這種方法基於用戶與用戶之間的交互來推薦物品。比如，如果用戶A和用戶B都喜歡看動作片，那麼系統就會推薦用戶B喜歡的動作片給用戶A。
3. `基於類比的推薦 (Demographic Filtering)`: 這種方法基於用戶的人口統計學特徵，比如年齡、性別、地區等，來推薦物品。
4. `基於深度學習的推薦 (Deep Learning Recommendation)`: 這種方法使用深度學習模型來自動特徵工程，並通過學習用戶和物品之間的交互來進行推薦。

## Exploratory Data Analysis
* ### Gender
最多人填寫 (65%)，但透過一些相關性分析與測試發現性別和用戶購買的課程關聯不大，因此不是我們要用來訓練模型的特徵。
* ### Occupation_titles
在填寫職業欄位的部分可以複選最多3個，但在users.csv中最少人填寫 (20%)，因此也不是我們要用來訓練模型的特徵。
* ### Interests
第二多人有填寫 (64%)，且有幾個特定的興趣與用戶購買的課程有高度相關，因此是我們要用來訓練模型的特徵。
* ### Recreation_names
倒數第二多人有填寫 (24%)，與用戶購買的課程相關性不大，因此不是我們要用來訓練模型的特徵。

## Approach
* ### Data Preprocessing
* #### One-hot encoding
將輸入使用者的興趣拆分成Group與Subgroup，再將Subgroup使用One-hot編碼的方式作為輸入的特徵，在Course Prediction與Subgroup Prediction這兩項任務都可做此資料前處理。

`Course Prediction` : 由於Course總共有728堂，再加上`NaN`，因此每個使用者的輸入特徵會是大小為`729×1`的向量。以使用者編號為`5bdecbfffec014002166796a`為例，該使用者在2021 1~7月購買課程為`5f194354cad0d086f3ee24cf`，因此其輸入特徵向量會是:

`Subgroup Prediction` : 由於興趣中的Subgroup總共有95個，再加上`NaN`，因此每個使用者的輸入特徵會是大小為`96×1`的向量。以使用者編號為`5bdb45c29d9ad40020e1e8ff`為例，該使用者興趣為`語言_英文`，在我們興趣的Subgroup編排中為27，因此其輸入特徵向量會是:

* #### Remove 20 least bought subgroups
雖然在訓練資料集中總共有91種課程的Subgroup，但將每個Subgroup的被購買次數由小到大排序，會發現在橫軸方向約20的地方有一個小凸起，小於這個凸點約有20個課程的Subgroup，這些Subgroup被購買的次數偏低。如下圖所示:

為了避免這些購買次數偏低的Subgroup出現在模型推薦的課程中，我們在資料前處理時移除這20個課程Subgroup，分別為手工書、氣球、數學、手工印刷、攝影理論、更多音樂、DJ、翻譯、護膚保養與化妝、手機程式開發、歐洲語言、更多攝影、更多行銷、資訊安全、音樂理論、數據分析、更多程式、遊戲開發、素描、更多手作。如此一來，我們要訓練的模型就能針對這71個相較熱門的Subgroup進行預測。

* #### Feature Engineering
由於許多訓練模型只能完成單標籤分類的任務，但許多使用者會購買一個以上的課程，甚至有些課程本來就包含多種Subgroup，導致Label不會只有一個，因此我們根據其購買的課程種類數量，來新增多個資料。以使用者編號`5a0bde2aa15b3f001e98429a`為例，該使用者購買的課程Subgroup包含1、59、60、71、79，所以我們在資料前處理時，將這一筆資料對應到複製5次，將這新增5筆資料的Lable分別對應1、59、60、71、79，而這五筆資料的96個特徵 (95個興趣的Subgroup加一個`NaN`)也和使用者原本興趣欄位填寫的資訊完全相同，如下圖所示:

使用上述方式後，原本train dataset有59737筆資料，經過此資料前處理方式後，新的Train dataset總共有235302筆資料。

* ### Data Post-Processing
* #### Apriori algorithm
Apriori演算法是購物籃分析背後的技術，它最主要的功能是找到`Association Rule`。由於Hahow上的課程有些主題會分成多個課程來授課，因此當有用戶購買其中一門課時，有高機率友會將其他課程也購入，因此透過此演算法我們能將模型預測出的課程，在其課程之後補上該用戶也可能購買的相關課。下表為我們使用此演算法在Training dataset中找出的一些Subgroup的Association Rule:
| Association Rule | Confidence |
|:----------------:|:----------:|
| {7, 66} → 72 | 6129/6205 |
| {7, 72} → 66 | 6129/6184 |
| {66, 72} → 7 | 6129/8313 |

* #### Use free courses
透過train.csv與courses.csv，我們可以分析Hahow的用戶在2021年1~8月購買課程價位的分布，如下圖所示:

可以發現免費的課程是最多人購買的，因此我們從courses.csv中統計2021年8~12月的免費課程有以下四堂:
| Course name | Course ID |
|:----------------------------------------:|:------------------------:|
| 建立個人品牌視覺：諾米帶你上手風格再造 | 6156a77fdf426a0007cc5fe1 |
| 創作坊精華：入手專家心法，讓品牌創意變身 | 6184efc3b2319400078aefe7 |
| 動態設計思維，柏尹帶你培養品牌動畫鑑賞力 | 6155cda6d425f500065f5c96 |
| 我想離婚怎麼辦：兒福聯盟的離婚規劃課 | 60c84de9eb75ca46e0c25e85 |

透過在Kaggle上的多次嘗試，可以得出在`Course Prediction`任務上用下述的順序表現最好:
`[6156a77fdf426a0007cc5fe1, 6155cda6d425f500065f5c96, 60c84de9eb75ca46e0c25e85, 6184efc3b2319400078aefe7]`

而對應的Subgroup順序為:
`[51, 5, 50, 25]`

而這四門課與這個順序我們稱它為`Magic Number`

* #### Put interested course first
雖然有Magic Number，但在Kaggle上測試時發現對於未知客戶的表現沒那麼好，因此我們推斷並不是每個用戶都會優先購買免費課，可能還是會以自身興趣相關的課程為優先，因此我們透過Hahow公司的廣告來推斷語言類的課程是廣受用戶喜愛，因此針對興趣有日文的用戶則將日文的subgroup id (28) 放置第一順位，而對英文有興趣的用戶則將日文的subgroup id (8) 放置第一順位，若對兩者皆有興趣者以日文為優先擺放。
由於我們做了這項資料後處理後發現Kaggle mAP@50的分數有明顯提升，因此我們將這兩個Subgroup還有與之對應的兩堂課程稱為`One Piece`。

* ### Course Prediction
* #### Implicit
[Implicit](https://github.com/benfred/implicit)是一個協同過濾的Python函式庫，該函式庫提供`Alternating Least Squares`、`Bayesian Personalized Ranking`等演算法來讓我們可以快速使用完成推薦系統的建立。

`Alternating Least Squares (ALS)` : 該演算法的Cost Function如下:

其中$\lambda$為超參數，用來避免模型過擬和。將使用者的購買課程經過One-hot編碼後輸入至該模型來做訓練，訓練好該模型後將Test dataset的使用者輸入至該模型，最後將Top 50的課程作為輸出。訓練超參數如下:
| Param# | Value |
|:-----------:|:-----:|
| random seed | 0 |
| factors | 128 |
| alpha | 0.2 |
| iterations | 100 |

`Bayesian Personalized Ranking (BPR)` : 該演算法的Cost Function如下:

做法與ALS相同，訓練該模型並將Test dataset的使用者輸入至該模型，最後將Top 50的課程作為輸出。訓練超參數如下:
| Param# | Value |
|:--------------:|:-----:|
| random seed | 0 |
| learning rate | 0.01 |
| factors | 128 |
| regularization | 0.05 |
| iterations | 100 |

* #### Similarity Matrix
參考協同過濾與關聯式分析的想法，我們透過使用使用者的購買紀錄建構相關性矩陣。在沒有其他資訊的情況下，與其考慮使用者填寫的興趣，我們認為更重要的是使用者的購買紀錄，真實購買紀錄比起使用者的資料中填的興趣更能刻劃使用者真實願意購買的課程類別，而出現在同一筆購買資料的課程也代表某種相同性質。以下說明我們的做法:
1. Initialize一個$n\times n$的零方陣$M$, $n$代表的是課程數。
2. 對所有購買紀錄，取出所有可能的長度為2的組合，並更新pair所對應到矩陣$M$的entry.

此處提及的相關性並非落在 $[0, 1]$，而是綜合了購買數量的相關性分數，因此我們並未對矩陣entry設定上限，也並未對分數進行normalize。

    # Here, we give the pseudocode for building a similarity matrix
    def similarity(purchase_record):
        n = len(num_courses)
        sim_mat = array.zeros(size=(n, n))
        for record in purchase_record:
            for course in record:
                array[course] += 1
            pairs = Combination(record, 2)
            for pair in pairs:
                sim_mat[pair[0], pair[1]] = +=1
                sim_mat[pair[1], pair[0]] = +=1
        return sim_mat

因為新課程(training dataset時間之後)沒有購買紀錄，這個做法仍然會有協同過濾cold start的問題，因此我們透過price、teacher、groups、topics定義了課程間的相關性。如同我們在EDA中發現的，課程價格與購買次數並沒有顯著關係，因此我們僅考慮課程是否為免費課。
$$sim(c1, c2) := w_1*1_{\{P_{c_1} = P_{c_2} \}} + w_2 *1_{\{T_{c_1} = T_{c_2} \}} + w_3 * \text{IoU}(G_{c_1}, G{c_2}) + w_4 * \text{IoU}(top_{c_1}, top_{c_2}),$$ where $w_i \in [0,1].P_c,T_c, G_c, top_c$分別對應課程$c$的 price、teacher、groups、topics.而
$$\text{IoU}(S_1, S_2) = \frac{|S_1\cap S_2|}{|S_1 \cup S_2|}$$
由此，我們可以定義新課程$i$與所有舊課程間的similarity vector $W_i$，將$W_i$ normalize後與舊課程similarity matrix相乘(即similarity matrix row的weighted sum)，就是我們定義的新課程對舊課程的相關性分數。
- Seen course prediction的方式是將消費者的購買紀錄vector $V = (0,1,...0,...,1)^T \in \mathbb{R}^n$跟similarity matrix $M$相乘($V^T M$)，去除掉已購買過的課程排序取出前50名輸出。
- Unseen course prediction是將$1_n = (1, 1, ..., 1)^T \in \mathbb{R}^n$與similarity matrix相乘($1_n^TM$)後排序輸出。

* ### Subgroup Prediction
* #### Transformer
`Transformer`是近幾年熱門且強大的模型，藉由注意力集中機制來學習序列資料中上下文的關係。而我們使用[Simpletransformers](https://github.com/ThilinaRajapakse/simpletransformers)來完成多標籤的分類任務，把使用者的興趣當作`Text`，然後`Label`為該使用者購買課程的Subgroup，由於Subgroup不會只有一個，因此將這些Subgroup也使用One-hot編碼來當作Label。以使用者編號`5a0bde2aa15b3f001e98429a`為例，由於使用者興趣會有Group與Subgroup，之間用底線做連接，因此將Group與底線濾除後做為輸入`Text`，而該使用者的Subgroup (1,59,60,71,79)經過One-hot編碼後作為輸出`Label`。該使用者輸入Text與輸出Label如下:

從subgroups.csv中可以得知總共有91個Subgroup，再加入一個`NaN`，因此輸出Label數量有92個

* #### Convert `Course id` predicted by Implicit to `Subgroup`
在`Course Prediction`的任務中，我們有使用`Implicit`來完成，而預測出來的課程在courses.csv都有對應的Subgroup，因此我們可以將Implicit預測每個使用者的推薦課程直接轉換成Subgroup

* #### Deep Neural Network
前面有介紹到使用Transformer來做訓練，但發現模型很容易overfit在training dataset上，因此我們有嘗試使用簡單的DNN來完成分類任務，流程如下:

將使用者興趣的Subgroup透過One-hot編碼當成輸入的特徵，再輸入至3層Linear layer與PReLU這個激發函數，為了避免過擬和發生，因此再加入Dropout，最後透過`Crossentropy`將模型預測的類別轉為機率值，並挑選機率前50高的當作輸出。下圖為訓練模型架構:

模型超參數如下:
| Param# | Value |
|:--------------:|:-------------:|
| random seed | 0 |
| epoch | 100 |
| optimizer | AdamW |
| learning rate | 0.01 |
| weighted decay | 5e-4 |
| batchsize | 16 |
| scheduler | ExponentialLR |
| gamma | 0.95 |

經過100次的迭代後，Loss curve如下所示:

* #### XGBoost
XGBoost全名為eXtreme Gradient Boosting，是一個流行的機器學習算法，也是許多Kaggle競賽的常勝軍。它專門用於提升分類和回歸任務的準確度。XGBoost是一種決策樹演算法，但是它在傳統決策樹的基礎上有了許多改進和優化。模型超參數如下:
| Param# | Value |
|:-----------------:|:------:|
| random state | 42 |
| lr | 0.06 |
| base_score | 0.5 |
| booster | gbtree |
| n_estimators | 100 |
| max_depth | 10 |
| max_cat_threshold | 64 |

## Experiments
### Course Prediction
| Method | Seen User Course | Unseen User Course |
|:--------------------------------------------:|:----------------:|:------------------:|
| Implicit BPR | 0.00851 | None |
| Implicit BPR + Magic Number | 0.14549 | None |
| Implicit ALS | 0.00659 | None |
| Implicit ALS + Magic Number | 0.14027 | None |
| Similarity Matrix | 0.0761 | 0.05978 |
| Similarity Matrix + Magic Number | 0.19282 | 0.13203 |
| Similarity Matrix + Magic Number + One piece | 0.21545 | 0.24199 |

由於Implicit是使用用戶購買資訊來訓練的，對於未知用戶就無法得知，而且可能建立稀疏矩陣時有些錯誤導致結果不如預期。而從上表可以看出使用Magic Number能使mAP@50分數有大幅度的提升，而再使用One Piece又能提升一個檔次。
### Subgroup Prediction
| Method | Seen User Topic | Unseen User Topic |
|:-----------------------------------------------------------------------:|:---------------:|:-----------------:|
| Transformer | 0.07845 | 0.09218 |
| Convert Course id predicted by Implicit BPR to Subgroup | 0.13463 | 0.22645 |
| Convert Course id predicted by Implicit BPR to Subgroup + Magic Number | 0.26804 | 0.24977 |
| Convert Course id predicted by Implicit ALS to Subgroup | 0.08299 | 0.07822 |
| Convert Course id predicted by Implicit ALS to Subgroup + Magic Number | 0.25916 | 0.1896 |
| DNN | 0.23728 | 0.22425 |
| DNN + Magic Number | 0.32884 | 0.24977 |
| XGBoost | 0.26129 | 0.25435 |
| XGBoost + Magic Number | 0.33937 | 0.32162 |
| XGBoost + Magic Number + One Piece | 0.34982 | 0.40154 |

再經過上述的實驗步驟後我們可以看到再加入One Piece後準確率，有進一步的提升，尤其又以新客戶(unseen user)的項目又來得更明顯。這也說明了很有可能大部分的新客戶都是為了某些講師、Youtuber、KOL等而去註冊Hahow的平台，而舊客戶只提升一點的可能，我們推斷是舊客戶比較會購買自己有接觸過的相關課程、或同一系列、同個講師的課程。

## Discussion
### 結果討論

在一開始選擇推薦系統當中，考慮到手上有的資料體量、特徵數量不多，加上表格資料通常比較離散，以及考慮到未來推薦系統在DevOps上的維護成本和整合容易度，我們在推薦系統的建立上，採EDA為主、ML為輔的策略。

以這次我們EDA的結果而言，我們發現有很大一部分的人購買免費課程，所以將熱門的免費課程推送到前面通常就會有不錯的準確率，此外我們也發現課堂發售的時間也佔非常大的因子，尤其是在新客戶(unseen user)上的影響又來得更大，這個結果我們推斷很有可能是廣告和Youtuber推廣等因子，造成大家跑去註冊Hahow的帳戶來修課。所以我們在一開始就在Validation set上採取try and error的方式，尋找最佳的排列組合。

對於把冷門課程類別移除的策略，也是考慮到當我們模型預測時，排在越後面的類別可能機率會非常接近，如果今天沒有將冷門類別移除，模型預測時有可能會把這些冷門類別排在中間的順位，以至於準確度下降。所以我們透過移除冷門課程，以增加熱門課程排序正確的準確率。

最後使用One Piece這個方法時，我們有不斷嘗試將比較少人填的興趣種類，搭配我們看過的廣告課程來做推送，最後發現語言種類，如日文和英文的相關性最高，這也間接證實了廣告的效用對用戶購買課程的意願有顯著的影響。

### 商業價值

在本專案中，所使用的XGBoost模型，優點就是其相較於眾多深度學習模型，如BERT、Transformer、CNN等，其記憶體占用空間小、容易維護、重現成本低、推斷預測時間接近即時，在不使用GPU加速的情況下，推斷10000筆測試資料的時間僅花不到2秒的時間，在GPU上訓練23萬多筆資料只需花費約1分鐘的時間。在課程預測上，我們透過對資料集的分析也定義了新舊課程的相關性，旨在解決新產品推出時缺乏購買紀錄造成資訊無法更新的問題。

而magic number系列的課程，為Hahow平台長久以來的熱銷課程類別，所以在未來應用上，可以繼續採用此組數字來推送相關課程。對於One Piece系列課程，我們也從準確率驗證了，YouTuber、KOL、廣告推送的影響力，在未來的行銷策略上，我們只要統計購買快速竄升的課程或是募資快速竄升的課程，再依據使用者的興趣來推送廣告到用戶搜尋引擎、社群平台、電子郵件等。而這個步驟可以直接自動化，先統計快速竄升課程、調整行銷策略，建造「即時推薦系統」，整個步驟不需要使用任何GPU或是讓模型重新訓練。

以此次研究報告中，我們也可以看出Hahow跟知名YouTuber和KOL合作，對於使用者的購買意願有極大的影響，以影響程度而言，新客戶(unseen)的影響力大於舊客戶(seen)，這也是為什麼最後兩組資料集用同一套推薦系統會有準確率上的差異。

對於新客戶的行銷策略，我們考慮到也有可能用戶是看了廣告才註冊平台，所以可以跟YouTuber和KOL合作，先吸引新客戶，新客戶註冊後之後，再將熱門課程推送給用戶。

對於舊客戶的行銷策略，雖然我們發現其受到跟YouTuber和KOL合作的新出課程影響度較低，但還是有相當大的提升幅度，所以我們應該根據依據其興趣推送快速竄升的新課程以及相關的熱門舊課程。

### 平台定位

對於我們組別而言，有使用過Coursera、Udemy、Udacity等相關付費線上課程平台的經驗。以我們這組的分析，

Coursera我們把他定位成中價位的課程平台，並提供很多來自世界各地知名教授的課程，且其項目偏向工程、科學和商業等。我們會購買Coursera課程主要是因為需要某項課程的修課紀錄，以證明自己的相關能力，同時也因為這些課程很多都是由大學和科技巨頭認證推出的，所以具有一定的公信力。

Udemy我們把他定位成低價位的課程平台，提供很多非常便宜的課程，項目包羅萬象，我們會購買Udemy課程主要是因為其平台有推出非常特別且少見的技術性課程。

Udacity我們把他定位成高價位的課程平台，通常不會購買該課程，只會等到該平台推出折扣活動才有可能購買，購買主要動力為該平台提供了Nanodegree的證書，並有實作Project項目，主要是以提升就業競爭力和豐富履歷為主。

而這次我們經過EDA等資料分析後，我們發現Hahow上大部分購買率較高的課程，受講師個人魅力的影響程度高，且Hahow平台有許多不同特色、授課風格的課程，我們這組認為這是Hahow和其他線上課程平台做出差異化的地方，所以未來在推送課程可以根據授課特色、講師特點將廣告推送給用戶。

## Conclusion
我們發現最重要的feature (影響分數最大的因數)

1. 免費課
2. 課程開課時間、知名度、評價、修課人數 (新課程)
3. 興趣我們認為是最有用feature (尤其是其中有幾個特別關鍵)
4. 刪除冷門的group跟課程
5. 找一個最好的預測組合(magic number)

## Work Distribution

| Name | Loading |
|:------:|:-----------------------------:|
| 劉智皓 | EDAㄝXGBoost topic prediction |
| 陳俊憲 | Similarity course prediction |
| 吳政彥 | Deep learning methods |
| 傅立威 | EDA, Data mining |