[發(fā)明專利]一種超市路徑推薦系統(tǒng)及其方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201810092935.5
• 申請(qǐng)日: 2018-01-31
• 公開（公告）號(hào): CN108416611B
• 公開（公告）日: 2020-12-04
• 發(fā)明（設(shè)計(jì)）人: 阮文俊;翁安林
• 申請(qǐng)（專利權(quán)）人: 佛山市順德區(qū)中山大學(xué)研究院;廣東順德中山大學(xué)卡內(nèi)基梅隆大學(xué)國(guó)際聯(lián)合研究院;中山大學(xué)
• 主分類號(hào): G06Q30/02
• 分類號(hào): G06Q30/02;G06Q30/06;G06Q10/04;G06K9/62
• 代理公司: 廣州嘉權(quán)專利商標(biāo)事務(wù)所有限公司 44205
• 代理人: 左恒峰

1.一種超市路徑推薦方法，其特征在于：包括以下步驟：

A、獲取數(shù)據(jù)，其中數(shù)據(jù)包括用戶行走路徑以及與用戶行走路徑一一對(duì)應(yīng)的購(gòu)買清單；

B、使用譜聚類算法對(duì)用戶行走路徑進(jìn)行聚類，并得到簇劃分集

C、根據(jù)簇劃分集計(jì)算其所有簇類的所有的商品概率分布以及平均簇類的商品概率分布；

D、根據(jù)用戶的當(dāng)前狀態(tài)判斷其所屬的簇類，并計(jì)算得到不同路徑下所有已抵達(dá)的商品概率總和；

E、采用A*算法為用戶推薦一條路徑上商品概率總和最大，并且路徑長(zhǎng)度相對(duì)較小的路徑；

其中，所述步驟B的具體步驟為：

B1、將每一條用戶行走路徑看做一個(gè)數(shù)據(jù)點(diǎn)，計(jì)算數(shù)據(jù)點(diǎn)與數(shù)據(jù)點(diǎn)之間的Levenshtein距離；

B2、將數(shù)據(jù)點(diǎn)之間的Levenshtein距離轉(zhuǎn)化成相對(duì)距離，并以此生成相似矩陣W，同時(shí)構(gòu)建度矩陣D；

B3、根據(jù)相似矩陣W以及度矩陣D計(jì)算得到拉普拉斯矩陣L,L＝D-W；

B4、構(gòu)建標(biāo)準(zhǔn)化后的拉普拉斯矩陣L_norm＝D^-1/2LD^-1/2；

B5、計(jì)算D^-1/2LD^-1/2最小的k₁個(gè)特征值各自所對(duì)應(yīng)的特征向量f，將各自對(duì)應(yīng)的特征向量f組成的矩陣按行標(biāo)準(zhǔn)化，最終組成n*k₁維的特征矩陣F；

B6、對(duì)特征矩陣F中的每一行作為一個(gè)k₁維的樣本，共n個(gè)樣本，用K-means聚類方法進(jìn)行聚類，聚類維數(shù)為k₂；

B7、得到簇劃分集C

所述步驟C的具體步驟為：從簇劃分集中取得簇類c_k，遍歷簇類c_k的所有數(shù)據(jù)點(diǎn)即所有用戶行走路徑，從而得到簇類c_k中商品出現(xiàn)頻率以及商品出現(xiàn)總次數(shù)，簇類c_k的商品概率分布等于各商品出現(xiàn)頻率除以總次數(shù)；同時(shí)計(jì)算通過聚類路徑簇類下的平均簇類，得到平均簇類的商品概率分布，其中k＝1，2···k₂，k₂為聚類維數(shù)。

2.根據(jù)權(quán)利要求1所述的一種超市路徑推薦方法，其特征在于：所述步驟A中獲取數(shù)據(jù)，數(shù)據(jù)還包括用戶位置、用戶個(gè)人信息、商品信息，其中所述用戶位置采用LBS技術(shù)進(jìn)行定位，所述用戶個(gè)人信息包括用戶年齡、性別、用戶曾經(jīng)的購(gòu)物行為、其他相似用戶以及用戶購(gòu)物車內(nèi)的商品信息，所述用戶購(gòu)物車內(nèi)的商品信息即為所述的與用戶行走路徑一一對(duì)應(yīng)的購(gòu)買清單，所述商品信息包括超市內(nèi)商品的類別、商品對(duì)應(yīng)的日期以及位置、商品的暢銷度。

3.根據(jù)權(quán)利要求1所述的一種超市路徑推薦方法，其特征在于：所述步驟D中根據(jù)用戶的當(dāng)前狀態(tài)判斷其所屬的簇類，并計(jì)算得到不同路徑下所有已抵達(dá)的商品概率總和，具體步驟為：若當(dāng)前用戶無行走路徑且已輸入目標(biāo)商品，判斷其所屬的簇類為平均簇類，然后以目標(biāo)商品為目的地，計(jì)算在閾值下到達(dá)目的地的所有路徑，以平均簇類下的商品概率分布為基準(zhǔn)，計(jì)算不同路徑下所有已抵達(dá)的商品概率總和；若當(dāng)前用戶已有行走路徑時(shí)，根據(jù)已有行走路徑判斷其所屬簇類，以所屬簇類下的商品概率分布為基準(zhǔn)，計(jì)算不同路徑下所有已抵達(dá)的商品概率總和。

4.根據(jù)權(quán)利要求3所述的一種超市路徑推薦方法，其特征在于：所述閾 值為路徑計(jì)算過程中允許的最大距離，所有路徑的距離均小于或等于閾 值。

5.根據(jù)權(quán)利要求1所述的一種超市路徑推薦方法，其特征在于：所述步驟E中采用A*算法為用戶推薦一條路徑上商品概率總和最大，并且路徑長(zhǎng)度相對(duì)較小的路徑，所述A*算法的計(jì)算式子為：

A＝G+H；

其中G為從起點(diǎn)開始沿著產(chǎn)生的路徑移動(dòng)到指定位置時(shí)的移動(dòng)實(shí)際耗費(fèi)；H為從指定位置移動(dòng)到目標(biāo)的預(yù)估耗費(fèi)，H值的大小通過歐幾里德距離方法進(jìn)行估計(jì)，計(jì)算公式為：

其中x和y分別為n維空間中的點(diǎn)的坐標(biāo)；

通過反復(fù)遍歷開啟列表內(nèi)的起點(diǎn)得到不同的A值的大小，具有最低A值的路徑為最終的推薦路徑。