當我們在談論K-means：數據概述

因此如果轉載，請務必保留源地址，非常感謝！

知乎專欄：當我們在談論數據挖掘

博客園：當我們在談論數據挖掘（暫時公式顯示有問題）

引言

當希望快速了解或回顧某些演算法的發展時，一般而言，大家都會選擇閱讀綜述性文章，然後有選擇性的閱讀部分論文。而這種高效率的做法的負面，就是比較無趣的體驗，畢竟一直都行走在別人規劃好的思路中，總感覺少了點趣味性。

此系列文章一方面旨在藉助數據分析，回顧一些演算法的歷史演變軌跡，以及挖掘一些有趣的信息；同時，盡量對演算法進行較為全面的總結，加深對演算法的認識。

作為熱身，本文先從最基本的機器學習演算法之一，K-means開始。

內容包括如下幾個部分：

1. 數據概述：抓取K-means論文相關數據，並進行初步分析

2. 論文概述：閱讀K-means相關論文，對其內容進行簡要描述

3. 其他聚類演算法：閱讀其他聚類演算法論文，對其內容進行簡要描述

4. K-means總結：對K-means相關性質進行總結

數據準備

從IEEE上抓取「標題或摘要中含有K-means或相關關鍵詞的論文」的部分公開信息，對於現在已有的信息，我關注的主要是title、authors、keywords、abstract、publicationYear、isConference（是否是會議文章）。抓取到數據後，將數據存入mongodb，後續使用python+jupyter來分析。

受限於抓取難度，以及本人初步的爬蟲水平，並沒有抓reference，這對接下來的數據挖掘是一個遺憾。若有同學比較擅長爬蟲，歡迎私信或留言交流！（IEEE的網站說明裡聲明禁止爬蟲，因此政治正確上最好是不要去爬的，此處也不討論具體的技術細節）

論文數量

1969-2016年，每年IEEE收錄關於K-means的論文數量如下圖。其中藍色表示當年總文章數量，綠色表示當年期刊論文數量，紅色表示當年會議文章數量。

從圖中可以得出以下幾點結論：

1. 1990年以前，K-means相關文章很少，多的時候每年出版的總文章數量是1，少的時候則沒有任何相關文章出版；90年代作為明顯的過渡期，其之前與之後論文數量與趨勢的變化是翻天覆地的；

2. 會議文章佔了總文章數量的絕大多數：在抓取的6000多篇文章中，會議文章總5476篇，而期刊數量540篇，只有會議文章的1/10；而每年的會議文章跟期刊文章的比值也差不多這個數；

3. K-means相關會議文章數量在2005-2010和2013-2015幾年間出現了爆炸性的增長；卻在2010-2011以及2015-2016出現了大幅下跌；

4. K-means期刊文章數量在1990-2012年增長較為平穩，而在2012-2016年出現了連續4年的高速增長。

論文數量的變化趨勢-原因分析（瞎猜）

以上這些結果有的很好理解，有的卻讓人費解。以下給出部分結論原因的推測：

• 在1990年前，由於技術的限制（沒有PC來提高寫作效率，沒有互聯網來加快學術交流，文章審核等流程也會比較緩慢），每年K-means論文數量比較少是比較正常的。
• 而在1990s，PC的普及直接縮短了論文創作的周期，極大提高了文章數量。由於期刊文章有質量上的硬性要求，因此雖然也有增加但是還不是很明顯；相對的，會議文章作為交流的工具，明顯的反映出了論文創作數量上的變化。而關於1990sPC的普及，這裡引用wiki的1990s詞條中一段話作為補充說明：

The 1990s were a revolutionary decade for digital technology. Between 1990 and 1997, individual personal computer ownership in the US rose from 15 to 35%….Only a few million people used online services in 1990, and the World Wide Web had only just been invented. The first web browser went online in 1993 and by 2001, more than 50% of some Western countries had Internet access, and more than 25% had cell phone access.

• 在接下來的2000s，世界迎來另一個史詩級技術的普及——互聯網。這次不僅是加速了文章創作的過程，而是極大地降低了溝通成本，使會議文章數量噴涌式的上漲。再次引用wiki的2000s in science and technology詞條中的句子作為補充說明：

There was a huge jump in broadband internet usage globally - for example, it comprised only 6% of U.S. internet users in June 2000 and one mid-decade study predicted 62% adoption by 2010. Yet, by February 2007, over 80% of US Internet users were connected via broadband and broadband internet became almost a required standard for quality internet browsing. There were 77.4 million broadband subscribers in the US in December 2008, with 264 million broadband subscribers alone in the top 30 countries at that time.

• 以上是客觀技術的影響，而隨著演算法本身的普及，相關文章數量上肯定也會有所增加。比如從1970-1990，就能看到文章數量是有所增加的。同時，隨著機器學習在1990s跟2000s開始大放異彩，從1990s年被用於數據挖掘到2000s開始用在各種自適應演算法中，而K-means作為一種常見的分析、預處理手段，被更高頻的引用也是理所當然的。這裡能夠看到簡單的機器學習歷史的簡要介紹。

• 以上主要分析都是針對會議文章的。通過觀察1970-2010年的K-means相關會議文章向期刊文章的轉化情況，可以發現IEEE基本不會讓期刊文章有爆髮式增長，審查還是比較嚴格的。但是在2012-2016年出現了期刊文章連續4年快速增長的情況。初期我推測是否是因為增加了額外的期刊導致論文數量的增加，如新增的China Communications Magazine Co. Ltd. IEEE Magazine。於是將1970年以來，主要期刊的論文數量變化趨勢繪製出來（為了容易觀看，數量太少的就不畫出來了），如下圖。可以看到，2012-2016年K-means期刊文章連續增長的原因是Transaction和Journal中文章數量的增加。那麼到底是碰巧這幾年用到K-means演算法的文章水平都比較高，還是期刊要求在降低，或是別的原因，就不得而知了。

• 除了以上這個未解之謎，還有為什麼2010-2011以及2015-2016這幾年會議文章的數量會大幅下降沒有解決。理論上，會議文章能反映出該年的熱點問題，所以初步猜測是碰巧那幾年K-means被關注的比較少，所以出現的偶然現象。

作者

一般論文作者不會只有一個，理論上會把對該文章有較重要貢獻的人寫上去；當然實際科研環境中也有很多別的規則，我們試試能不能從數據中看出來點什麼。

這裡把每個作者看作節點，兩個節點間的連通性取決於是否合作創作過一篇文章，邊的權重表示合作過多少次。於是，圖裡每個節點的度就是與他合作者的數量。節點度的數值與該值對應的頻數的直方圖如下。可以看出大部分作者在這些論文里的合作者在5個以內。

這幾位也都是國內不同領域知名的專家了。但是看具體數據，如，Jiao 老師參與的K-means相關論文共9篇，相關作者高達30個。通過查看具體數據，其中Jiao老師為一作的1篇，大部分都是最後一個作者，且相關文章的作者一般都是4~6人。對於Zhang老師跟Wang老師，基本也都是同樣的情況。同時也能發現，這些老師也都是國內實驗室的。

這其實也是國內科研界的縮影：國內科研人員在發表文章時，時常會將實驗室同僚、還有大老闆等相關人員帶上，意在互相幫助。這也就說明了為什麼這些大佬們的共同作者這麼多，遠超平均值。

除此之外別的有關作者的分析，總覺得數據量不足，難以證明結論，所以就不貼上來了。

關鍵詞

每篇文章作者都會列出來幾個關鍵詞，接下來統計1969-2016年關鍵詞出現的頻數。以下給出總數量最多的5個關鍵詞，這幾個關鍵詞能表明K-means主要有哪些作用或跟那些領域相關。

以下對這幾個關鍵詞簡要說明：

• Clustering algorithms：這個是K-means演算法的本質作用，所以次數毫無疑問是最多的

• Algorithm design and analysis：有此關鍵字的文章，大多都屬於對K-means演算法的分析、改進，或者提出新的演算法並將K-means作為其中一步，如

Robust fuzzy clustering algorithms

K-tree: a height balanced tree structured vector quantizer

A modified version of the K-means algorithm with a distance based on cluster symmetry

• Data mining：有此關鍵字的文章，更傾向於利用K-means進行數據的預處理或者聚類，目的則是分析實際問題，如

Experimental evaluation of structural features for a speaker-independent voice recognition system

The application of agglomerative clustering in image classification systems

Learning to extract temporal signal patterns from temporal signal sequence

• Image segmentation：有此關鍵字的文章，則是利用K-means進行圖像分割，如

Image coding based on segmentation using region growing

Analysis of texture images using robust fractal description

• Feature extraction：有此關鍵字的文章，則是利用K-means提取特徵，如

Feature Extraction on Binary Patterns

A World Wide Web region-based image search engine

我們可以將這幾個關鍵詞每年出現的次數畫出來，如下圖。

從中可以看出：

1. 通過Algorithm design and analysis關鍵詞的增長趨勢能分析出，對K-means演算法的改進或者引用數量，一直在增加；

2. 通過Image segmentation和Feature extraction這兩個關鍵詞的高頻，能看出K-means大量被用在了圖像分割與提取各種特徵上；

3. 其中data mining的變化趨勢比較詭異，在2009年達到峰值，後又快速下降；我分析了這些論文的標題、摘要等，也並沒有看出內在原因是什麼；同時也排除是因為data mining在2009年的火爆，導致論文數量的增多，因為從Google trends中能看到data mining作為一個成熟學科，熱度一直在下降，並基本穩定，如下圖；初步猜測可能是2008或2009年有某個改進的K-means演算法被提出來，導致被大量的借鑒；不過由於缺少reference信息，難以定量分析。

每年的關鍵詞

除了分析關鍵詞的總體情況，我們還能夠從每一年熱門關鍵詞的變化中看出K-means使用領域的改變。由於1995年以前文章數量較少，以下給出1995以後每年熱門關鍵詞top3。

稍微觀察一下以上每年的熱門關鍵詞，就能發現K-means的應用領域就這麼幾個；只是隨著時間變化，熱門程度上有所改變而已。同時，也能看出熱點這種東西總是不斷地在循環，感覺跟潮流時尚什麼的一個樣子，過時的東西放個幾年可能又成了潮流的引領者。

Abstract分析

本希望通過自動提取每篇文章abstract的關鍵詞，我可以根據關鍵詞只查看感興趣的文章，進行後續分析。

於是先對所有非期刊的文章提取abstract。對每個abstract去除停用詞並tokenize。因為只是想簡單分析，並沒有stemming和過濾非單詞等操作。 然後對單詞列表計算TF-IDF，並提取每個abstract的TF-IDF最大的5個單詞。

結果發現這樣提取的詞語，並不能推測出abstract的含義，效果很不好。

最終決定還是把相關的文章abstract都過一遍。

本系列其他文章：

• 當我們在談論K-means：數據概述

• 當我們在談論K-means：論文概述（1）

• 當我們在談論K-means：論文概述（2）

• 當我們在談論K-means：其他聚類演算法

• 當我們在談論K-means：總結

推薦閱讀：