基于WIFI实时定位技术的偏好动线挖掘

1、第 29 卷第 5 期2012 年 5 月计算机应用与软件Computer Applications and SoftwareVol. 29 No 5May 2012基于 WIFI 实时定位技术的偏好动线挖掘孙莉戴浩洋李继云( 东华大学计算机科学与技术学院 上海 201620)随着 WIFI 实时定位技术的迅速发展，使得将 WIFI 实时定位系统应用于超市，便捷、准确地获得顾客的购物行为数据，从摘 要而分析顾客的偏好成为可能。提出区域吸引力的偏好性模型在考虑传统的区域通过次数因素的影响外，还充分考虑了区域停留时间因素和区域购买率因素对区域吸引力的影响。给出此模型下的顾客的偏好动线挖掘算法，算法

2、可以根据每一步发生区域转移的 概率统计得出顾客的偏好动线。实验结果表明所提出的方法是可行的，市场营销专家可以根据挖掘得到的偏好动线做出相应的 决策。关键词WIFI 实时定位 偏好性 偏好动线中图分类号文献标识码TP301 6APREFERRED SHOPPING PATHS MINING BASED ON WIFI REAL-TIMELOCATION TECHNOLOGYSun Li Dai HaoyangLi Jiyun( School of Computer Science and Technology，Donghua University，Shanghai 201620，China)As

3、 WIFI real-time location technology is developing rapidly，it is convenient and accurate to capture consumers' behavior dataAbstractby deploying WIFI RTLS in supermarkets，so that it's possible to analyze consumers'behavior by these data This paper proposes a preferencemodel to reflect zon

4、e attraction The model not only takes into account a zone's visited times，but also adds the influence of the zone' s stay time and purchase ratio According to the model，the paper proposes an efficient algorithm which is developed for mining consumers'preferred shopping paths It can get c

5、onsumers' preferred shopping paths by the zone-zone transition probabilities statistics in each step Experiment results demonstrate the feasibility of the method Given the preferred shopping paths，marketing experts can make appropriate decisionsKeywordsWIFI Real-time location Preference Preferre

6、d shopping path另外，市场营销专家往往需要直接对大量杂乱无章的原始数据进行分析，导致专家的工作量很大，而且容易忽视一些比较0引言隐蔽的规律。为了解决这个情况，需要对原始数据进行挖掘。在以前的顾客行为分析中，动线和购买数据是很难获得的。为了获取这些数据，典型的方法是让工作人员跟随顾客并记录 数据或者在超市中布置大量的监控摄像头。这些方法可以采集 大量数据用于分析，但是需要花费很大的人力物力。现在，随着 无线定位技术的发展，研究员可以轻松地采集顾客的动线数据， 从而使得市场研究员分析顾客行为以及研究商场布局策略更加 方便。目前无线定位技术有很多种，其中应用最广泛的是射频识 别技术(

7、RFID) ，应用的领域有: 零售业、服务业、制造业、物流业 等。但是由于 RFID 实时定位系统需要特别布置读写器及天 线，且读写器之间必须使用专用数据线相连，施工麻烦，同时这 些专门设备的普及程度不高，搭建时需要专业工程师，人工成本 高，而且其接收器价格昂贵，在大型超市中应用极少。而基于 WIFI 的实时定位系统可以利用 WIFI 基础设施进行定位跟踪， 无须重新搭建其他网络或设施，也不用购买单独的定位阅读器 等设备，AP 之间可以通过无线互联，以低成本方便地实现大面 积的无缝覆盖。本文所用的数据是使用 Ekahau 公司开发的 WIFI 实时定位系统来采集的。然而，目前的挖掘算法在判断动

8、线的回溯方面存在缺陷，而且使用的区域吸引力模型也不太能够合理地反映出区域的吸引力。本文提出一种新的表示区域吸引力的偏好性模型，同时提出一种新的挖掘偏好动线的算法，以求更加准确地得到顾客的偏好 动线。相关工作1WIFI 无线定位技术作为一种新型的无线定位技术，发展要比 RFID 晚，应用于零售行业也不多。据我们所知，目前还没有通过 WIFI 无线定位技术采集的数据来分析顾客行为的论文。但是基于 RFID 来分析顾客行为的论文有很多。虽然采集数据所使用的无线定位技术不相同，但是，在后期的数据分析、挖掘 上有很多可以借鉴的地方。收稿日期: 2011 08 18。孙莉，副教授，主研领域: 数据库技术。

9、戴浩洋，硕士。李继云，副教授。文献1使用一种从未应用在市场营销上的多变量聚类算法 k-medoids，这种算法是由 k-means 算法进化而来且比 k-means 算法更加健壮，它的另一个优点是可以处理有空间约束的数据 集。该文指出顾客在通道时更倾向于回溯，而不是穿过通道，并 提出了在购物中花费的时间有很重要的影响，且将所有动线分 成短期、中期、长期三组分别进行聚类分析。文献2提出将区域和动线离散化的定义，并提出一种个 体级别的概率模型，该模型同时抓住消费者购物行为的三个关 键方面: 顾客访问的区域，每一个区域停留的时间，是否购买了 该区域的商品，并得出商品购买多大程度上是源于商品内在本 质

10、的吸引力，还是源于特定区域的吸引力。文献3采用一种时间序列分析技术 EBONSAI 来分析顾 客的购买行为，将顾客分为高购买量和低购买量两类，并分析两 类顾客在动线方面的区别。文献4提出一种挖掘偏好动线的算法顾客访问矩阵 算法( CAM) 以及一种挖掘偏好动线与购买商品之间联系的算法顾客交易挖掘算法( CTM) 。文献1在研究中发现顾客在购物中的回溯规律，即顾客 在区域 A 的偏好选择是区域 B，在区域 B 的偏好选择亦可能是 区域 A ，该规律在文献2的研究中也得到了证实，但是文献4提出的 CAM 算法没有考虑到动线存在回溯的可能; 另外， 也没有考虑区域购买率权重对区域吸引力的影响。其中，

11、txm 是动线 x 在第 m 步的停留时间，Tmax_visit 是最大通过时间，Tmax_shortly_stay 是最大短暂停留时间，Tmax_normal_stay 是最大普通停留时间。定义 5 记 P 为顾客动线的集合。给定一个 Q P，x Q，所有的 x 有相同的 m-前缀，且在第 m + 1 步有 n 种不同的区 域可以选择。给定一个 KQ，yK，所有的 y 有相同的 m +1-前缀，且第 m + 1 步的选择均为第 k 种区域( k = 1，2，n) 。则在集合 Q 中，第 m + 1 步选择第 k 种区域的停留时间权重为:Wt= T( m +1) ki( m +1)iK其中，T

12、i( m + 1) 是动线 i 在第 m + 1 步的停留时间。定义 6 记 P 为顾客动线的集合。xP，购买函数:10 没有发生购买行为f( x，m) =发生了购买行为表示动线 x 在第 m 步的购买值。定义 7 记 P 为顾客动线的集合。给定一个 Q P，x Q，所有的 x 有相同的 m-前缀，且在第 m + 1 步有 n 种不同的区 域可以选择。给定一个 KQ，yK，所有的 y 有相同的 m +1-前缀，且第 m + 1 步的选择均为第 k 种区域( k = 1，2，n) 。则在集合 Q 中，第 m + 1 步选择第 k 种区域的购买权重为:= f( i，m + 1)Wb( m +1)

13、kiK其中，f( i，m + 1) 是动线 i 在第 m + 1 步的购买值。定义 8 记 P 为顾客动线的集合。给定一个 Q P，x Q，所有的 x 有相同的 m-前缀，且在第 m + 1 步有 n 种不同的区 域可以选择。给定一个 KQ，yK，所有的 y 有相同的 m +挖掘偏好动线的算法21-前缀，且第 m + 1 步的选择均为第 k 种区域( k = 1，2，n) 。2 1 偏好性模型定位系统包括 WIFI 标签和无线 AP: 购物车上带有 WIFI 标 签，每 5 秒钟发射出拥有唯一编码的信号。每一条动线既有购 物路径，用以 5 秒为间隔采集的( x，y) 坐标的列表来表示，还有 从

14、 POS 机中得到的购物记录。当购物车推到超市入口时，一条 动线开始，购物车推到收银台线并到达收银台另一边后，该动线 结束。定义 1 WIFI 标签每 5 秒钟向 EPE( Ekahau 定位引擎) 发 送一个信号，称为一次闪烁。每次闪烁包含的数据有: 发出这次 闪烁的标签的 MAC 地址、标签当前坐标( x，y) 、闪烁的时间以 及标签当前所在地图。定义 2 在 一 条 动 线 中，从 A 区 域 访 问 到 B 区 域，称 为 一步。要在众多的动线中找出一条或多条具有代表性的动线，需 要一个区域吸引力模型来规定如何才具有代表性。文献5在挖掘网页访问模式时提出了一个偏好性的概念来表示网页的吸

15、 引力。由于在网页访问和超市区域访问之间存在一定的差别， 而且网页访问不需要考虑购买行为对网页吸引力的影响，因此，本文为挖掘超市顾客的偏好动线提出了合适的偏好性模型。定义 3 动线的前 m 步称为动线的 m-前缀。定义 4 记 P 为顾客动线的集合。x P，x 在第 m 步的 离散化停留时间为:则在集合 Q 中，第 m + 1 步选择第 k 种区域的偏好性为:n( Wt( m +1) k + Wb( m +1) k ) / ( ( ( Wt( m +1) i + Wb( m +1) i ) ) / n)i = 1其中，Wt( m + 1) i 是第 m + 1 步选择第 i 种区域的停留时间权

16、重，Wb( m + 1) i 是第 m + 1 步选择第 i 种区域的购买权重。由上面的定义可以得知，偏好性模型既考虑区域访问次数 和区域停留时间，又考虑区域购买率。它可以防止只挖掘访问比较频繁的区域。停留时间权重在考虑区域通过次数的同时，增加了区域停留时间对偏好性的影响。购买权重则是增加了区域购买率对偏好性的影响。通过停留时间权重和购买权重，偏 好性能够更加准确地反映出区域对顾客的吸引力。偏好性的值在( 0，n) 之间，n 是可选择区域的个数。当某个 区域的偏好性超过 1 时，说明在当前这步顾客比较倾向于选择该区域。偏好性的值越高，倾向性越强。如果偏好性的阈值设 置得太高，则很多典型的动线可

17、能挖掘不到。反之，如果阈值设置过低，则会有很多不够典型的动线也被认为是偏好动线。因 此，设置一个合理的偏好性阈值是挖掘偏好动线的关键。一般 情况下，将偏好性的阈值设为 1。原始数据预处理所有的原始数据都来自于定位标签和 POS 机。在使用挖掘 算法对数据进行挖掘之前，需要对原始数据进行一些预处理工 作: 1) 对数据进行清理。比如由于顾客在购物途中放弃使用购物 车而导致的动线数据不完整等等。2) 为了减少数据的复杂性，分 析顾客动线的共同特征，需要对超市进行离散化，将超市划分为 多个非重叠的区域，然后对动线进行离散化，将每条动线上每次 闪烁的( x，y) 坐标映射到对应的区域，并根据闪烁次数算

18、出该动 线在该区域内的停留时间。3) 根据预设好的最大通过时间，最大2 2?0txm= 0?1= ?2?30 txm Tmax_visitTmax_visit txm Tmax_shortly_stayTmax_shortly_stay txm Tmax_normal_stayTxm?4Tmax_normal_stay txm孙莉等: 基于 WIFI 实时定位技术的偏好动线挖掘第 5 期205短暂停留时间和最大普通停留时间将停留时间离散化。4) 结合POS 小票数据得出每条动线购买的商品分布在哪些区域。这样，每一条动线可以用 第 0 步区域名: 离散化停留时间( 是否购买) ，第 1 步区域名

19、: 离散化停留时间( 是否购买) ， 第 n 步区域名: 离散化停留时间( 是否购买) 来表示，其中，是 否购买的值是 0 或 1，0 表示未购买，1 表示购买。所有的动线 组成一个候选动线集合。2 3 挖掘偏好动线的算法将入口区域记为 A，出口区域记为 Z。因为数据的采集是 从购物车离开 A 开始，进入 Z 结束，所以候选动线集合中的每 一条动线的第一个区域均为 A，最后一个区域均为 Z。为了保 持数据结构的标准以及算法需要，本文将 A 和 Z 的离散化停留 时间均记为 1，是否购买均记为 0。算法从动线的第一步开始， 计算出候选动线集合中当前步的每一种选择的偏好性。如果某 种选择的偏好性大

20、于偏好性阈值，则对该种选择进行下一步挖 掘，如此循环往复，直到选择为 Z。如果选择 Z 的偏好性大于偏 好性阈值，则这种动线为偏好动线。算法 1 挖掘偏好动线的算法( SPP) 输入 候选动线集合 SCP，偏好性阈值 Pt 输出 偏好动线集合 SPP输的数据，同时将 POS 小票数据写入数据库并与相应的动线数据绑定。WIFI 实时定位系统的工作原理如图 1 所示。图 1 WIFI 实时定位系统工作原理移动设备附近无线信号强度( RSSI) 被记录下来，并通过客 户端程序发送 RSSI 到 Ekahau 定位引擎，定位引擎里有 RSSI 的 模型文件，其识别 RSSI 的值，并计算出地图中二维坐

21、标，然后发 送定位信息给应用程序或者写入数据库。在部署 WIFI 实时定位模型时需要注意以下两点:( 1)AP 的密度。为了保证合理的 AP 密度，AP 之间需要保持大约 15 米到 23 米的距离。( 2)AP 的频道。由于 WIFI 使用的是 2 4GHz 频带，各频道之间频率可能相互重叠，可能相互干扰。如图 2 所示，频道1、6、11 之间频率没有重叠，所以我们设置 AP 的频道时选择频 道 1、6、11，且应尽量避免相邻的 AP 频道相同。( 1)( 2) ( 3) ( 4) ( 5) ( 1) ( 2)PROC main( SCP，Pt)SPP init( )mining( SCP，

22、1，Pt，SPP)return SPP EndPPROC mining( SP，step，Pt，SPP)SA = findSelections( SP，step)/ / 返回动线集合 SP 在第 step 步的选择集合For each area in SAp = calculate( SP，step，area)/ / 返回动线集合 SP 在第 step 步选择 area 的偏好性If p = PtIf area equals( Z)dp = getDistinctPath( SP，step，area)/ / 返回动线集合 SP 中第 step 步是 area 的一条动线SPP add( dp)

23、ElseST = getPathSet( SP，step，area)/ / 返回动线集合 SP 中第 step 步是 area 的动线集合step + +mining( ST，step，Pt，SPP)step- EndIfEndIfEndForEndP( 3)( 4)( 5)( 6) ( 7)图 2 各频道使用的频率范围3 2实验结果实验使用的地图是经过现场调研后得出的大卖场的地图，如图 3 所示，共分为 83 个区域。其中，区域 A 为入口，区域 Z 为收银台。由于在真实环境中应用定位系统需要一些花费，因此 本文使用的动线数据是请一些同学根据超市地图模拟自己平常 购物的行为所得到的。( 8)

24、( 9)( 10)( 11)( 12) ( 13) ( 14) ( 15) ( 16) ( 17)3实验设计及结果分析WIFI 实时定位系统为了可以记录顾客的动线，我们将 WIFI 标签固定在购物车 上。当购物车离开入口区域时，服务器将该标签传输过来的数 据写入数据库中，当购物车进入出口区域或者超过设定的最长 购物时间( 如 2 小时) 时，服务器停止向数据库中写入该标签传3 1图 3 超市货架布局及区域划分从图 4 中使用加粗标注的路径可以看到，一旦顾客进入一个通道，一般规律是回溯，即顾客进入通道后，更可能是原路返 回，而不是穿过通道，从另一个方向走出。这个结论符合文献1，2的研究发现。而通

25、过图 5 我们可以看到，使用 CAM 算法 得到的结果无法真实地反映出动线的回溯规律。实验总共模拟了 281 条动线数据。最终得到了 8 条偏好动线，实验结果如图 4 所示。另外我们使用文献4提出的 CAM 算法对实验数据进行挖掘，得到了 9 条偏好动线，结果如图 5 所示。结语4随着市场营销专家对通过分析顾客的购物行为来设计超市布局以及指定销售策略越来越重视，准确的顾客行为数据也越 来越被需要。本文提出一种新的表示区域吸引力的偏好性模 型，它不仅考虑了区域访问次数对区域吸引力的影响，还考虑了 区域停留时间和区域购买率对区域吸引力的影响，另外还很好 地解决了动线回溯的问题。根据这个模型，本文提

26、出一种新的 挖掘偏好动线的算法。通过这个算法，可以准确地得到顾客的 偏好动线。实验结果表明该方法是可行的。根据 SPP 算法挖掘 得到的偏好动线，专家可以更加轻松地进行更深入的顾客行为 规律分析并做出相应的决策，而不需要直接对大量杂乱无章的 原始数据进行分析。在未来的工作中，我们将致力于研究更高 效、更准确的挖掘偏好动线的算法，也将为偏好性增加更多的因 素使其能够更加准确地反映区域的吸引力。参 考 文 献1 Larson J S，Bradlow E T，Fader P S An exploratory look at supermar-ket shopping pathsJ Internati

27、onal Journal of Research in Market- ing，2005，22( 4) : 395-4142 Hui S K，Bradlow E T，Fader P S An integrated model of grocery store shopping path and purchase behaviorOL Working paper，University of Pennsylvania，Philadelphia http: / / ssrn com / abstract = 9609603 Yada K String analysis technique for shopping path in a supermarketJ Journal of Intelligent Information Systems，2011，36 ( 3 ) :385-4024 Liao I E，Lin W C RFID Eurasia，2007 1st Annual: Shopping path a- nalysis and transaction mining based on RFID technologyC/ /