作者 | 蔣寶尚
編輯 | 叢 末
6月6日，中國計算機學會（CCF）主辦的中國計算機學會青年精英大會（CCF YEF）在線上舉行，在「經典流傳的機器學習與數據挖掘算法」技術論壇上，明略科技首席科學家、明略科學院院長吳信東；UCLA 副教授孫怡舟；微軟雷蒙德研究院高級研究科學家東昱曉；CCF高級會員、清華大學計算機系長聘副教授朱軍；CCF高級會員、中科院計算所研究員沈華偉幾位特邀專家帶領了大家重溫經典，解讀他們心目中的經典機器學習與數據挖掘算法，並與大家分享了這些算法的起源、應用與影響。
其中， 明略科技首席科學家、明略科學院院長吳信東做了題為《數據挖掘算法回顧：經典與現代》報告，總時長為1個小時左右，內容主要分為三個部分：數據挖掘中代表性的領域、數據挖掘的經典算法、2006年之後的現代數據挖掘技術。
下文是本場報告的文字版，由 AI 科技評論編輯。
今天主要回顧三個方面，第一方面是數據挖掘比較有代表性的領域；第二方面是分析2006年在IEEE ICDM會議上排名前十位的數據挖掘算法；第三方面是分析2006年以後，數據挖掘兩個比較有代表性的方向。
無論是模型研究還是應用，數據挖掘主要有10個代表性的領域。第一個領域是大家耳熟能詳的「分類」，主要內容是探討如何將數據進行歸類。在分類領域比較經典的算法包括C4.5、CART、KNN、樸素貝葉斯等等。
其中，C4.5是澳大利亞的研究者在1993年做出的工作；CART是史丹福大學的統計學教授在1984年的工作，主要面向分類與回歸樹；KNN是1996年發明的，也是目前比較常用的「物以類聚，人以群分」思想；樸素貝葉斯發明於2001年，其在條件機率的基礎上進行了獨立性的假設。
第二個領域是「聚類」，其與「分類任務」的差別在於是否有類型標籤，聚類任務常常涉及無類型標籤的任務。比較經典的算法主要有兩個，一個是K-Means，於1967年提出，另一個是BIRCH，全稱是利用層次方法的平衡疊代規約和聚類，是資料庫領域的研究者於1994年提出，其效率比K-Means更高。
第三個領域是「關聯分析」，這類主題在網際網路和日常生活中廣泛存在，經典的案例是「啤酒與尿片」的故事。早期最有代表性的算法是Apriori，作為關聯規則挖掘（Association rule mining）的代表性算法，其主要任務就是設法發現事物之間的內在聯繫。另一個代表性的算法是華人學者韓嘉煒在2000年提出的關聯分析算法—FP樹，其效率比Apriori提高了一個數量級。
上面三個是數據挖掘領域裡面最有代表性的三個領域，只有了解了這三類領域才算數據挖掘基本入門。
第四個領域是「統計學習」，更多的是挖掘分析數字期望，數據特徵。兩類比較有代表性的算法，一是SVM（支持向量機），其是一類按監督學習方式對數據進行二元分類的廣義線性分類器；另一個是EM（期望極大）算法，其是一類通過疊代進行極大似然估計的優化算法。這兩類算法對初學者要求比較高，因為涉及很多統計分析。
第五個領域是「Link Mining」（連結挖掘），主要處理全球資訊網中網頁的連結、結構。PageRank和HITS是此領域比較經典的算法，其中，PageRank是谷歌搜索網頁背後的算法支撐，當時發明這個算法的兩個人（佩奇和布林），雖然現在還沒有拿到博士學位，但其現在是美國工程院的院士；HITS是由康奈爾大學( 的Jon Kleinberg 博士於1997 年首先提出的， 是一種網頁重要性的分析的算法。
第六個領域是「Bagging和Boosting」，其核心思想是「三個臭皮匠頂一個諸葛亮」，也即群體智慧超越個人智慧，其作為一種模型融合的方法，可以將弱分類器融合之後形成一個強分類器，而且融合之後的效果會比最好的弱分類器更好。經典的代表算法是AdaBoost。
第七個領域是「序列模式」，其將空間、時間等另外的維度引入了關聯分析。其代表性的算法是GSP和PrefixSpan。
第八個領域是「Integrated Mining」，這一領域最開始由新加坡國立大學的幾位華人學者探索，比較有名的是LiuBing老師，他1998年首次提出了CBA算法，將集成分類與關聯規則挖掘融合了起來。
第九個領域是「圖挖掘（Graph Mining）」，其在計算機以外的領域應用廣泛，例如化學、生物等等。比較有代表性的算法是gSpan。
第十個領域是「深度學習」，其集大成之作是2015年由圖靈三劍客Yann LeCun, Yoshua Bengio Geoffrey Hinton那篇發表在nature上面的《Deep Learning》。
1
十大經典算法
數據挖掘領域的十大算法評選是基於我2006年在IEEE ICDM上推出的數據挖掘算法Top 10。這十個算法如上圖所示，分別是：CART、Naive Bayes、KNN、AdaBoost、PageRank、EM、Apriori、SVM、K-means、C4.5。
其中，CART是由史丹福大學的四個統計學教授發明，這四位老師只有一位是IEEE Fellow，另外三位是美國的工程院院士、美國科學學院院士，在統計回歸領域非常有名望；第七名的位次是由樸素貝葉斯、KNN、AdaBoost三個算法並列；PageRank排在了第六名；統計學習方法EM排在了第五位；Apriori這一關聯分析方法排在第四位；SVM（支持向量機）在第三位；聚類算法K-Means在第二位；2006年，澳大利亞學者Ross Quinlan開發的C4.5算法排在了第一位。
上述10個算法是2006年評選的，14年過去了，這十大算法是否時過境遷？是否需要重新評選？
昨日，我去google scholar 搜索了一下當年的文章《Top 10 Algorithms in Data Mining》，這篇文章發表寫成於2006年，發表於2008年，目前引用量已經達到了4879次。如上圖所示，可以清晰的看到，其引用量還在逐年上升。以一本書的銷量為例，只有當書的銷量開始下滑的時候才需要重新考慮重新寫書。所以，考慮到文章與日俱增的「熱度」，重新考慮Top 10算法的排名與評選為時過早。十大算法的評選在今天來看並未過時。
2
數據挖掘領域的現代算法
前面講述的內容大多在2006年之前，接下來介紹我個人認為2006年之後的數據挖掘的兩大方向，供大家討論。
第一個方向是大家都會承認的是Deep Learning，因為此領域掀起了人工智慧領域研究的熱潮，也對數據挖掘領域的推動起到了不可否認的作用。上面我列了三個框架：卷積神經網絡、遞歸神經網絡、循環神經網絡等給大家提供討論的思路，因為我本人研究「邏輯」比較多，對深度學習了解不是很多，後面的報告講者也會討論深度學習，所以我就不展開討論了。
第二方向，是我自己的一個工作，叫做OSFS：Online Streaming Feature Selection，這個工作與前面經典算法大不相同。其核心思想是針對數據來源多樣性，數據分散性來把數據分成數據元。值得一提的是，OSFS不光是針對數據量，還針對數據特徵的變化。例如一個資料庫裡面，包含的變量是X1~X20，那麼經過一天的時間，可能就變成了X1~X21。所以，這樣數據的特徵就會變成「流」狀態。
我們此類工作的大致框架如上圖，給定一個新特徵X，先檢查其的相關性，看新特徵是否能影響當下任務，如果無影響，那麼拋棄，如果能夠影響當下任務，那麼進一步檢查冗餘性，即這個新特徵能否用現有的特徵推導？能否用現有的特徵表示？如果能夠表示，那麼拋棄新特徵，如果沒有冗餘性，那麼將此新特徵更新到模型中，從而輸出新的特徵集合。
可以看到這個算法框架是個閉環，其重點在於如何設定停止訓練的標準。我們設定了三個標準：1.達到預期的精度；2.達到最大的疊代次數；3.沒有更多的新特徵可以加入。
這個方向的工作，我們最早是在2010年開始嘗試，並在ICML會議上發表了一篇文章，2013年又那篇文章進行了進一步的分析，而目前此類工作可能已經有了幾百篇文章。
上面是我們最初的算法思路具體細節，重點是在於對新特徵的相關性分析和冗餘性分析，雖然在處理新特徵方面比較有新意，但是容易導致NP問題。也就是說相關性分析可以做dependency ，但一旦判定存在相關性，進行冗餘性分析的時候，需要考慮所有現存特徵的子集。
針對NP問題，我們在OSFS的思路上進行了創新，即設計出Fast-OSFS算法將原有的NP複雜度問題轉換成多項式問題。原有的相關性分析沒有改變，此算法改變的是冗餘性分析。即在冗餘性分析中將所有特徵的子集檢測轉換成了馬爾科夫毯。
基於此，我們也做過很多的實驗，如上圖所示，示例的數量在不斷上升。
用OSFS算法我們也做了一些例子，例如對上面三張火星大圖片（每張圖片是37500*56250平方米）進行撞擊坑檢測。例子的結果我們也寫到了論文中：
最後，談一些開放問題，首先經典十大算法的排名要變麼？答案是：肯定要變，因為需要更好的算法去替代歷史。
再者，深度學習會不會取代經典算法？答案是：不會！深度學習是機器學習或者數據挖掘一個有力的工具，雖然很有效，但是取代不了現有經典算法。
招 聘
文章來源: https://twgreatdaily.com/zh-cn/Jvd0lXIBnkjnB-0zMtxC.html