[[217139]]

在本文中，作者提出了使用k-means算法來對圖像進行色彩還原，介紹算法的步驟，同時應(yīng)用在圖像上，通過對比還原前后的圖像，來證明k-means算法的有效性。

k-means是機器學(xué)習(xí)中***、最廣泛使用的算法之一。在這篇文章中，將使用k-means算法來減少圖像上的顏色(但不減少像素)，從而也減少了圖像的大小。在這個領(lǐng)域不需要任何基礎(chǔ)知識，因為可執(zhí)行應(yīng)用程序文件（大小為150MB,這是由于長時間的Spark依賴）已經(jīng)提供了友好的用戶界面。所以你可以很容易地用不同的圖像來做實驗。在GitHub上有完整可用的執(zhí)行代碼。

K-Means 算法

k-mean算法是一種非監(jiān)督型學(xué)習(xí)算法，將相似的數(shù)據(jù)分成不同的類別或集群。它是無監(jiān)督型算法，因為數(shù)據(jù)沒有被標(biāo)記，而且算法不需要對相似數(shù)據(jù)進行分類的反饋（可能是預(yù)期類別的數(shù)量——稍后再討論）。

應(yīng)用

k- means算法的一些應(yīng)用包括客戶服務(wù)、集群計算、社交網(wǎng)絡(luò)和天文數(shù)據(jù)分析。

客戶服務(wù) 

假設(shè)有大量與客戶相關(guān)的數(shù)據(jù)，并且希望更多地了解所擁有的客戶類型，從而可以更好地為特定群體服務(wù)。也許你要生產(chǎn)牛仔褲和t恤，所以你需要在一個特定的國家將人以身材大小進行分組，這樣你就能知道生產(chǎn)什么尺寸更合適。

集群計算 

從性能角度來看，將某些計算機分組在一起比較好;例如，從網(wǎng)絡(luò)的角度來看，交換機適合聚集在一起工作，或者提供相似的計算服務(wù)。K-means算法可以將相似功能的計算機分在一組，這樣就可以進行更好的布局和優(yōu)化。

社交網(wǎng)絡(luò) 

在社交網(wǎng)絡(luò)中，你可以通過客戶關(guān)系、偏好、相似性等來對他們進行分組，并從營銷的角度更好地對客戶進行定位。基于提供的數(shù)據(jù)的輸入，k-means算法可以幫助我們從不同的角度對相同的數(shù)據(jù)進行分類。

天文數(shù)據(jù)分析 

k-means也用于了解星系的形成，以及在天文數(shù)據(jù)中尋找內(nèi)聚性。

它是如何工作的

k-means算法有兩個步驟。假設(shè)把數(shù)據(jù)分成四組，執(zhí)行以下步驟。

注意：在開始任何步驟之前，k-means算法會從數(shù)據(jù)中隨機抽取三個樣本，稱為聚類中心。

• 它檢查每一個數(shù)據(jù)樣本，會根據(jù)它們與開始隨機選擇的聚類中心的相似程度，來對它們進行分類。
• 它使聚類中心與相似的同類點更接近(第1步的分組)。

重復(fù)這些步驟，直到聚類中心沒有顯著的移動。下面使用簡單數(shù)據(jù)進行算法執(zhí)行。 

步驟1 

現(xiàn)在繼續(xù)解釋步驟1是如何實現(xiàn)的。如果你不熟悉多維特性數(shù)據(jù)。首先來介紹一些變量：

k：集群的數(shù)量

Xij：示例i的第j個特征值

μij：示例i的第j個特征的聚類中心(類似于X，因為聚類中心是隨機選擇的)

在這個步驟中，通過迭代，計算它們與聚類中心的相似度，并將它們放入合適的類別中。更確切地說，這是通過一個樣本的歐幾里得距離來計算的，并從最微小的距離中選取中心。由于中心點是隨機選擇的，因此將所有特征點與中心點的歐幾里德距離相加。

或者，更簡化，計算量更少:

步驟2 

從圖上看，這一步將中心點向步驟1中相似的分組進行移動。更準(zhǔn)確地說，就是取所有與中心點相似或?qū)儆谠摲纸M的點的平均值(步驟1的分組)，來計算每個中心的新位置。

例如，如果有4個集群和第1步驟之后的103個示例，那么有以下結(jié)果：

μ1 = 20表示標(biāo)號1-20示例的特征中心是20 

μ2=10 表示標(biāo)號21-31示例的特征中心是10 

μ3=30表示標(biāo)號32-62示例的特征中心是30 

μ4=40 表示標(biāo)號63-103示例的特征中心是40

新的計算方法如下： 

這是所有數(shù)據(jù)的平均值，類似于一個特定的中心。

重復(fù),重復(fù),重復(fù)…何時停止?

重復(fù)第1步和第2步，直到如圖形上顯示的，中心向數(shù)據(jù)集群移動的越來越近，才會得出新的中心。該算法會一直運行，直到對結(jié)果滿意時，就需要明確地告訴它，這樣它就可以停止了。一種方法是，當(dāng)?shù)鷷r，中心體不會在圖中移動，或者它的移動非常少。形式上說，可以計算成本函數(shù)，這基本上就是在步驟1中所計算的平均值：

μc是Xi的中心值。每個示例都可以是不同組或中心的一部分。每次迭代成本都會與之前的成本相比較，如果變化真的很低，就停止它。例如，如果改進(成本函數(shù)的差異)是0.00001(或者其他認(rèn)為合適的值)，那就可以停止了，因為繼續(xù)下去就沒有意義了。

算法會出錯嗎?

通常不會出錯，但眾所周知，k-means算法僅能達(dá)到局部***，而不是全局***。在這種情況下，k-means算法無法發(fā)現(xiàn)更加明顯的分組，如下圖所示：

幸運的是，解決方案相當(dāng)簡單——只要用k-means算法多運行幾次，然后選擇***的結(jié)果就好了。這個解決方案很有幫助，因為在一開始，隨機初始化k-means算法，比方說，運行10次，那么會得出局部***解。當(dāng)然，這增加了運行時間，因為它運行了很多次，卻只需要一個結(jié)果。另一方面，完全可以在并行的甚至是不同的集群上運行算法，所以通?？梢宰鳛橐粋€工作解決方案。

當(dāng)然，k-means算法比我所介紹的要多，所以強烈推薦這篇文章，以獲得更深入的見解。

算法的執(zhí)行和結(jié)果

在本節(jié)中，將運行應(yīng)用程序（也可以下載代碼），并通過一些細(xì)節(jié)來了解k-means算法如何進行色彩還原。

色彩還原

需要說明的是，k-means算法不是減少圖像上的像素，而是通過將相似的顏色組合在一起，以此來減少圖像的顏色數(shù)量。一個正常的圖像通常有幾千個甚至更多的顏色，所以減少顏色的數(shù)量可以顯著減少文件的大小。

為了說明減少顏色的數(shù)量有助于減少圖像大小，來看一個例子。假設(shè)有一個1280x1024像素的圖像，對于每個像素，有一個簡單的顏色表示(RGB 24位，8位紅，8位綠色，8位藍(lán)色)?？偠灾枰?280 * 1024 * 24 = 31457280位或30MB來表示圖像?，F(xiàn)在，把整體顏色減到16種，這意味著不需要24位像素，而是4位來代表16種顏色?，F(xiàn)在，有1280 * 1024 * 4 = 5MB，這也就少占了6倍的內(nèi)存。當(dāng)然了，圖像看起來不會像之前那樣***(現(xiàn)在只有16種顏色)，但肯定能找到一個合適的圖像。

執(zhí)行和結(jié)果

執(zhí)行算法的最簡單方法是下載JAR包，并使用自己的圖像來執(zhí)行(需要安裝Java)。我的電腦大約需要花一分鐘的時間來運行，使顏色減少到16種(高CPU和內(nèi)存會更好，因為Spark是并行運行的)。在用戶界面中，可以選擇想要嘗試的圖像文件，也可以選擇減少圖像上顏色的數(shù)量。下面是一個用戶界面和結(jié)果的例子：

可以注意到，文件大小減少了4倍，但最終的圖像看起來并不是那么糟糕。多運行幾次它可能會帶來更好的效果。再試試24種顏色：

這看起來明顯好一些，尺寸也沒有增加多少(只有0.08 MB)。似乎在24到28之間是這個圖像***的視覺效果。

盡管結(jié)果看起來不錯，但選擇***圖像是一項手工任務(wù)。畢竟，我們正在執(zhí)行和挑選最適合視覺的圖像。

相信這個問題可以用多種方法來解決。

其中一個解決方案是簡單地計算原始圖像上的所有顏色，并在此基礎(chǔ)上，定義用于圖像的顏色數(shù)量，同時仍然保持圖像看起來不錯。這一過程可以通過使用像線性回歸這樣的機器學(xué)習(xí)預(yù)測算法來完成。通過賦予圖像不同的顏色來訓(xùn)練算法，同時，對于每個圖像來說，它們看起來仍然很好。在給出了一些重要的示例之后，該算法根據(jù)不同的圖像學(xué)習(xí)了如何減少到***顏色數(shù)量?，F(xiàn)在是時候讓線性回歸算法預(yù)測下一個圖像的顏色會減少多少了。

可以下載代碼（https://github.com/klevis/KMeansImageColorReduction）并在Java IDE上運行它。當(dāng)然，如果不想在源代碼中運行，只需下載代碼并運行maven：mvn clean install exec:java。