基于K-means聚類算法的物流配送方案設(shè)計(jì)

羅平娟，張勝禮

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

0 引言

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

1 K-means算法的基本思想

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

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

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

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

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

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

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

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

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

（2）對(duì)于n=1,2,…N

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

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

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

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

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

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

2.1 問題的提出和分析

貴州省興義市某物流公司要給興義市黃草街道的100個(gè)客戶配送貨物。在“雙十一”期間由于公司車輛有限，現(xiàn)分別設(shè)計(jì)兩套備用方案進(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語言實(shí)現(xiàn)K-means算法[6]

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

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

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

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

圖1 5輛貨車配送

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

圖2 2輛貨車配送

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

3 結(jié)語

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

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

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

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

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

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

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