# 基於社群網路分析的交友軟體推薦系統
###### tags: `MLG`
簡報網址：hackmd.io/@kuouu/MLG_final
提案簡報：hackmd.io/@kuouu/MLG_final_proposal

近年來人們的交友管道越來越多元化，且隨著網路發展，開始出現了一些網路交友的平台，手機的普及更是促成交友軟體的誕生。但在使用交友軟體時常常會出現一些問題，像是配對的人不回訊息，或是開場很尷尬之類的情況，因此不同的開發團隊使用不同的方法來減少這方面的情形產生，像是使用一些興趣的標籤，讓陌生的彼此能夠快速用關鍵字認識對方，或是完善配對的推薦系統等等。

而我在這個研究當中，打算利用圖（Graph）來分析軟體的使用情況並且打造一個基於 Graph Neural Network 的推薦系統。將使用者轉換成點，將互動轉換成邊，所有使用者的互動情形最後會變成一張圖，圖像化這些資料之後，將會比以往資料庫中表格形式更能展現出現況，並且加以分析讓開發團隊能夠知道開發的方向與重點，讓團隊能夠更進步。

---

## 介紹

### AInimal 人工智慧社群養成

網頁版 👉 ainimal.io

結合「寵物養成」以及「交友」兩個元素，透過與寵物的互動，利用 AI 分析性格，並且使用性格來做交友配對。其中性格一共分為五類，分別是：浪漫、狂野、睿智、活力、佛系。

#### 性格分析


性格分析是使用了與寵物的對話進行自然語言處理，機制大概是如下：

1. 將聊天訊息萃取成單字的陣列
2. 將單字一個一個做 word embedding
3. 比對五個性格當中哪個最接近，並將那個最接近的性格加分
4. 最高分的性格即為使用者的性格

但在使用一段時間後，會發現這個分析其實並不準確，我們自己的猜測是：

- 聊天訊息並不足以代表一個人的性格，僅能代表他的聊天用字習慣而已
- 性格分類沒有心理學依據

因此現階段的性格分析並不能做為交友配對的依據，但自然語言處理並不是這篇研究的重點，因此會先暫時跳過這部分。

#### 配對機制


現行的配對機制非常簡單，只要符合以下兩點

1. 符合篩選條件
2. 當天有上線

就會被加入抽卡池，並「隨機」抽取一位來配對，沒有喜歡跟不喜歡的階段，抽到就能直接開啟聊天室。

#### 改良--基於個人特質的聊天活絡程度預測

[Google Colab](https://colab.research.google.com/drive/1V33OHXKVuFGInMpeTwKCzmjxGJMZwjyt?usp=sharing)



在前陣子就有想到說可以把深度學習套用在配對上，那時的想法也是利用人格特質來當作配對的依據，為了讓人格分析能夠更準確，我們使用了 LIWC(Linguistic Inquiry and Word Count) 這個軟體來對聊天訊息做處理，並且加入一些使用上的因素來做學習，正確率如下

train accuracy: 0.78
test accuracy: 0.62

可以看到模型表現其實沒有很好，而且是有些 over fitting 的，開發團隊討論後列出幾個可能原因：

- 模型太過簡單
- 人格特質不適合作為聊天活絡程度的評斷標準

我自己的觀點是：人格特質或許跟交友有關，但沒有辦法確定是“很像的人”還是“不像的人”容易成為朋友，甚至是情侶（這是大多數人用交友軟體的目的）

比起個性或興趣，我認為成為朋友的契機更注重於一些當下的因素，心情、場域、機緣等，因此決定使用社群網路來做推薦系統，在取得當下使用者的整體使用情況做分析之後，再來做配對

----

### 配對成功定義

其實做交友軟體的推薦系統一個比較難的點是定義配對成功，以 AI 的領域看就是資料的標記。在其他軟體上可能是右滑喜歡，我也有看過是配對一段時間之後會有彈出式視窗詢問配對滿意程度，但在 AInimal 裡面並沒有一個明確的評分標準，因此在開發過程必須自己定義。

我自己會將配對分為幾個階段，排除掉完全沒有訊息的來回以及單純打招呼，大概分為三個階段

#### 會回訊息


#### 聊得很熱絡


#### 真命天子/女、一生的好朋友


以軟體宗旨來說是希望能幫助使用者找到真命天子/女，但得知後續發展可能要做調查，在實際執行上可能有些困難，所以我會選擇退一步回到**找到很會聊的人**

---

## 相關研究

- [Recommender System for Online Dating Service](https://arxiv.org/pdf/cs/0703042.pdf) 2007 / 162 cites
- [RECON: A reciprocal recommender for online dating](https://www.researchgate.net/publication/221140972_RECON_A_reciprocal_recommender_for_online_dating) 2010 / 184 cites
- [Recommender Systems for Online Dating](https://core.ac.uk/download/pdf/33736431.pdf) 2015 / 6 cites
- [Design of Reciprocal Recommendation Systems for Online
Dating](http://web.cs.ucla.edu/~yzsun/papers/snam2016.pdf) 2016 / 24 cites
- [Shedding More Light on How Instagram Works](https://about.instagram.com/blog/announcements/shedding-more-light-on-how-instagram-works?fbclid=IwAR0L5kk9JEu3dEmz1VqIETTOevSWoc0IcZceaGTS9Vj_m0LccUGuJGsu_T0)

儘管推薦系統也算是一項熱門的研究領域，但大多會著重在物品或是社交平台上的推薦，使用在交友軟體上的論文並沒有很多。以上幾個列出的相關研究大多是使用 CF（Collaborative Filtering）來做，使用深度學習的並不多。

---

## 演算法
程式碼 👉 github.com/erickuo5124/MLG_final

在使用 Graph Neural Network 之前，我先嘗試單純用 rule base 的邏輯來做配對，並跟 GNN 的結果來做比對。除了多一個比對的標準之外，rule base 的效果其實也不一定比較差，計算的成本也不會很大，能夠大幅簡化配對的過程。

因此這部分會分成兩段來介紹，前面會是我自己考慮使用者的需求想出的 rule base 演算法，第二部分則會使用使用者資料來畫成圖，並用 GNN 來做推薦。

### rule base

在設計時，我預期了一些使用者可能遇到的問題，以及對於使用交友軟體的期望，得到的結論是：比起推薦所謂「匹配」的人，不如推薦「很會聊」的人給使用者，達到我們預期效果---聊天熱絡---的比例說不定會比較高。

那問題就會變成怎麼定義「很會聊」，我自己的解釋會是在一定時間下的聊天量，與開啟的聊天室數量的比例，也就是「平均聊天量」。一個人如果面對不同的人、不同的情況下都能侃侃而談，那他應該就會是我們大力推薦給其他使用者的人；相對來說如果那個人只有對幾個人比較聊得開，那可能就是碰巧遇到而已，分母很大的情況下會拉低分數，更不用說很少在回訊息的人了。

||會聊|不會聊|
|-|-|-|
|會聊|一定聊得來|有機會聊起來|
|不會聊|有機會聊起來|有點困難|

在這個情況下，「很會聊」的人會被一直配對到新的使用者，考量到一個人的時間有限，回訊息的量總有一個極限，到達極限之後再增加聊天室會讓分數降低，如此一來就能避免永遠只有一個人會被配對到的情況。

#### 平均聊天量

依據當下的**平均聊天量**由高至低做推薦

$$
平均聊天量 = \frac{\sum_{聊天室}聊天字數}{聊天室數量}
$$

#### 期望結果

- 會聊天的人優先，會“被”配對到很多人
- 不會聊天的人比較不會被主動配對到
- 在時間內配對到一定程度會讓聊天量下降，後面順位的人往上排名

#### 解決的問題

- 配對到的人最近一定有在玩，而且很活躍
- 雙方至少有一人有一定的社交程度，造成尷尬開場的機率較低（難聊的人不會互相遇到）
- 聊天室數量增加會降低平均聊天量，因此過度配對會降低排名，不會有某個人一直配對到超多人的情況
- 與比較會聊的人配對，增加社交能力較低的人的自信

#### pseudo code

1. get G
2. get user_list
3. remove random edge, get G’
4. get rec_list by G’
5. validation

### Graph Neural Network


使用 Graph Neural Network 的目的不外乎就是獲得圖上 local 或是 global 的資訊，能在目前搜集的資料之外獲得更多額外的資訊來做配對。因此我的想法是結合 GNN 跟目前交友軟體推薦系統研究的大宗 Collaborative Filtering 來做推薦。

#### GNN

用 GCN 得到 node embedding ，並使用 similarity 做 user user 的 Collaborative Filtering

1. GCN 學習 node embedding
2. 做 user user 的 CF

---

## 實作

### Evaluation

對於推薦系統的驗證方式其實有很多種，但考量到真實資料的狀況，其實有很多方式是不太合適的。最主要的問題是「單一聊天室聊天量太少」的資料佔整體的很大一部分，這使資料嚴重的不平衡，若是移除這些資料又會讓資料變得太少，不足以反映平均的狀況。

因此在這裡我是使用召回率（Recall）來做評價的方式，也就是「預測」出現在「實際」上的比例，其中也考慮到有問題時比較好 Debug（將兩邊的 list 印出）。

#### recall

$$
Recall(pred, label) = \frac{pred 出現在 label\_list 出現次數}{label\_list 的長度}
$$

### Data set

| 資料名稱 | 數量 |
| -------- | -------- |
| user | 5043 |
| chat | 290559 |
| friend | 22683 |

上面是目前資料庫中整體的資料狀況，但在訓練的過程中，會將資料以「一段時間」來做取用，因為這篇研究強調「當下狀況」，而不是整體的表現。實際是使用一個月來訓練，以抓取 2020 年 11 月來說，大約可以獲得 300 個左右的使用者，訊息總量大約是 20000 上下，但實際上經過篩選後的資料又更少了。

在取得使用者的 node feature 部分我是使用以下幾種資料：

- gid
- gender
- animal
- heart
- type
- personality
- bgm
- active_time

當然資料庫裡面並不只有這些，還有一些上線時間等等的資料，但考量到是以時間間隔來做訓練，再抓資料的時候如果不是抓最新資料，有些資料就沒有辦法使用，例如：最後上線時間。

如果有要發展下去之後可能要定期備份資料庫 snapshot。

#### 網路圖

##### 2020


##### 2019


上面分別為 2020, 2019 年 11/01～11/15 的資料，可以看到除了中間那一坨之外，外面還有一圈單個的點，那圈就是比較沒有在玩的使用者，放大看可以看到箭頭都是往內，也就是別人傳訊息給他，但他都沒有回，可能是下載之後馬上就刪掉了，又或者單純是沒有在聊天。

事前規劃的時候沒有想到這個情況會影響這麼嚴重，直接就下去測試，結果如下：

- rule base: < 0.1

但在移除不活躍的使用者之後，rule base 的 Recall 提升至約 0.1 ~ 0.2 雖然是有很明顯的提升，但還是不高。

其實很多點“沒有往外的邊”，也就是很多使用者沒有在使用，可能只是下載來看一看就再也沒有登入了，因此在加入 user feature 之後，我將不活躍的使用者移除，並按照性別改變顏色，圖形變成如下


按照性別配對之後就有顯著的提升了，我居然都忘記交友軟體的大宗還是男女配對啊！

- rule base 的 Recall 提升至約 0.1 ~ 0.5
- GNN 約為 0.4 ~ 0.5（較穩定

但其實也不算是太高，相比之前使用性格做深度學習的甚至沒有比較好，就算我現在的使用方法是比較有邏輯性的，我相信現在的方向是正確的，只是可能還有很多資料處理的地方沒有考慮到，我把目前想到的問題點列在下一點。

### 問題點

- 需要每個時間點資料庫的 snapshot，ex: 更新時間、今日登入、交友狀況
- 移除不活躍的使用者之後資料不足（需要一段時間內的資料
- 沒有標記的資料

---

## 結論

本篇研究圖（Graph）在交友軟體上的應用，包括：

- 利用圖形來視覺化呈現資料並分析使用者習性
- 聊天狀況
- 配對偏好
- 平均聊天量
- 使用時間區段內的使用者資料來做配對
- rule base
- Graph Neural Network

### future work

- 利用網路圖來呈現目前使用者的狀況
- 本篇當中的圖是使用 spring layout，應該有更好的呈現方式
- 定期備份資料庫狀態以拿來做訓練
- 改善軟體配對機制，取得標記資料
- 右滑喜歡、左滑不喜歡
- 配對評分機制