大型商场智能导购策略与应用

叶小艳 邓可儿 钟彬胜 梁梓滢 卓圳豪 钟华钧

摘  要： 针对大型商场传统导航和搜索效率低的问题，设计了一种导购策略，采用改进后的A*算法实现最优路径的规划，根据混合交叉推荐技术进行数据采集与数据推荐，加强算法对复杂室内地图环境的适应性，提高推荐效率。构建了基于微信小程序的大型商场智能导购系统进行验证，在店铺搜索和推荐逻辑模型下，搜索效率提升了近50%，并解决了室内导航以及信息个性化推荐问题。

关键词： A*算法; 导购策略; 导航; 推荐; 搜索

中图分类号：TP309.7          文献标识码：A  文章编号：1006-8228（2021）08-17-04

Strategy of indoor navigation and shopping guide system for

shopping malls and its application

Ye Xiaoyan， Deng Ke'er， Zhong Binsheng， Liang Ziying， Zhuo Zhenhao， Zhong Huajun

（Department of network technology， Guangzhou Institute of software， Guangzhou， Guangdong 510990， China）

Abstract： In order to solve the low efficiency of traditional navigation and search in large shopping malls， a shopping guide strategy is designed， which uses improved A-Star algorithm to realize the optimal path planning， and according to the hybrid cross recommendation technology， carries out the data collection and data recommendation to strengthen the adaptability of the algorithm to the complex indoor map environment and improve the recommendation efficiency. An intelligent shopping guide system for large shopping malls based on WeChat mini program is built to make the verification. With the logic model of shop search and recommendation， the search efficiency has been improved by nearly 50%， and the problems of indoor navigation and personalized information recommendation are solved.

Key words： A-Star algorithm; shopping guide strategy; navigation; recommendation; search

0 引言

如今大型商場一般都会有商场智能导览导购系统，用于线路指引、自助查询、客户数据分析，也作为广告宣传和品牌推介。商场智能导购须解决以下关键技术问题：室内路径规划，室内环境布局搜索，根据用户喜好推荐商品，从而达到导购的目的。

关于室内路径规划与搜索的研究，主要集中在基于外部物理硬件设施的支持，如Shivam Verma^[1]“基于智能手机的室内导航系统”、ToshinoriKagawa^[2]“基于传感器的超宽带自主导航系统在商场的部署与实验”、Hongwei Ding^[3]“基于AP加权多重匹配近邻的室内指纹定位方法”。利用现有软硬件条件来优化解决方案，以达到节约成本、提高效率目的。

路线规划常见的算法是A*（A-Star）算法，通过比较当前路径栅格的启发式函数值来逐步确定下一个路径栅，即从初始点经由节点到目标点的估价函数。其优点是能够严格沿着最短路径搜索，但搜索点少，范围小;其缺点是当搜索点数多、搜索范围大时，搜索效率低。当前大型电商平台通过采集用户数据，对用户的购物的个性化偏好程度和购物行为等变量信息^[4]进行分析，挖掘用户的消费能力，向其精准推荐商品。在路径规划上，一些软件也会借助手机GPS、陀螺仪、WiFi等感知单元，实时获取更为丰富的时间、空间和出行状态信息来描绘用户个体出行过程，返回更加客观、精确的导航数据。本文正是结合以上两点，采用改进后的A*算法，实现最优路径规划，加强算法对复杂室内地图环境的适应性，根据混合交叉推荐^[5]等技术方法，实现根据用户喜好、有针对性地推荐商品。

1 智能导购策略算法设计

1.1 改进A*算法，实现最优路径规划

针对现有A*算法在移动的目标节点判别和计算时，出现大量节点在搜索的过程中被删除现象^[6]。在被删的节点中，也可能包括了最优路径节点，令搜索过程陷入“死循环”，从而导致无法搜索到目标路径。对商城导航中A*算法进行优化。首先，对A*算法的地图数据进行划分，获取有效的且可支持完成导航的地图数据。传统A*算法启发函数通常只考虑距离启发信息且均采用单次计算，其应用主要为二维平面的寻路，改进后的A*算法采用分层计算的思想，实现了室内三维空间跨楼层的最优路径寻路。在路线规划方法函数中加入相关限制，有效保证了最优路径的唯一性，同时实现了复杂室内地图环境下用户步行路线最短的个性化需求，进一步增强了算法对复杂室内地图环境的适应性。综合室内复杂地图环境下用户对最短距离和直行路程的需求，在位置计算中，引入同时考虑方向和距离启发信息的启发函数，把POI点与寻路节点分开处理，以映射的方式建立联系，有效避免了直接搜寻POI节点数据量大、速率低的问题。

1.2 混合交叉推荐算法

混合交叉推荐算法是关联分析算法和协同过滤算法的结合和改进，继承了协同过滤算法的优点，避免冷启动的问题，不仅具有协同过滤算法的实时性，还具备关联规则算法的实用性。混合推荐算法不需收集用户的个人信息，这不仅避免过于依赖于用户个人行为，也保证用户的个人隐私的安全，符合用户关注隐私的要求，还提高了推荐效率。

将每一个类别的集合使用一个链表存储，并将所有类别的集合使用到一个链表存储^[7]。其算法不仅比完全冷启动的协同过滤算法在精确性上更有优势，还保持了商品类型的一致性。与许多单一推荐技术相比，可以发现内部应用商品之间的关联，挖掘出跨电商商品之间的关系，给用户定制出更符合自身需求的个性化推荐方案。

混合交叉推荐算法主要分为两个部分，分别是数据采集与数据推荐。

⑴ 数据采集：采用用户搜索轨迹记录方式，用户搜索过的词条会记录在本机中，当短时间内，用户搜索过的两件物品（称为A与B）会被认为它们之间是有关联的，如果A或B是一个物品、店铺等，将获取它的分类名称，然后将A与B的分类名上传到数据模型中。如图1所示，给定一个数据集有a、b、c、d四个对象。

图1  对象关系图

在图的术语中，带权的为网，图1即是网结构。其邻接矩阵为：

其中为对象a与对象b的权值（a，b），使得：

对于所有对象，则有以下算式：

当对象a和对象b被搜索或者使用时，则两个对象的权值会发生变化，其中k为常数值：

如果无两个节点的数据，则初始化該两个节点。

⑵ 数据推荐：同样采用该用户搜索轨迹进行推荐，如该用户搜索过A物品或者店铺，系统将获取到A的分类名称，将其作为请求参数请求数据，系统将审核请求参数的正确性，如果正确，系统通过判定缺省值将噪声数据清除，在接下来生成数据模型中筛选与A关联性最高的三个类型，在获取类型后，系统进一步筛选出这三个类型店铺中综合评分最好的十个店铺推荐给用户。如A点，在矩阵中则有：。

混合交叉推荐算法将根据对象获取与该对象最高权值的对象。根据对象a将得到按顺序排序的对象c、对象d、对象b，则。

通过c、d、b三个对象去获取相匹配的各十个店铺，系统将根据这三十个店铺的综合评分，筛选出综合评分最高的十个店铺推荐给用户。

通过对用户整体行为和物品关联性的记录，同时减少噪声数据量大但获取有价值数据少的低回报率的处理行为，进行高回报率的处理行为。

2 智能导购系统应用

基于改进的A*算法和混合交叉推荐算法，设计了基于微信小程序的大型商场智能导购系统。该系统由两个功能模块组成：室内导航服务和个性化商铺推荐。在导航部分，提供2D/3D导图展示、路线规划的制定和查找、店铺等位置查询服务。在个性化搜索部分，根据用户活动痕迹推荐可能喜欢商品或商铺，同时内嵌了合作商铺的广告和活动信息。

用户进入商场，打开本应用后可以看到该商场的3D布局地图，能清晰找到自己的位置和每个商铺的位置，输入起点和终点进入导航后，会即时规划出最适合的路线、计算出行走时间，为用户“指路”，并有语音播报辅助。在个性化商铺推荐方面，会根据用户的搜索记录、浏览记录、光顾频繁度等推荐可能喜欢的店铺。

3 商场智能导购系统实现

3.1 Redis数据库

考虑商城智能导购系统需要对用户的行为进行收集，而用户的搜索行为频繁是不可避免的。如果在这一场景下，采用结构化数据库，将会非常影响系统的用户体验。参考了众多的中间件的优缺点，最终选择了非结构数据库Redis作为数据存储。一方面Redis是内存数据库，查询和存储速度快，适合频繁的用户行为场景;另一方面Redis存在多种数据结构，如String、Set、Sort Set、Geo等，灵活的数据结构可以方便地为系统提供数据存储结构。其中有序集合Sort Set可以根据权值自动进行高效排序，适合系统当前的场景。

3.2 店铺推荐

店铺推荐使用Redis的有序集合实现，有序集合的名称即是主节点，有序集合的元素是其他节点，元素的分数即是与主节点的关联性。

接着，考虑节点的存储和连线问题，需要将参数进行分析、存储与持久化。节点的连线和权值的增加实现如下：

创建一个链表，用于存储所有的节点

for （int i=0; i<链表的长度; i++） {

a<-从链表中弹出头元素

for（Object b：链表） {

relate（a，b）=relate（a，b）+1

relate（b，a）=relate（b，a）+1

}

将a存入到链尾表

}

最终是推荐。需要根据关键字返回对应的高关联性的类别，并且在多个种类集合中，混合输出元素，例如存在n个集合中，则前n个元素应该是n个集合中的第一个元素，第n+1元素應该是第1个集合的第2个元素。店铺推荐逻辑模型如图2所示。

图2  店铺推荐逻辑模型

3.3 店铺搜索

由于一个小类别与大类别是n与n的关系，使用Redis的集合存储时比较方便。根据用户的输入一个或多个关键字，搜索出高度符合的店铺。店铺搜索逻辑模型如图3所示。

图3  店铺搜索逻辑模型

去重和排序的算法如下：

创建一个HashMap，用于存储元素

if（HashMap中不存在该元素） {

将该元素作为键，值设定为1

} else {

将该元素的值自增1

}

定义一个排序器，对HashMap根据值进行排序，规则为降序

返回记录

3.4 实现效果

在实际应用测试过程中，发现该导购系统能个性化推荐商品并实现商品所在位置的最优化路线规划，获得快速导航的效果。如在太古汇商场，输入“乔丹”，程序显示“F2”（第2层），并准确标识具体位置。“个性化商铺”或“商品推荐效果”也可以根据用户搜索和访问记录自动生成，“kefto”（太古汇商场F1）、“薯皇”（太古汇商场F1）、“双鹿”（太古汇商场F3）。根据用户的输入一个或多个关键字，搜索出高度符合的店铺，如搜索“衣服”显示“NIKE”（体育用品）、“TRIES”（体育用品）、“雅鹿”（服饰）、“阿迪多纳”（体育用品）。

从搜索的效果看，模型与算法改进后，搜索效率如图4所示，搜索的整体效率提升了近50%，实现了达到加速导航算法的目的。

图4  模型与算法改进前后搜索效率比较

4 结束语

本系统采用了Redis的有序集合，使用模拟连线和关联算法、对象元素交叉存储算法，实现了个性化店铺推荐，有效地提高了个性化推荐的效率;使用去重和排序算法，实现了智能店铺搜索，使系统能根据关键词，搜索出高度符合的店铺。在个性化推荐方面做到了信息的有效过滤，解决了冷启动、数据稀疏性及精确性所带来的推荐信息不准确或不精细的问题，从而使推荐内容更贴合用户实际，提高用户们的体验感。在室内导航方面做到了在商场内实现了最优路线规划和导航，解决了用户在商场无法快速准确到达目的地的问题。纵观互联网时代发展的潮流，对于研究者而言，如何解决更深入的路線规划算法问题，如何解决信息推荐的协同过滤算法问题，这需要后面进一步的探索与检验。

参考文献（References）：

[1] Shivam Verma;Rohit Omanwar;V Sreejith;G S Meera. A

smartphone based indoor navigation system[C]//2016 28th International Conference on Microelectronics. Giza， USA： IEEE Press，2017：402-405

[2] Toshinori Kagawa;Huan-Bang Li;Ryu Miura. A UWB

navigation system aided by sensor-based autonomous algorithm-Deployment and experiment in shopping mall[C]//2014 International Symposium on Wireless Personal Multimedia Communications.Giza，USA： IEEE Press，2017：402-405

[3] Hongwei Ding;Zhengqi Zheng;Yu Zhang. AP weighted

multiple matching nearest neighbors approach for fingerprint-based indoor localization[C]//2016 Fourth International Conference on Ubiquitous Positioning，Indoor Navigation and Location Based Services.Giza， USA： IEEE Press，2017：402-405

[4] 王姝静.电子商务平台个性化推荐强化学习算法研究[J].中

外企业家，2020.9：92

[5] 王腾宇.大数据时代下电子商务个性化推荐系统的分析与

设计[J].智库时代，2020.8：132-133

[6] 丁恒，黄全舟.基于属性特征的个性化旅游推荐算法研究[J].

智能计算机与应用，2020.10（1）：193-196

[7] 漆阳华，杨战平，黄清华.A*的改进路径规划算法[J].太赫兹

科学与电子信息学报，2009.4.

收稿日期：2021-03-11

作者简介：刘聪（1995-），女，陕西西安人，硕士研究生，主要研究方向：服务计算、服务组合。

通讯作者：杨怀洲（1970-），男，陕西西安人，博士，副教授，主要研究方向：物联网、服务计算。