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

　　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;

　　}

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

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

　　0 1 2

　　3 4 5

　　6 7 8

　　首先對窗口內的每一列分別計算最大值，中值和最小值，這樣就得到了3組數據

　　最大值組：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ì )大大降低計算量?？梢?jiàn)設計一個(gè)好算法永遠是那么的重要!

　　三、數據挖掘中的K-means和K-median

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

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

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

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

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

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

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

　　最后我們給出一個(gè)實(shí)際應用的例子。(代碼采用我最喜歡用做數據挖掘的R語(yǔ)言來(lái)實(shí)現)

　　一組來(lái)自世界銀行的數據統計了30個(gè)國家的兩項指標，我們用如下代碼讀入文件并顯示其中最開(kāi)始的幾行數據?？梢?jiàn)，數據共分散列，其中第一列是國家的名字，該項與后面的聚類(lèi)分析無(wú)關(guān)，我們更關(guān)心后面兩列信息。第二列給出的該國第三產(chǎn)業(yè)增加值占GDP的比重，最后一列給出的是人口結構中年齡大于等于65歲的人口(也就是老齡人口)占總人口的比重。

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

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

　　對于聚類(lèi)結果，限于篇幅我們仍然只列出了最開(kāi)始的幾條。但是如果用圖形來(lái)顯示的話(huà)，可能更易于接受。下面是示例代碼。

　　上述代碼的執行結果如圖13-3所示。

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