[發(fā)明專利]一種基于N階近鄰分析聚類的配送中心選址方法

在審

• 申請?zhí)枺?/td>: 202010848654.5
• 申請日: 2020-08-21
• 公開（公告）號: CN112132184A
• 公開（公告）日: 2020-12-25
• 發(fā)明（設(shè)計(jì)）人: 張貴軍;陳馳;武楚雄;王浩文;李亭;周曉根
• 申請（專利權(quán)）人: 浙江工業(yè)大學(xué)
• 主分類號: G06K9/62
• 分類號: G06K9/62;G06Q10/04;G06Q10/08
• 代理公司: 杭州斯可睿專利事務(wù)所有限公司 33241
• 代理人: 王利強(qiáng)

1.一種基于N階近鄰分析聚類的配送中心選址方法，其特征在于：所述方法包括以下步驟：

1)根據(jù)候選點(diǎn)的地理位置信息，初始化為二維地理坐標(biāo)特征的樣本點(diǎn)數(shù)據(jù)集D＝{x₁,x₂,...,x_M}，M為候選點(diǎn)的數(shù)量，初始化聚類數(shù)目K＝1；

2)定義為樣本點(diǎn)x_i的一階近鄰距離，即x_i與數(shù)據(jù)集中其他樣本點(diǎn)之間的最近距離，為樣本點(diǎn)x_i的二階近鄰距離，即x_i與數(shù)據(jù)集中其他樣本點(diǎn)之間的第二近距離；依次類推，為x_i的n階近鄰距離；

3)計(jì)算樣本點(diǎn)的n階近鄰距離，過程如下：

3.1)從數(shù)據(jù)集D中取出一個(gè)目標(biāo)樣本點(diǎn)x_i，i∈{1,2,...,M}；

3.2)再從數(shù)據(jù)集D中取出不同于x_i的一個(gè)樣本點(diǎn)x_j，j∈{1,2,...,M}；

3.3)計(jì)算兩個(gè)樣本點(diǎn)x_i和x_j之間的歐式距離d_ij，其中d_ij＝||x_i-x_j||₂；

3.4)迭代步驟3.2)和步驟3.3)直到x_j取完數(shù)據(jù)集中除x_i之外的所有點(diǎn)，再將所求的距離按照從小到大排序，即得到樣本點(diǎn)x_i的n階近鄰距離，其中n∈{1,2,..,M-1}；

3.5)更新目標(biāo)樣本點(diǎn)x_i，即從數(shù)據(jù)集中隨機(jī)取出新的目標(biāo)樣本點(diǎn)x_i′，令x_i＝x_i′，迭代步驟3.2)、3.3)和步驟3.4)，直到x_i取完數(shù)據(jù)集中的所有樣本點(diǎn)為止；

4)計(jì)算樣本點(diǎn)的n階近鄰距離的平均值和平方均值其中

5)分析數(shù)據(jù)集中樣本點(diǎn)之間的離散程度，確定合適的聚類數(shù)目K值，過程如下：

5.1)計(jì)算數(shù)據(jù)集中樣本點(diǎn)的N階近鄰方差其中n∈{1,2,...,M-1}；

5.2)根據(jù)次序統(tǒng)計(jì)的相關(guān)原理，當(dāng)滿足時(shí)，和n+1滿足線性關(guān)系，其中ε是趨近于0的數(shù)；

5.3)根據(jù)5.1)計(jì)算得到的各個(gè)樣本點(diǎn)之間簇間方差的結(jié)果，代入中，當(dāng)滿足該式的不等關(guān)系時(shí)，更新K＝K+1；

6)從數(shù)據(jù)集D中隨機(jī)選取K個(gè)數(shù)據(jù)點(diǎn)作為聚類的初始均值向量T＝{t₁,t₂,L,t_K}；

7)計(jì)算樣本點(diǎn)x_i到各均值向量t_k的距離：dist(x_i,t_k)＝||x_i-t_k||₂，根據(jù)距離最近的均值向量確定x_i的簇標(biāo)記：λ_i＝arg min_{k∈{1,2,L,K}}dist(x_i,t_k)，將樣本點(diǎn)x_i劃入相應(yīng)的簇；

8)更新均值向量t_k：計(jì)算當(dāng)前簇中每一個(gè)樣本點(diǎn)到其他樣本點(diǎn)的距離之和，并將距離之和最小的樣本點(diǎn)記為新的均值向量t′_k，若t_k′≠t_k，則令t_k＝t_k′，迭代步驟7)，否則，進(jìn)行步驟9)；

9)當(dāng)前均值向量t_k均不再發(fā)生變化，將聚類后的簇劃分出來，此時(shí)最終的均值向量集合T中的K個(gè)均值向量所對應(yīng)的候選點(diǎn)即為配送中心的最佳選址位置。