一個(gè)貫穿圖像處理與數(shù)據(jù)挖掘的永恒問題

創(chuàng)新對(duì)于學(xué)術(shù)研究或產(chǎn)業(yè)應(yīng)用都具有不言而喻的重要作用，現(xiàn)在國(guó)家也提出了要建立創(chuàng)新型國(guó)家的發(fā)展戰(zhàn)略。如果回到我們所探討的圖像處理或數(shù)據(jù)挖掘研究，細(xì)細(xì)品讀其中的某些點(diǎn)滴，你是否能窺探出些許啟迪？首先，創(chuàng)新可以分成兩種，一種是原始創(chuàng)新，另外一種就是所謂的二次創(chuàng)新。如果一個(gè)東西過去完全不存在，你鬼使神差的就想出來，那就是原始創(chuàng)新。比如圖靈當(dāng)初石破天驚地構(gòu)想出圖靈機(jī)模型就是原始創(chuàng)新。到現(xiàn)在也沒有任何跡象表明，他受到了什么事或什么人的啟發(fā)。事實(shí)上，現(xiàn)在人們（包括我學(xué)習(xí)圖靈機(jī)的時(shí)候）也非常驚訝，圖靈是如何提出這種前無古人的奇思妙想的！

二次創(chuàng)新也有很多種形式。比如逆向創(chuàng)新。據(jù)說人們?cè)诎l(fā)明吸塵器之前最先發(fā)明的是吹塵器。一吸一吹，看似簡(jiǎn)單的一個(gè)顛倒，結(jié)果卻如此神奇。現(xiàn)在同學(xué)們學(xué)習(xí)模式匹配算法時(shí)，必然是言必稱KMP算法。的確，就原有的思路來說，KMP算法已經(jīng)是做到極致了。但如果你還想有所突破呢？那就得首先打破舊有的條條框框。所以Boyer和Moore逆其道而行之，便提出了BM算法。KMP是從前向后做比較，而BM則是從后向前做比較。BM算法不僅提供了效率，更重要的是，由他們所提出的新思路為發(fā)端，后續(xù)產(chǎn)生了一個(gè)龐大的算法族。像BMH，BMHS等等又接踵而至?，F(xiàn)在實(shí)際中基于BM算法的改進(jìn)算法（相比于KMP）應(yīng)用得其實(shí)更為廣泛！

但是今天要談的還不是逆序創(chuàng)新的話題。我們要談的是二次創(chuàng)新中另外一種方法，暫且稱之為“推衍創(chuàng)新”。這個(gè)思路在現(xiàn)代計(jì)算機(jī)科學(xué)中可謂隨處可見，如果你還沒有抓住他的名門，那么說明就研究工作來說，你還沒入門。舉一個(gè)簡(jiǎn)單的例子作為序言的結(jié)尾。最初，“偉哥”是作為治療心絞痛的藥物而研發(fā)的。但是，后來在臨床試驗(yàn)中發(fā)現(xiàn)對(duì)治療男性勃起功能障礙更加有效。所以現(xiàn)在它主要被應(yīng)用于這方面的疾病。所以我們所說的推衍的大概意思就是，把一個(gè)領(lǐng)域的成果平行地轉(zhuǎn)移到另外一個(gè)領(lǐng)域，說不定就能發(fā)揮起效！希望本文在這方面能夠給大家一些啟示。

一、平均值與中位數(shù)：一對(duì)死纏爛打的概念

平均數(shù)是統(tǒng)計(jì)學(xué)中用來衡量總體水平的一個(gè)統(tǒng)計(jì)量。但是，顯然它并不“完美”。舉個(gè)例子，現(xiàn)在房間里有6個(gè)人，他們的財(cái)富不盡相同，但又相差無幾，這時(shí)我們可以說他們的平均身價(jià)是100萬(wàn)元。這個(gè)平均數(shù)基本上是有意義的，因?yàn)樵诩僭O(shè)前提下，我們知道他們6個(gè)人的財(cái)富或多或少都在100萬(wàn)元上下?，F(xiàn)在馬云突然來了，然后房間里變成7個(gè)人了。同樣的問題，房間里所有的人平均身價(jià)可能已經(jīng)突破100億，但是這個(gè)平均數(shù)就沒有什么意義了?，F(xiàn)在房間里沒有誰(shuí)的身價(jià)在100億上下。這時(shí)就引出了中位數(shù)的概念！把一組數(shù)從小到大排列，取中間位置的那個(gè)數(shù)來作為衡量該組總體水平的一個(gè)統(tǒng)計(jì)量。如果取包含馬云在內(nèi)的7個(gè)人之財(cái)富的中位數(shù)，我們知道應(yīng)該還是100萬(wàn)左右，那么它顯然是有意義的，它至少代表了這個(gè)總體中絕大多少人的情況。

你看出中位數(shù)的意義和作用了嗎？現(xiàn)在當(dāng)數(shù)據(jù)點(diǎn)分布比較均勻的時(shí)候，平均值是有意義的。但是一旦數(shù)據(jù)中存在異常值時(shí)，平均數(shù)就有可能失靈，這時(shí)就要用中位數(shù)來排除掉異常值的影響。但是平均數(shù)仍然有存在的價(jià)值，（只是某些時(shí)候我們要對(duì)其進(jìn)行修正）。例如體育比賽時(shí)的打分機(jī)制，通常是“去掉一個(gè)最高分，去掉一個(gè)最低分，然后去平均值”。顯然在體育比賽打分中，用中位數(shù)就不合適。所以我們說平均數(shù)和中位數(shù)就是一對(duì)死纏爛打的狐朋狗友！后面的內(nèi)容會(huì)討論這對(duì)概念在圖像處理和數(shù)據(jù)挖掘中的重要應(yīng)用。這涉及到簡(jiǎn)單平滑、中值濾波、K-means算法、k-Median算法等。你應(yīng)該注意體會(huì)前面談到的推衍創(chuàng)新思維。這能很好地幫助你舉一反三。

二、簡(jiǎn)單平滑與中值濾波：同時(shí)聯(lián)系到LeetCode上一道Hard級(jí)別的題目

現(xiàn)實(shí)中圖像因?yàn)槭艿江h(huán)境的影響，很容易被噪聲所污染。如下圖中的左上所示，這是一幅被椒鹽噪聲污染的圖像。噪聲體現(xiàn)為原本過渡平滑的（自然圖像）區(qū)域中一個(gè)突兀的像素值。處理它最簡(jiǎn)單的策略是用一個(gè)低通濾波器對(duì)信號(hào)進(jìn)行過濾。比如可以采用簡(jiǎn)單平滑算法。說白了，就是針對(duì)某個(gè)像素點(diǎn)，在其領(lǐng)域的一個(gè)小窗口內(nèi)（例如3×3），對(duì)所有像素值取平均，然后用這個(gè)平均值來代替窗口中心位置的像素值。這樣就能縮小噪聲和非噪聲像素之間的差距。也就是讓原本高的值變低一點(diǎn)，而讓原本低的值變高一點(diǎn)。結(jié)果如左下圖所示。易見，簡(jiǎn)單平滑有一定效果，但是并不“完美”。舉個(gè)例子，現(xiàn)在有一杯堿性溶液（PH>7），我們不斷向其中加入純水來稀釋，結(jié)果PH值會(huì)越來越小。但是無論我們放多少水，這個(gè)值也不可能小于7。就算用盡全世界的水，它的整體仍然呈現(xiàn)堿性！

有沒有更好的辦法？如果你還沒有想到用中位數(shù)來替代均值，那么我覺得你的頭腦應(yīng)該不用再繼續(xù)讀下去了！既然（椒鹽）噪聲是一個(gè)異常值，那么顯然用中位數(shù)的方法來將其排掉是最好的選擇了，這就是所謂的“中值”濾波的基本思想。上圖右下就是采用中值濾波算法處理的圖像，顯然比簡(jiǎn)單平滑效果好。

但是，問題還沒完！你有沒有想過中值濾波相對(duì)于簡(jiǎn)單平滑的一個(gè)不足或者劣勢(shì)？是的，中值濾波的復(fù)雜度太高，計(jì)算起來那是相當(dāng)?shù)暮臅r(shí)。為什么我會(huì)想到這個(gè)話題。因?yàn)樽罱以诟挛业腗agicHouse（一款小型的圖像處理軟件http://blog.csdn.net/baimafujinji/article/details/50500757）。原來中值濾波算法是由我的劉師弟完成的。他曾經(jīng)是騰訊電腦管家研發(fā)的最初核心成員，現(xiàn)在已經(jīng)自主創(chuàng)業(yè)變成劉總了~我也順便遙祝他宏圖大展：）。劉同學(xué)寫的中值濾波沒有采用進(jìn)行任何優(yōu)化措施（當(dāng)然這也是為了算法演示之用，如果優(yōu)化了別人比較難把握原始算法的核心思想），每次執(zhí)行起來都跟感覺死機(jī)了一樣。于是最近我決定重寫這個(gè)算法。

有興趣的讀者不妨搜一下關(guān)于中值濾波的加速算法，結(jié)論是這方面的paper很多，但我不得不告訴你大部分其實(shí)沒啥創(chuàng)新。很多都是在串行轉(zhuǎn)并行上下功夫，我真不認(rèn)為這有啥意義。因?yàn)樗鼈兊幕A(chǔ)仍然是下面我要談的兩個(gè)算法。

首先來看Leetcode上一道評(píng)級(jí)為Hard級(jí)別的題目，如下。兩個(gè)有序數(shù)組，求它們合并后的中位數(shù)。這當(dāng)然沒啥難的，你可能會(huì)想到合并后用一個(gè)quicksort()，然后取中間位置。結(jié)果上當(dāng)然可以得到正確答案。但是一定要注意：題目要求算法時(shí)間復(fù)雜度是O(log(t))，t是合并后數(shù)組的長(zhǎng)度。但是，quicksort()的復(fù)雜度應(yīng)該是O(t·log(t))。顯然這樣做行不通。滿足時(shí)間復(fù)雜度要求才是本題的難點(diǎn)！

有沒有什么好方法？題目給出的提示是要用“分治法”策略。而且你應(yīng)該能想到是，我們要取中位數(shù)的兩個(gè)子數(shù)組本來就是有序的，這個(gè)條件必須要好好利用。所以，本題的策略應(yīng)該是：

該方法的核心是將原問題轉(zhuǎn)變成一個(gè)尋找第k小數(shù)的問題（假設(shè)兩個(gè)原序列升序排列），這樣中位數(shù)實(shí)際上是第(m+n)/2小的數(shù)。所以只要解決了第k小數(shù)的問題，原問題也得以解決。
首先假設(shè)數(shù)組A和B的元素個(gè)數(shù)都大于k/2，我們比較A[k/2-1]和B[k/2-1]兩個(gè)元素，這兩個(gè)元素分別表示A的第k/2小的元素和B的第k/2小的元素。這兩個(gè)元素比較共有三種情況：>、<和=。如果A[k/2-1]<B[k/2-1]，這表示A[0]到A[k/2-1]的元素都在A和B合并之后的前k小的元素中。換句話說，A[k/2-1]不可能大于兩數(shù)組合并之后的第k小值，所以我們可以將其拋棄。反之亦然，所以當(dāng)A[k/2-1]>B[k/2-1]時(shí)，我們將拋棄B[0]到B[k/2-1]的元素。
當(dāng)A[k/2-1]=B[k/2-1]時(shí)，則已經(jīng)找到了第k小的數(shù)，也即這個(gè)相等的元素，將其記為m。由于在A和B中分別有k/2-1個(gè)元素小于m，所以m即是第k小的數(shù)。(這里可能有人會(huì)有疑問，如果k為奇數(shù)，則m不是中位數(shù)。當(dāng)然這種情況我們后面給出的代碼里已有做特殊考慮，但整個(gè)算法的大體思路并無不同)
通過上面的分析，我們即可以采用遞歸的方式實(shí)現(xiàn)尋找第k小的數(shù)。此外還需要考慮幾個(gè)邊界條件：
    如果A或者B為空，則直接返回B[k-1]或者A[k-1]；
    如果k為1，我們只需要返回A[0]和B[0]中的較小值；
    如果A[k/2-1]=B[k/2-1]，返回其中一個(gè)；
最終實(shí)現(xiàn)的代碼為：

通過對(duì)上述LeetCode題目的討論，其實(shí)已經(jīng)可以給出我們一些優(yōu)化的想法了。來看下面這個(gè)圖，當(dāng)我們最初計(jì)算紅色像素的鄰域中值時(shí)，其實(shí)已經(jīng)得到了紅框中像素值的一個(gè)有序排列。然后在計(jì)算綠色像素的鄰域中值時(shí)，我們把滑塊向后移動(dòng)。這時(shí)為了避免重復(fù)計(jì)算，一定要充分利用之前的有序結(jié)果。剔除最左面三個(gè)像素后的紅框中的6個(gè)像素仍然有序，這時(shí)只要把新加入的綠框中的三個(gè)元素也做排序，然后得到兩個(gè)有序的序列，是不是就變成了上我們討論的問題了？而且，這個(gè)算法面對(duì)更大的滑動(dòng)窗口時(shí)，優(yōu)勢(shì)會(huì)更為明顯。

但是，如果我們只想計(jì)算3×3鄰域內(nèi)的中值，其實(shí)還有另外一個(gè)選擇。例如下面的鄰域

0   1   2

3   4   5

6   7   8

首先對(duì)窗口內(nèi)的每一列分別計(jì)算最大值，中值和最小值，這樣就得到了3組數(shù)據(jù)

最大值組：Max0 = max[P0，P3，P6]，Max1 = max[P1，P4，P7]，Max2 = max[P2，P5，P8]

中值組： Med0 = med[P0，P3，P6]，Med1 = med[P1，P4，P7]， Med2 = med[P2，P5，P8]

最小值組：Min0 = Min[P0，P3，P6]，Min1 = Min[P1，P4，P7]，Min2 = max[P2，P5，P8]
由此可以看到，最大值組中的最大值與最小值組中的最小值一定是9個(gè)元素中的最大值和最小值，不可能為中值，剩下7個(gè)；中值組中的最大值至少大于5個(gè)像素，中值組中的最小值至少小于5個(gè)像素，不可能為中值，剩下5個(gè)；最大值組中的中值至少大于5個(gè)元素，最小值組中的中值至少小于5個(gè)元素，不可能為中值，最后剩下3個(gè)要比較的元素，即
最大值組中的最小值Maxmin，中值組中的中值Medmed，最小值組中的最大值MinMax；找出這三個(gè)值中的中值為9個(gè)元素的中值。

采用上述方法，也會(huì)大大降低計(jì)算量?？梢娫O(shè)計(jì)一個(gè)好算法永遠(yuǎn)是那么的重要！

三、數(shù)據(jù)挖掘中的K-means和K-median

聚類是將相似對(duì)象歸到同一個(gè)簇中的方法，這有點(diǎn)像全自動(dòng)分類。簇內(nèi)的對(duì)象越相似，聚類的效果越好。支持向量機(jī)、神經(jīng)網(wǎng)絡(luò)所討論的分類問題都是有監(jiān)督的學(xué)習(xí)方式，現(xiàn)在我們所介紹的聚類則是無監(jiān)督的。其中，K均值（K-means）是最基本、最簡(jiǎn)單的聚類算法。

在K均值算法中，質(zhì)心是定義聚類原型（也就是機(jī)器學(xué)習(xí)獲得的結(jié)果）的核心。在介紹算法實(shí)施的具體過程中，我們將演示質(zhì)心的計(jì)算方法。而且你將看到除了第一次的質(zhì)心是被指定的以外，此后的質(zhì)心都是經(jīng)由計(jì)算均值而獲得的。

首先，選擇K個(gè)初始質(zhì)心（這K個(gè)質(zhì)心并不要求來自于樣本數(shù)據(jù)集），其中K是用戶指定的參數(shù)，也就是所期望的簇的個(gè)數(shù)。每個(gè)數(shù)據(jù)點(diǎn)都被收歸到距其最近之質(zhì)心的分類中，而同一個(gè)質(zhì)心所收歸的點(diǎn)集為一個(gè)簇。然后，根據(jù)本次分類的結(jié)果，更新每個(gè)簇的質(zhì)心。重復(fù)上述數(shù)據(jù)點(diǎn)分類與質(zhì)心變更步驟，直到簇內(nèi)數(shù)據(jù)點(diǎn)不再改變，或者等價(jià)地說，直到質(zhì)心不再改變。

基本的K均值算法描述如下：

根據(jù)數(shù)據(jù)點(diǎn)到新質(zhì)心的距離，再次對(duì)數(shù)據(jù)集中的數(shù)據(jù)進(jìn)行分類，如圖13-2(c)所示。然后，算法根據(jù)新的分類來計(jì)算新的質(zhì)心，并再次根據(jù)數(shù)據(jù)點(diǎn)到新質(zhì)心的距離，對(duì)數(shù)據(jù)集中的數(shù)據(jù)進(jìn)行分類。結(jié)果發(fā)現(xiàn)簇內(nèi)數(shù)據(jù)點(diǎn)不再改變，所以算法執(zhí)行結(jié)束，最終的聚類結(jié)果如圖13-2(d)所示。

對(duì)于距離函數(shù)和質(zhì)心類型的某些組合，算法總是收斂到一個(gè)解，即K均值到達(dá)一種狀態(tài)，聚類結(jié)果和質(zhì)心都不再改變。但為了避免過度迭代所導(dǎo)致的時(shí)間消耗，實(shí)踐中，也常用一個(gè)較弱的條件替換掉“質(zhì)心不再發(fā)生變化”這個(gè)條件。例如，使用“直到僅有1%的點(diǎn)改變簇”。

盡管K均值聚類比較簡(jiǎn)單，但它也的確相當(dāng)有效。它的某些變種甚至更有效， 并且不太受初始化問題的影響。但K均值并不適合所有的數(shù)據(jù)類型。它不能處理非球形簇、不同尺寸和不同密度的簇，盡管指定足夠大的簇個(gè)數(shù)時(shí)它通?？梢园l(fā)現(xiàn)純子簇。對(duì)包含離群點(diǎn)的數(shù)據(jù)進(jìn)行聚類時(shí)，K均值也有問題。在這種情況下，離群點(diǎn)檢測(cè)和刪除大有幫助。K均值的另一個(gè)問題是，它對(duì)初值的選擇是敏感的，這說明不同初值的選擇所導(dǎo)致的迭代次數(shù)可能相差很大。此外，K值的選擇也是一個(gè)問題。顯然，算法本身并不能自適應(yīng)地判定數(shù)據(jù)集應(yīng)該被劃分成幾個(gè)簇。最后，K均值僅限于具有質(zhì)心（均值）概念的數(shù)據(jù)。一種相關(guān)的K中心點(diǎn)聚類技術(shù)沒有這種限制。在K中心點(diǎn)聚類中，我們每次選擇的不再是均值，而是中位數(shù)。這種算法實(shí)現(xiàn)的其他細(xì)節(jié)與K均值相差不大，我們不再贅述。

最后我們給出一個(gè)實(shí)際應(yīng)用的例子。（代碼采用我最喜歡用做數(shù)據(jù)挖掘的R語(yǔ)言來實(shí)現(xiàn)）

一組來自世界銀行的數(shù)據(jù)統(tǒng)計(jì)了30個(gè)國(guó)家的兩項(xiàng)指標(biāo)，我們用如下代碼讀入文件并顯示其中最開始的幾行數(shù)據(jù)?？梢姡瑪?shù)據(jù)共分散列，其中第一列是國(guó)家的名字，該項(xiàng)與后面的聚類分析無關(guān)，我們更關(guān)心后面兩列信息。第二列給出的該國(guó)第三產(chǎn)業(yè)增加值占GDP的比重，最后一列給出的是人口結(jié)構(gòu)中年齡大于等于65歲的人口（也就是老齡人口）占總?cè)丝诘谋戎亍?br />

為了方便后續(xù)處理，下面對(duì)讀入的數(shù)據(jù)庫(kù)進(jìn)行一些必要的預(yù)處理，主要是調(diào)整列標(biāo)簽，以及用國(guó)名替換掉行標(biāo)簽（同時(shí)刪除包含國(guó)名的列）。

如果你繪制這些數(shù)據(jù)的散點(diǎn)圖，不難發(fā)現(xiàn)這些數(shù)據(jù)大致可以分為兩組。事實(shí)上，數(shù)據(jù)中有一半的國(guó)家是OECD成員國(guó)，而另外一半則屬于發(fā)展中國(guó)家（包括一些東盟國(guó)家、南亞國(guó)家和拉美國(guó)家）。所以我們可以采用下面的代碼來進(jìn)行K均值聚類分析。

對(duì)于聚類結(jié)果，限于篇幅我們?nèi)匀恢涣谐隽俗铋_始的幾條。但是如果用圖形來顯示的話，可能更易于接受。下面是示例代碼。

上述代碼的執(zhí)行結(jié)果如圖13-3所示。

現(xiàn)在如果我問能不能提出另外一種與k-means類似的算法，你會(huì)想到什么？如果你能從k-均值算法想到提出k-中值算法，那么你算是沒白讀這篇文章！觸類旁通，舉一反三這招你算真學(xué)會(huì)了。（我想我已經(jīng)無需再詳細(xì)介紹k-中值算法的細(xì)節(jié)了，基本上和k-means一樣，只是把所有均值出現(xiàn)的地方換成中值而已）這個(gè)思想看起好像很不起眼，但是你還別說，k-median算法還真的存在，而且是k-means算法的一個(gè)重要補(bǔ)充和改進(jìn)。你可能會(huì)說提出k-median算法的人絕對(duì)是撿了一個(gè)大便宜，這么輕輕松松地就提出了一個(gè)足以留名的算法。但其實(shí)我想說，真正想到這一點(diǎn)的人，功力也絕對(duì)不可小覷。冰凍三尺、非一日之寒。唯有基礎(chǔ)扎實(shí)，內(nèi)力深厚的大家才能擁有這般敏銳的創(chuàng)新嗅覺。