国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

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

2021-10-18 08:13:18羅平娟張勝禮
現(xiàn)代計算機(jī) 2021年24期
關(guān)鍵詞:中心點貨車數(shù)據(jù)挖掘

羅平娟,張勝禮

(興義民族師范學(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ù)時代。

猜你喜歡
中心點貨車數(shù)據(jù)挖掘
貨車
幼兒畫刊(2023年12期)2024-01-15 07:06:14
探討人工智能與數(shù)據(jù)挖掘發(fā)展趨勢
Scratch 3.9更新了什么?
電腦報(2020年12期)2020-06-30 19:56:42
如何設(shè)置造型中心點?
電腦報(2019年4期)2019-09-10 07:22:44
貨車也便捷之ETC新時代!——看高速公路貨車ETC如何實現(xiàn)
基于并行計算的大數(shù)據(jù)挖掘在電網(wǎng)中的應(yīng)用
電力與能源(2017年6期)2017-05-14 06:19:37
學(xué)與玩(2017年6期)2017-02-16 07:07:24
治超新規(guī)實施在即 深究貨車非法改裝亂象
專用汽車(2016年9期)2016-03-01 04:16:52
漢字藝術(shù)結(jié)構(gòu)解析(二)中心點處筆畫應(yīng)緊奏
一種基于Hadoop的大數(shù)據(jù)挖掘云服務(wù)及應(yīng)用
淄博市| 阳西县| 游戏| 斗六市| 习水县| 集贤县| 张家口市| 乃东县| 和龙市| 原平市| 双流县| 柯坪县| 永泰县| 永善县| 安平县| 德州市| 竹北市| 双鸭山市| 伊通| 航空| 拉萨市| 巫溪县| 云南省| 平武县| 广饶县| 白城市| 英吉沙县| 乐都县| 昆明市| 周宁县| 张家口市| 南岸区| 阳朔县| 永济市| 鹤庆县| 淮阳县| 栾城县| 黎川县| 温宿县| 双柏县| 什邡市|