Shopee Code League 2021：數據分析問題解法與 Union-Find 演算法教學

Shopee Code League 2021 是電商蝦皮購物為全東南亞舉辦的線上資料科學競賽，2021 年的賽事為期三週，每週有不同主題，包括數據分析（Data Analytics）、資料科學（Data Science）、以及演算法程式設計（Programming Contest）。

在這則筆記，我將分享第一週賽事 Multi-Channel Contacts 的競賽心得：介紹 Union-Find 演算法、以及它如何又快又準確地解決這次的數據分析難題。

競賽題目說明

用戶會透過多種管道來使用產品服務，然而，它們每次留下的足跡不見得一樣。在本競賽中，主辦單位希望透過每次顧客接觸所留下的電子郵件信箱、電話號碼、或是訂單編號，來判斷哪幾次互動是來自「同一個顧客」。

競賽提供 50 萬筆客戶接觸的資料，每筆資料會留下電子信箱、或者電話號碼、或者訂單編號，不見得三者都有、但是三項訊息至少會留下一個。一旦觀察到多筆資料在上述三項資訊有任何其中一項相同，就判定為同一個顧客，例如，如果在兩筆客戶接觸資料中，電話號碼欄位相同，這兩筆就視為同一人。

參賽者的主要任務就是要判斷哪些產品接觸紀錄是來自同一個顧客。

本文只是白話簡述競賽內容，細節請見官方競賽頁面（Kaggle）。

解題困難點

用 Corner Case 來簡單說明本題最大困難點：

會發生多筆資料，彼此信箱、電話號碼、以及訂單號碼全都不一樣、沒重疊，但是他們應被歸類為同一個人的狀況！

如下圖範例，藍色 Highlight 的三個用戶，電話、信箱、與訂單號碼毫無重疊，但是它們在比賽規則中、應被歸類成同一人。事實上，圖片中 9 個 ID 全都應該歸類成同一個人。

解題困難點範例，自製資料、並非比賽實際數據（Source：好豪的 Github）

透過基本的 Group By 計算，我們可以得知哪些人有相同的信箱、哪些人有相同的電話號碼、以及哪些人有相同的訂單號碼。但是，這些分組資訊分別處在這三張表格，單純的 Join 合併並不足以解決問題。舉例來說：

先使用信箱的表格，得知 A、B、C 三個人有相同的信箱，應被視為同一人
- 得到資料： {A: A-B-C, B: A-B-C, C: A-B-C}
後使用電話號碼的表格，得知 C 與 D 兩個人有相同電話號碼
- 得到資料： {C: C-D, D: C-D}
但是，要合併上述兩項資訊，只能用重疊的 C 來參照（Join）
- 得到資料：{A: A-B-C, B: A-B-C, C: A-B-C-D, D: A-B-C-D}
- 正確答案顯然是：A、B、C、D 都該視為同一人
- A 與 B 沒有改到組別、答案錯誤！

最大難點就在於：如果組別內某個人更改組別、那整個組別的資料都要一起更改組別，要怎麼做到「遷一人而動全組」？

當然，直覺做法可以是幫「動全組」的行為多加一個迴圈就好，但是，這樣時間複雜度至少是 O(N^2)，本次競賽有 50 萬筆資料，時間複雜度太高是解不完問題的。

對此「遷一人而動全組」問題，我的解題方式是採用 Union-Find 演算法，以下文章將會先簡短介紹此演算法。

Union-Find 演算法簡介

Union-Find 處理的是分組問題，它要求資料結構要有 Distinct-set 特性：

為資料分組，並且一筆資料只能出現在其中一組
也就是各組之間無交集（non-overlapping）
如果一筆資料屬於 A 組，後來發現也屬於 B 組，那 A、B 兩組需被合併為同一組。

假設有兩個組別的資料、資料大小分別是 N_1 與 N_2，若要把兩組資料合併成同一組，需要更動每筆資料的組別資訊、總共執行 N_1 + N_2 次嗎？不用！只要善加利用 Union-Find 的核心概念就可以更快：

每一個組別給一個「頭目」
每筆資料都能找到組別的頭目
合併多個組別時，合併各組的頭目即可

在此概念下，要合併兩個組別的多筆資料，其實只要做一次「兩個頭目合併成同一個頭目」的動作就好，不管兩組總共有幾筆資料，都只需要做一次動作。

Union-Find「頭目」的抽象概念，視覺化之後會長得跟機器學習常見的階層式分群法一樣。

更正規的程式實作方式，筆者好豪推薦你閱讀普林斯頓大學的演算法教材。以下，我只實作 Union-Find 對解題有幫助的功能。

解題方法

認識 Union-Find 之後，我們既有的「哪些人有相同的信箱、哪些人有相同的電話號碼、以及哪些人有相同的訂單號碼」三個表格，就是做三次 Union-Find。

# Union-Find (Python3)
# Author: Kuan-Hao Huang
# https://github.com/KuanHaoHuang/shopee-code-league-2021-multi-channel-contacts-problem/

class UF:
  def __init__(self, node_list):
    self.data = {nd: nd for nd in node_list}

  def _find_deepest_node(self, node):
    while self.data[node] != node:
      node = self.data[node]
    return node

  def connect(self, node_1, node_2):
    self.data[self._find_deepest_node(node_2)] = self._find_deepest_node(node_1)

  def get_data(self):
    return {k: self._find_deepest_node(v) for k, v in self.data.items()}

用 Python3 實作說明，Union-Find 物件初始化後，內部結構用 dict 儲存資料，key 與 value 分別是 Id 與「直屬組別 Id」。稱為「直屬」，是因為直屬組別可能隸屬於另一個組別。這個直屬關係會有盡頭，我們定義：

當 Id 與直屬組別 Id 相同時，該 Id 就是「組別頭目」

物件初始化時，每個人都跟自己一組、每個人的 Id 都跟直屬組別 Id 相同、每個人都是自己所屬組別的頭目。

怎麼幫每個 Id 找到組別頭目呢？_find_deepest_node() 函式中，就是遞迴地不斷為「Id 的直屬組別」查看它的直屬組別，直到找到「Id 與直屬組別 Id 相同」的條件為止。

這項實作最重要的部分是 connect()，要讓兩筆資料成為同一組，小心不要搞錯變成只更改直屬組別（data[node_2] = node_1），而是要記得先找到兩筆資料找到各自的組別頭目、合併頭目才正確。

最後就用下圖數據範例來說明 Union-Find 的解題方式，需要注意的是，物件內部儲存的是直屬組別，要取得最終分組需要另外用 get_data() 取得資料：

本競賽還有其他的解題要求，但是只要做好正確分組，其他要求就只是單純的資料處理而已、在本篇文章就不贅述。對完整程式碼有興趣的話可以參考好豪的 Github。

複雜度分析

所有資料都要用 dict 儲存各自的直屬組別資訊，空間複雜度是 O(n)。

時間複雜度的關鍵在 _find_deepest_node() 函式，裡面雖然有一個 while-loop，實際上，這個 while-loop 的迴圈執行次數取決於有幾項比對條件。在本競賽，分別比對信箱、電話號碼、以及訂單號碼，並且三個表格 Group By 之後都符合 Distinct-set 特性，因此，_find_deepest_node() 內的 while-loop 最多執行 3 次，此函式本身時間複雜度是 O(1)。也因此，「合併組別」的 connect() 時間複雜度也是 O(1)。

此外，每個表格執行「合併組別」的次數上限就等於資料筆數，對每筆資料都合併組別花費總時間是 O(1)*O(N)，所以本次解題的時間複雜度是 O(N)。

意猶未盡？來挑戰面試題吧！

筆者解完比賽題目，亂逛 PTT 才發現，相似的問題也出現在蝦皮新加坡總部的機器學習工程師面試題目裡（面試經驗分享原文）：

請為資料分組，且分組後的資料順序要與原始資料相同。
輸入：[('a', 'b'), ('c', 'd'), ('b', 'e')]
輸出：[['a', 'b', 'e'], ['c', 'd']]

我認為這題也能用本文的 Union-Find 概念來解題，所以將它納入本文，有興趣的讀者就快試試看怎麼解吧！

結語

本文提及的這項數據分析競賽，只有限時三個小時就比完了，然而，筆者在比賽結束後還持續在思考這個題目整整兩天，因為，我在本業的遊戲數據分析工作也遇到了一模一樣的問題：

玩家為了在遊戲一開始就抽到最好的寶物、一直重新申請帳號
我們要怎麼判斷多個帳號其實來自同一個玩家？

我很高興跟隊友們參加了這項比賽，雖然我們沒在限制時間內想出最佳解法，但是比賽過程的密集討論，就算只有三小時、也獲得很多靈感，發現 Unino-Find 演算法也可以解決公司遇到的遊戲數據問題！

我的所有解法 Python3 程式碼都放在我的 Github，歡迎參考，如果有可以改進的地方，也希望可以給我回饋。關於這場比賽，還想參考更多不同解法的話，台灣資料科學社群 Facebook 社團裡有參賽者熱情分享他們的做法，值得一看。

在此感謝一起討論解題的隊友們，筆者寫下這篇筆記（2021-03-08）時，此賽事還有另外兩場不同主題的競賽還沒開始，很期待跟大家一起繼續努力。

Kaggle 演算法