羅平娟，張勝禮

（興義民族師范學(xué)院，信息技術(shù)學(xué)院，興義562400）

0 引言

在數(shù)據(jù)挖掘的眾多算法中，聚類算法是機(jī)器學(xué)習(xí)的入門基礎(chǔ)算法，同時也是作為數(shù)據(jù)挖掘算法中其他分析算法的一個預(yù)處理步驟。K-means是迭代動態(tài)聚類算法中的一種，也被稱為K-平均或者K-均值算法，是一種無監(jiān)督學(xué)習(xí)的方法，是許多領(lǐng)域中常用的統(tǒng)計數(shù)據(jù)分析技術(shù)。在物流迅速發(fā)展的現(xiàn)代社會，設(shè)計一個合理、優(yōu)化、高效率的配送方案可以大幅度提高工作效率，基于K-means算法設(shè)計的思想，使用Python語言強(qiáng)大的matplotlib、numpy庫等作為基礎(chǔ)編程語言[1]，通過迭代過程把配送點的數(shù)據(jù)集劃分為不同的區(qū)域類別，以就近原則分配各區(qū)域的配送車輛和人員，能有效節(jié)約人力物力資源。

1 K-means算法的基本思想

K-means算法是一種使用較為廣泛的聚類算法，其中K表示類簇個數(shù)，means表示類簇內(nèi)數(shù)據(jù)對象的均值，它是將各個聚類子集內(nèi)的所有數(shù)據(jù)樣本的均值作為該聚類的代表點，通過迭代過程把數(shù)據(jù)劃分為不同的類別，使得評價聚類性能的準(zhǔn)則函數(shù)達(dá)到最優(yōu)[2]。

1.1 K-means算法的步驟[3]

（1）首先，我們隨機(jī)選取K個對象作為初始的聚類中心，要想知道使用的類的數(shù)量，需要快速地查看一下數(shù)據(jù)，并嘗試識別各種不同的分組。

（2）然后計算每個對象與各個聚類中心之間的距離，把每個對象分配給距離它最近的聚類中心。距離的度量手段有很多種，常用的歐氏距離、曼哈頓距離等。例如假設(shè)數(shù)據(jù)集X包含n個數(shù)據(jù)點，需要劃分到K個類。類中心為用集合U表示。聚類后所有數(shù)據(jù)點到各自聚類中心的差的平方和為聚類平方和用J表示，J值為：

聚類目標(biāo)是使得J值最小化。

（3）聚類中心以及分配給它們的對象就代表一個聚類。一旦全部對象都被分配了，每個聚類的聚類中心會根據(jù)聚類中現(xiàn)有的對象被重新計算。對一組迭代重復(fù)這些步驟，然后選擇看起來對它提供了最好結(jié)果的來運行。

1.2 K-means算法的流程[4]

輸入是樣本集D={x1,x2,…,xm}，聚類的簇樹K，最大迭代次數(shù)N；輸出是簇劃分C={C1,C2,…,Ck}

（1）從數(shù)據(jù)集D中隨機(jī)選擇K個樣本作為初始的K個質(zhì)心向量：{u1,u2,…,um}

（2）對于n=1,2,…N

1.3 3種K-means的優(yōu)化算法簡介[5]

（1）K-means初始化優(yōu)化K-means++。在K-means算法中K個初始化的質(zhì)心的位置完全是隨機(jī)選擇的，有可能導(dǎo)致算法收斂很慢，K-means++算法就是對K-means隨機(jī)初始化質(zhì)心的方法的優(yōu)化。

（2）K-means距離計算優(yōu)化Elkan K-means。此算法就是從距離簡化計算入手，減少一些不必要的距離的計算。

（3）K-means大樣本優(yōu)化Mini Batch K-means。在K-means算法中要計算所有的樣本點到所有的質(zhì)心的距離，如果遇到樣本量非常大，例如達(dá)到10萬、100萬以上是非常耗時的，Mini Batch就是用樣本集中的一部分的樣本來做傳統(tǒng)的K-means，這樣可以避免樣本量太大時的計算難題，算法收斂速度大大加快。

這3種優(yōu)化算法在后期數(shù)據(jù)挖掘的算法中再進(jìn)行應(yīng)用，本文中選取K-means的基本算法來介紹物流配送方案的設(shè)計。

2 基于K-means算法物流配送方案

2.1 問題的提出和分析

貴州省興義市某物流公司要給興義市黃草街道的100個客戶配送貨物。在“雙十一”期間由于公司車輛有限，現(xiàn)分別設(shè)計兩套備用方案進(jìn)行配送，一是假設(shè)公司只有5輛貨車進(jìn)行配送；二是假設(shè)公司只有2輛貨車進(jìn)行配送，客戶的地理坐標(biāo)在testSet.txt文件中，如何配送效率最高？

問題分析：可以使用K-means算法，將文件內(nèi)的地址數(shù)據(jù)聚成5類或者2類，從聚類結(jié)果把每類的客戶相近地址進(jìn)行劃分后，可以分配給同一輛貨車，以保證在最短距離類進(jìn)行合理的配送。

2.2 用Python語言實現(xiàn)K-means算法[6]

首先，導(dǎo)入Python語言中的numpy和matplotlib庫，進(jìn)行數(shù)據(jù)的統(tǒng)計分析和圖形的分析，再進(jìn)行這100個配送點之間精準(zhǔn)距離的計算，其代碼如下：

其次，實現(xiàn)K-means算法，因為種子的數(shù)量不確定擬定為K（K=5或者2），這時取K個數(shù)據(jù)點作為聚類的中心，確定每個簇的數(shù)據(jù)點和中心點。在初步確定簇的數(shù)據(jù)點和中心點后，把每個數(shù)據(jù)點依據(jù)最短距離分配到最近的簇，用while循環(huán)如此反復(fù)進(jìn)行中心點和數(shù)據(jù)點的確定直至達(dá)到最佳效果，其關(guān)鍵代碼如下：

最后，使用函數(shù) def show（dataSet, k, classCenter，clusterPoints）（詳細(xì)代碼部分略）進(jìn)行聚類結(jié)果的顯示，這里將在city.png圖片中根據(jù)每個對象的坐標(biāo)繪制點，把不同劃分區(qū)域的位置點用不同顏色進(jìn)行代表，并在相同的簇類找到其中心點，以便配送時進(jìn)行參考。程序結(jié)束部分設(shè)置K的值，對源代碼部分進(jìn)行調(diào)用和圖片的顯示，其代碼如下：

這樣，在通過計算分析后，客戶的地理坐標(biāo)位置就可以清晰地在地圖上進(jìn)行顯示，而且根據(jù)貨車數(shù)量的不同，將顯示不同的配送方案。如圖1所示，是5輛貨車的分配圖，圖中每個區(qū)域根據(jù)聚類的位置在循環(huán)多次后確定各個中心點，再根據(jù)中心點的鄰近數(shù)據(jù)確定區(qū)域的族，中心位置用紅色三角形標(biāo)注，圍繞中心位置的各數(shù)據(jù)點用不同顏色的圓形、矩形、三角形等進(jìn)行區(qū)分。這樣，從圖中可以很方便快捷合理對車輛進(jìn)行分配，節(jié)省了人力物力資源。

圖1 5輛貨車配送

但是，在實際分配中，我們還需要為用戶考慮更周全的方案，也就是當(dāng)5輛物流車遇到特殊情況，不能同時出發(fā)完成任務(wù)時的備選方案。例如，做出一個比較不理想的假設(shè)，當(dāng)只能有2輛貨車工作時，這時如圖2所示是僅僅只有2輛貨車的分配圖。這時，初始代碼沒有發(fā)生較大的改變，在設(shè)置的參數(shù)中把種子的數(shù)量K的值由5變成2，重新運行程序后即可得到新的分配方案。同理，當(dāng)用戶調(diào)整不同數(shù)量的貨車，我們都可以進(jìn)行較小改動即可完成用戶的需求。

圖2 2輛貨車配送

從上例方案的設(shè)計中可以看出，配送方案的代碼確定后，當(dāng)K=5和K=2的取值不同時可以生成不同的配送圖，這樣通過簡單的計算即可為客戶選擇最優(yōu)的方案既節(jié)省了勞力物力又提升了工作效率，很大程度上減輕了“雙十一”期間的配送壓力。所以，Kmeans算法結(jié)合Python語言中的numpy和matplotlib庫進(jìn)行數(shù)據(jù)的統(tǒng)計分析和圖形的分析，是一種較為實用、省時省力的優(yōu)化設(shè)計，能利用Python強(qiáng)大的第三方庫面向?qū)ο筮M(jìn)行有針對性的算法設(shè)計，這也是我們在進(jìn)行機(jī)器學(xué)習(xí)道路上比較有效的方法和途徑。

3 結(jié)語

通過實踐的應(yīng)用可以看出K-means算法是機(jī)器學(xué)習(xí)中的一種簡單實用的算法，利于初學(xué)者進(jìn)行實戰(zhàn)分析應(yīng)用，其優(yōu)點有：

（1）計算復(fù)雜度低，為O（Nmq），其中N是數(shù)據(jù)總量，m是類別（即k），q是迭代次數(shù)。

（2）原理簡單，實現(xiàn)容易，收斂速度快，算法的可解釋度比較強(qiáng)。

（3）聚類效果較好，可以發(fā)現(xiàn)新知識、新規(guī)律。

（4）聚類也是了解未知世界的一種重要手段，可以單獨實現(xiàn)，也可以作為其他學(xué)習(xí)任務(wù)的前驅(qū)過程。

但是K-means算法也存在一些弊端和不足：①需要提前確定K值（類別），分類的結(jié)果依賴于分類中心的初始化，每個樣本只能有一個類別（屬于“硬聚類”），對于帶狀（環(huán)繞）等非凸形狀沒有團(tuán)狀的數(shù)據(jù)點集區(qū)分度好；②初始聚類中心的選擇如果出現(xiàn)偏差對聚類結(jié)果有較大影響，使用迭代方法有時會得到局部最優(yōu)的結(jié)果；③K-means算法的時間開銷比較大、功能具有局限性等問題[7]。所以在初始聚類中心的選擇時會考慮使用K-means++或者Elkan K-means算法，在進(jìn)行大樣本分析時會考慮使用Mini Batch K-means。

通過此方案的設(shè)計與實現(xiàn)，讓我們感受到數(shù)據(jù)挖掘算法改變傳統(tǒng)思路的優(yōu)越性，但是僅一種算法的設(shè)計應(yīng)用還存在諸多的問題和不足，需要我們再深入學(xué)習(xí)把更多的數(shù)據(jù)挖掘算法進(jìn)行多方位多角度的結(jié)合，才能更好地進(jìn)行數(shù)據(jù)的分析匯總，才能適應(yīng)如今飛速進(jìn)步發(fā)展的大數(shù)據(jù)時代。