羅平娟,張勝禮
(興義民族師范學(xué)院,信息技術(shù)學(xué)院,興義562400)
在數(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é)約人力物力資源。
K-means算法是一種使用較為廣泛的聚類算法,其中K表示類簇個數(shù),means表示類簇內(nèi)數(shù)據(jù)對象的均值,它是將各個聚類子集內(nèi)的所有數(shù)據(jù)樣本的均值作為該聚類的代表點,通過迭代過程把數(shù)據(jù)劃分為不同的類別,使得評價聚類性能的準(zhǔn)則函數(shù)達(dá)到最優(yōu)[2]。
(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é)果的來運行。
輸入是樣本集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)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è)計。
貴州省興義市某物流公司要給興義市黃草街道的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)行合理的配送。
首先,導(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í)道路上比較有效的方法和途徑。
通過實踐的應(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ù)時代。