多支持度的正负序列模式在客户购买行为分析中的应用

摘要

本发明涉及一种多支持度的正负序列模式在客户购买行为分析中的应用。本发明中提出一个名为E-msNSP的高效算法来挖掘基于多支持度的负序列模式，所述算法的主要思想是首先通过改进MS-GSP算法挖掘得到基于多支持度的正序列模式，然后用和e-NSP相同的方法通过公式来计算负序列侯选模式的支持度，无需再次扫描数据库。所述E-msNSP是第一个没有约束限制的基于多支持度的负序列模式挖掘算法。本发明筛选出某一段时间内，每一类产品中用户购买量比较大的商品，这样客户在购买产品时，利用本发明可以向他推荐一些其它客户购买频率比较大的类似相关产品，从而增加客户的交易机会，将网站浏览者转变为购买者，提高交叉销售能力，提高客户的忠诚度，以及提高网站的经济效益。

主权项

一种多支持度的正负序列模式在客户购买行为分析中的应用，其特征在于，包括步骤如下：(1)定义基于多支持度的负序列的最小支持度MIS(i)表示项i的最小项支持度，i是正项或负项；正元素，即已购买的商品，它的最小支持度是元素中项i的最小支持度值，对于负元素，即未购买的商品，则用相关的正元素的信息来计算它的最小支持度：对于负元素(ab)，其中a，b代表某种商品，该负元素的最小支持度是：基于多支持度的负序列S的最小支持度是序列中元素的最小支持度值，其中S中元素集包含：e₁,e₂...e_r，其中S的最小支持度minsup(S)是：minsup(S)＝min[MIS(e₁),MIS(e₂),...,MIS(e_r)]；对于一个购买序列S和它的最小支持度minsup(S)，如果S只包含正元素，s(S)≥minsup(S)，那么S被称为正序列模式；如果S包含负元素，s(S)≥minsup(S)，那么S被称为负序列模式；(2)利用E‑msNSP算法的步骤如下：首先，用基于多最小支持度的MS‑GSP算法来挖掘得到所有的正序列模式，即在某一段时间内，客户购买量大的商品；然后，基于所述正序列模式生成相应的负侯选序列；其次，利用相关的正序列模式的支持度来计算所述负侯选序列的支持度；再从所述负侯选序列里筛选出符合最小支持度要求的负序列模式，再用适当的筛选方法将能用于决策的序列模式筛选出来，利用这些筛选后的序列模式对客户的购买行为进行分析；(3)E‑msNSP负侯选序列的生成对于大小为k的正序列模式，其负侯选序列是通过改变正序列模式中任意m个不相邻元素为负元素得到的：m＝1,2,…,其中为大于k/2的最小整数；(4)计算负侯选序列的支持度定义一个负侯选序列MPS(ns)：负序列ns的最大正子序列，即包含负序列中所有的正元素；1‑negMS_ns：负序列ns的子序列，并且该子序列是由MPS(ns)以及一个负元素组成；1‑negMSS_ns：包含负序列ns的所有1‑negMS_ns子序列的集合；p(1‑negMS):序列1‑negMS中的正元素不变，将负元素转换为相应的正元素；如：大小为m并且含有n个负元素的序列ns，对于(只含有一个负元素的序列)∈1‑negMSS_ns(含有一个负元素的序列的集合)(1≤i≤n),在序列数据库D中ns的支持度sup(ns)是：$\begin{array}{c}\sup \left(\mathrm{ns}\right)=\left|\right\{\mathrm{MPS}\left(\mathrm{ns}\right)\left\}\right|-\left|{\cup }_{i=1}^n\right\{p(1-\mathrm{neg}{\mathrm{MS}}_i)\left\}\right|\\ =\sup \left(\mathrm{MPS}\left(\mathrm{ns}\right)\right)-\left|{\cup }_{i=-1}^n\right\{p(1-\mathrm{neg}{\mathrm{MS}}_i)\left\}\right|\end{array}---\left(i\right)$如果ns只包含一个负元素，那么序列ns的支持度是：sup(ns)＝sup(MPS(ns))‑sup(p(ns))  (ii)特别地，对于负序列(5)算法伪代码设计一个数据结构来存储e‑msNSP相关数据，所述数据结构存储正侯选序列以及它的支持度和{sid}，包含相应的正侯选序列的sid集合；所述e‑msNSP算法是基于正序列模式来挖掘负序列模式，算法E‑msNSP包括步骤如下：其中，输入：D：客户购买序列数据库；MIS(i)：每款产品的最小项支持度；输出：NSP：用于分析客户购买行为的序列模式的集合；所述步骤(1)是用基于多最小支持度的MS‑GSP算法从序列数据库中挖掘出所有的正序列模式；所有的正侯选序列以及它的支持度和sid的集合都被存储到哈希表PSCHash，其中，所述步骤(2)是负侯选序列的哈希码作为关键码；所述步骤(4)是对于每一个正序列模式，通过刚才所说的“负侯选序列的生成”方法来生成负侯选序列NSC；步骤(5)至步骤(20)，通过公式(i)‑(iii)计算出NSC中的每一个nsc的支持度；步骤(21)至步骤(23)然后判断出哪些是负序列模式NSP；步骤(6)至步骤(10)，通过公式(ii)和公式(iii)计算出只含有一个负元素的nsc的支持度，对于包含多于一个负元素的nsc的支持度，通过公式(i)计算出如步骤(9)至步骤(11)；对于后者，最关键的一步就是如何计算$\left|{\cup }_{i=1}^n\right\{p(1-\mathrm{neg}{\mathrm{MS}}_i)\left\}\right|,$将包含p(1‑negMS_i)的sid集合存储到{p(1‑negMS_i)}集合中，然后计算{p(1‑negMS_i)}的并集，再计算出集合中含有的sid的个数；步骤(21)行计算出nsc的最小支持度，它是序列中所有元素的MIS值中最小的一个；如果nsc.support>＝minsup(nsc)那么nsc被加入到NSP中，如步骤(22)至步骤(23)；返回结果，如步骤(26)，再用适当的筛选方法将能用于决策的序列模式筛选出来，利用这些筛选后的序列模式来分析客户的购买行为。