從資料之海撈出冠軍杯(1/2)
撰文／林軒田｜轉載自《科學人》2012年11月第129期
重點提要
- 資料探勘與機器學習是一體兩面，但資料探勘更強調實際預測時的表現及執行效率。
- 藉由舉辦世界性的比賽，讓學術界以及業界研究團隊競爭開發預測模型，是資料探勘的一種研發策略。
- 台灣大學團隊整合了組合式與平均式系統模型的優點，在2011年資料探勘杯以Yahoo!線上音樂服務系統的資料進行預測分析，奪得冠軍。
做為一名在大學講授「機器學習」課程的老師，我在第一堂課最常被學生問到的問題之一是：「機器學習和資料探勘有什麼不一樣？」
我的老師阿布‧莫斯塔法（Yaser S. Abu-Mostafa）在〈會思考的電腦〉中已經為我們勾劃了現代機器學習的面貌。機器學習可視為一種實現人工智慧的方式，它融入了統計學、機率學、演算法設計及計算理論分析，希望讓電腦能從充足的資料中，自動歸納出可以用於預測的規則；資料探勘則是電腦科學中一個歷史久遠的領域，在電腦科學發展的早期，人們就想運用電腦能運算及儲存大量資料的特性，從這些資料中找出些有用的蛛絲馬跡。舉例來說，超市的行銷部門可能想從銷售的資料中，找出哪些商品之間具有高度的關聯性，來做為商品排放的依據（有興趣的讀者，不妨去搜尋一下「尿布」、「啤酒」及「星期五」的故事）。
機器學習與資料探勘都著眼於讓電腦自動對「資料」加以運用，如果運用的方向是「預測」的話，那麼機器學習與資料探勘的目標是一致的。比較細緻的差別，在於機器學習源自於一個理則學的目標：對智慧（預測能力）的終極追尋；而資料探勘則較接近工程學的目標，且更重視方法在特定應用上的實用性，包括方法的實際預測表現及執行效率等。近代的機器學習與資料探勘其實可說是一體兩面，難以切割。許多源自機器學習的方法，已經被有效用於解決資料探勘上的各式問題；許多資料探勘上的重要工具，也成為機器學習系統密不可分的一部份。
在這兩個領域中，由計算機協會（Association for Computing Machinery, ACM）所屬的資料探勘小組（SIGKDD）主辦的大型比賽「資料探勘杯」（ACM KDD Cup），是現今全世界最重要的機器學習與資料探勘比賽。這項比賽每年舉辦一次，吸引了全世界學界及業界許多重量級的研究團隊參加，例如2008年的冠軍隊伍之一來自IBM研究部門，2009年的冠軍隊伍之一來自澳洲墨爾本大學。
資料探勘杯的目標，是在特定的主題上，設計能更準確「預測」的機器學習與資料探勘系統。每年的主題都不一樣，例如2008年的主題是希望能自動由病人的X光片判定是否得到乳癌；2009年的主題是希望能自動由行動電話的銷售資料中，預測顧客未來的行為（升級月租費、轉換公司等）；2010年的主題是希望能由學生在一個數學線上學習軟體的學習歷程中，自動判定學生的學習成效。
挑戰資料探勘杯
台灣大學從2008年起，每年都組隊參加這項大賽，隊伍成員以資訊工程系大學部及研究所的師生為主，這四年來屢獲佳績。2008年和IBM研究部門並列世界冠軍、2009年得到長期組（slow track）世界第三名、2010年得到世界冠軍、2011年得到兩組子比賽的雙料世界冠軍，成果十分豐碩。
在資料探勘杯中，主辦單位通常會提供一個巨大的資料集，稱之為訓練資料。參賽者必須運用機器學習與資料探勘的演算法，透過對訓練資料的分析，來建立適當的預測模型。主辦單位另外會提供一組測試資料，參賽的隊伍要把預測模型應用在測試資料後，將所得的預測結果上傳給主辦單位。主辦單位會把他們手上的正確答案和預測結果相比對，來評定預測的精準程度。以人類的學習來比喻的話，訓練資料就像上課的教材一樣，提供機器學習與分析；而測試資料就像考試的考題一樣，要用來評定學習的成效。
舉例來說，2011年第一項子比賽的主題，是希望能自動預測使用者對音樂的喜好，這在商業的音樂推薦系統中是個重要的課題。這個比賽的資料來自Yahoo!的線上音樂服務系統，總共橫跨11年的時間。每筆資料類似於「張三，兩隻老虎，85，2007年7月8日9:10」，意思是張三這位使用者，在2007年7月8日9點10分，給「兩隻老虎」這首歌評定為85分的喜好度；其中0分代表非常不喜歡，100分代表非常喜歡。這11年中，Yahoo!從許多不同使用者收集了大約2億6000萬筆這樣的資料，並且把每名使用者最後所評定的四筆資料，列為測試資料，其他（更早期所評定）的資料則做為訓練資料。
在測試資料裡，主辦單位把「喜好度」這個欄位隱藏起來當做他們手頭的答案，參賽系統的目標，就是預測這個隱藏欄位。也就是說，參賽者的預測模型，要能由使用者早期所評定的資料（可想成已經聽過的歌）預測他們之後對歌曲的喜好度。預測的精準與否，會以所預測的值和隱藏起來的答案的均方根誤差（root mean square error）來計算，越小代表越準確。
這樣的問題通常稱之為「協同篩選」（collaborative filtering），意思是希望協同自己與其他使用者的資料，來做出準確的喜好預測。要怎麼協同地預測使用者對歌曲的喜好呢？我們來聊聊一個簡單的方法。如果系統在訓練資料裡面發現，張三和李四都非常喜歡「兩隻老虎」這首歌，這可能表示他們有相似的喜好，而張三還聽過「快樂天堂」這首歌，也給了很高的分數，則系統或許可以推論，李四也會給「快樂天堂」這首歌很高的分數。所以從李四所評過的歌裡，我們可以找出「跟李四有相似喜好」的幾位使用者（例如張三），算一算「快樂天堂」這首歌平均在這些使用者中得到了幾分，就可以依此預測李四所給的分數。
這聽起來是個簡單的方法，也有個很有趣的名稱，叫「芳鄰法」（nearest neighbor，亦稱「最鄰近法」）。姑且不論這個方法的精確度如何，先讓我們來算算這樣做可能要花多少時間。我們要先幫李四在所有使用者中找出和他有相似喜好的人，2011年資料探勘杯的資料中有大約100萬名使用者，如果算一次相似度要花0.01秒的話，算完所有使用者和李四的相似度就要花上將近三小時，而算完所有使用者兩兩間的相似度要多久呢？158年！這說明了資料探勘杯的困難性，不但要精確，更要「有效率」（注意！這是資料探勘領域著重的特點之一），才能在短短數個月的比賽中奪得佳績。(待續)
(本文由教育部補助「AI報報─AI科普推廣計畫」取得網路轉載授權)