[[217139]]

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

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

K-Means 算法

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

應(yīng)用

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

客戶服務(wù) 

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

集群計(jì)算 

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

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

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

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

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

它是如何工作的

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

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

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

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

步驟1 

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

k：集群的數(shù)量

Xij：示例i的第j個(gè)特征值

μij：示例i的第j個(gè)特征的聚類中心(類似于X，因?yàn)榫垲愔行氖请S機(jī)選擇的)

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

或者，更簡(jiǎn)化，計(jì)算量更少:

步驟2 

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

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

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

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

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

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

新的計(jì)算方法如下： 

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

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

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

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

算法會(huì)出錯(cuò)嗎?

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

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

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

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

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

色彩還原

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

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

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

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

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

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

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

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

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

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