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

　　vector& nums2, int size2, vector::iterator it2, int k)

　　{

　　//Always assume that size1 is equal or smaller than size2

　　if (size1 > size2)

　　return findKth(nums2, size2, it2, nums1, size1, it1, k);

　　if (size1 == 0) return *(it2+k-1);

　　if (k == 1) return min(*it1, *it2);

　　//Divide k into two parts

　　int offset1 = min(k / 2, size1);

　　int offset2 = k - offset1;

　　if (*(it1+offset1-1) <= *(it2+offset2-1))

　　{

　　return findKth(nums1, size1 - offset1 , it1+offset1, nums2, offset2, it2, k - offset1);

　　}

　　else

　　{

　　return findKth(nums1, offset1, it1, nums2, size2 - offset2, it2+offset2, k - offset2);

　　}

　　}

　　double findMedianSortedArrays(vector& nums1, vector& nums2) {

　　int m = nums1.size();

　　int n = nums2.size();

　　int total = m + n;

　　double result = findKth(nums1, m, nums1.begin(), nums2, n, nums2.begin(), (total + 1) / 2);

　　if ((total & 1) == 0) //Odd

　　{

　　result = (result + findKth( nums1, m, nums1.begin(), nums2, n, nums2.begin(), total / 2 + 1)) / 2;

　　}

　　return result;

　　}

　　通過對(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)勢會(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)是最基本、最簡單的聚類算法。

　　在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均值聚類比較簡單，但它也的確相當(dāng)有效。它的某些變種甚至更有效， 并且不太受初始化問題的影響。但K均值并不適合所有的數(shù)據(jù)類型。它不能處理非球形簇、不同尺寸和不同密度的簇，盡管指定足夠大的簇個(gè)數(shù)時(shí)它通?？梢园l(fā)現(xiàn)純子簇。對(duì)包含離群點(diǎn)的數(shù)據(jù)進(jìn)行聚類時(shí)，K均值也有問題。在這種情況下，離群點(diǎn)檢測和刪除大有幫助。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語言來實(shí)現(xiàn))

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

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

　　如果你繪制這些數(shù)據(jù)的散點(diǎn)圖，不難發(fā)現(xiàn)這些數(shù)據(jù)大致可以分為兩組。事實(shí)上，數(shù)據(jù)中有一半的國家是OECD成員國，而另外一半則屬于發(fā)展中國家(包括一些東盟國家、南亞國家和拉美國家)。所以我們可以采用下面的代碼來進(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)新嗅覺。