重复负序列模式在客户购买行为分析中的应用

1.一种重复负序列模式在客户购买行为分析中的使用方法，包括步骤如下：
(1)定义一个负序列在一个数据序列中出现的次数
MPS(ns)是指一个由客户购买的商品组成的负序列ns的最大正子序列，其由ns中包含的所有正元素按照原顺序组成；
一个负序列在一个数据序列中出现的次数由它的左终止位置决定；令ds＝是一个数据序列，对一个负序列ns，如果 并且 1则称p为左终止位置，定义为LAE(ns,ds)＝p,其中p≥1因为已经满足 如果
则LAE(ns,ds)＝1；
计算ns在ds中出现的次数t，并将该计算t的方法定义为t＝RptTimes(ns,ds)：
首先使用LAE(ns,ds)获得ns在ds中的左终止位置p，如果p>0，则t＝t+1，之后令ds＝，重复以上步骤直到
负序列ns：
RptTimes(ns,ds)＝RptTimes(MPS(ns),ds),如果
给出s1＝， ds1＝，ds2＝，则LAE(s1,ds1)＝4，LAE(s1,ds2)＝2，RptTimes(s1,ds1)＝1，RptTimes(s1,ds2)＝3；LAE(s2,ds1)＝2，LAE(s2,ds2)不存在因为
(2)负序列的重复支持度计算
负序列ns的重复支持度是负序列在所有数据序列中重复出现的次数，定义为rps_count(ns)，那么ns在序列数据库D中的重复支持度为：
(3)利用e-RNSP算法的步骤如下：
首先，使用重复正序列挖掘算法RptGSP挖掘得到所有的重复正序列模式，即在某一段时间内，客户重复购买量大的商品；
然后，基于所述重复正序列模式生成相应的重复负候选序列，该负候选序列用于判断在某一段时间内，哪些商品客户购买的多，哪些商品客户没有购买；
其次，利用相关的重复正序列模式的支持度来计算负候选序列的重复支持度；
再从所述负候选序列里筛选出符合最小支持度要求的重复负序列模式，再用现有适当的筛选方法将能用于决策的序列模式筛选出来，利用这些筛选后的重复负序列模式对客户的购买行为进行分析；商家根据分析结果针对客户提供个性化服务，根据客户购买习惯安排商品的推荐顺序和频率；
(4)e-RNSP负候选序列的生成
改变正序列模式中任意不相邻元素为负元素；
(5)计算负候选序列的支持度
定义一个负候选序列：
1-negMSns：负序列ns的子序列，并且该子序列是由MPS(ns)以及一个负元素组成；
1-negMSSns：包含负序列ns的所有1-negMSns子序列的集合；
p(1-negMS):序列1-negMS中的正元素不变，将负元素转换为相应的正元素；
一个大小为m并且含有n个负元素的序列ns，对于 在序列
数据库D中ns的支持度sup(ns)由以下几个公式计算得出：
使用公式(iii)来获得所有包含ns的数据序列的sid，其中{MPS(ns)}是所有包含MPS(ns)的数据序列的sid， 是所有{p(1-negMSi)}组成的sid集合的并集；
所述ns的传统支持度由|{ns}|计算出，|{ns}|表示{ns}集合中sid的个数；所述ns的重复支持度为：
其中dsi是指包含ns的第i个数据序列，通过公式(i)计算RptTimes(ns,dsi)，如果ns的大小是1，那么负序列ns的支持度是：
sup(ns)＝|D|-sup(p(ns))  (v)
(6)算法伪代码
设计一个数据结构来存储e-RNSP相关数据，所述数据结构存储正候选序列和包含它的数据序列的{sid}以及重复次数；
所述e-RNSP算法是基于正序列模式来挖掘重复负序列模式，算法e-RNSP包括步骤如下：
其中，输入：D：客户购买序列数据库；min_sup:最小支持度；
输出：RNSP：用于分析客户购买行为的重复负序列模式的集合；
所述步骤(1-1)是用重复正序列模式挖掘算法RptGSP从序列数据库中挖掘出所有的重复正序列模式；步骤(1-2)和步骤(1-3)将所有的重复正候选序列以及它的重复支持度和sid的集合都被存储到哈希表RNSPHash；
所述步骤(1-6)是对于每一个重复正序列模式，通过步骤(1-4)中表述的负候选序列的生成方法来生成负候选序列RNSC；
步骤(1-7)至步骤(1-24)，通过公式(i)-(v)计算出RNSC中的每一个rnsc的支持度；步骤(1-25)至步骤(1-27)然后判断出哪些是重复负序列模式RNSP；
其中步骤(1-8)至步骤(1-10)，通过公式(v)计算出只含有一个负元素的rnsc的支持度，对于包含多于一个负元素的rnsc的支持度，通过公式(i)到公式(iv)计算出，如步骤(1-
12)至步骤(1-24)；
如果rnsc.support>＝min_sup那么rnsc被加入到RNSP中，如步骤(1-25)至步骤(1-
27)；
返回结果，如步骤(1-29)，再用适当的筛选方法将能用于决策的序列模式筛选出来，利用这些筛选后的重复负序列模式来分析客户的购买行为。

重复负序列模式在客户购买行为分析中的应用\n技术领域\n[0001] 本发明涉及重复负序列模式在客户购买行为分析中的应用，属于重复负序列模式的应用技术领域。\n背景技术\n[0002] 随着互联网高潮来临，使得网络购物的用户规模不断上升。对消费者来说，网络购物已经成为一种全新的购物体验，并逐步成为生活中不可或缺的一部分。互联网提供了一个新的交互的购物渠道，消费者获得巨大的优势：丰富的商品信息，克服地理与时间的障碍，获得有价格竞争力的商品，产品的个性化、定制化，更多的商品选择，更大的购物便利等。近年来，网络购物呈爆发式增长，每年都以几何数级增长，与此同时很多大型的电子商务网站，如Amazon、阿里巴巴旗下的淘宝和天猫商城、京东等都积累了大量的客户交易数据。如何充分利用这些数据对客户购买行为进行有效的分析、组织利用,如何了解到客户尽可能多的爱好和价值取向,以优化网站设计,为客户提供个性化服务,成为电子商务发展迫切要解决的问题。\n[0003] 与传统的经营方式相比，网络购物的产品信息量大，数量、种类丰富，选择范围广。\n在传统购物环境下，消费者获取商品信息的来源主要靠生活积累,搜集过程较长,得到的信息比较片面。在网络购物环境下,消费者就可以集中时间搜集、查找大量的有关商品的信息。网上商品种类丰富，有些商品消费者想要购买而传统商铺不容易找到，就可以通过网络商店方便的查询购买，补充了传统商店某些产品的短缺。但是目前的电子商务商家通常不能直观的去了解客户，获取的相关的数据有限(比如用户的注册信息，购买记录等)。通过对大量的客户购买记录进行分析和挖掘，发现客户的频繁访问序列模式，针对不同的客户属性和网上购物步骤，采用不同的商品推荐形式，适时的向客户推荐恰当的商品，并优化电子商务网站商品的摆放位置，可以有效的增加客户的交易机会，将网站浏览者转变为购买者，提高交叉销售能力，提高客户的忠诚度，以及提高购物网站的服务质量和经济效益。\n[0004] 序列模式分析所要解决的问题是客户在完成一次交易之后，在以后的特定时间内，还会购买什么商品，是发现交易之间关系规律的过程，使得售货方能够根据当前的商品买卖情况来预测以后的商品买卖情况，从而能够更好的安排商品的摆放。它的主要目的是研究商品购买的先后关系，找出其中的规律，即不仅需要知道商品是否被购买，而且需要确定该商品与其它商品购买的先后顺序，例如，在线购买DVD的一个典型的顺序是购买“星球大战”，之后很有可能继续购买“帝国反击战”，再是购买“杰达武士归来”。因此序列模式能够发现数据库中某一段时间内的一个频繁序列，即在这个时间段内哪些商品会被客户购买的比较多，多或少的标准是由最小支持度来决定的。每个序列是按照交易的时间排列的一组集合，可以设置最小支持度来挖掘满足不同频繁程度的序列。但在应用序列模式分析客户购买行为，解决个性化商品推荐问题时，他们仅考虑了已发生的事件，也称为正序列模式(Positive Sequent ial Pattern，PSP)挖掘。\n[0005] 与传统的正序列模式(Positive Sequential Pattern，PSP)不同，负序列模式(Negative Sequential Pattern，NSP)挖掘不仅考虑了已经发生的事件，还关注于未发生事件，它能够更深入地分析和理解数据中的潜在含义，从而挖掘出容易被人们忽略但是非常有价值的信息。例如：a代表面包，b代表咖啡，c代表茶，d代表糖， 表示一个客户购买序列模式，该模式说明在某一段时间内，该客户在购买了商品a、b后，在没有购买商品c的情况下，购买了商品d。如今负序列模式的价值越来越被人们认可，在深入理解和处理许多商业应用方面，如对客户购买行为分析方面，它更有一种不可替代的作用。\n[0006] 目前，关于负序列模式挖掘算法的研究成果较少，如，NSPM，PNSP，Neg-GSP，e-NSP等等。但是这些算法在计算负序列支持度的时候，仅仅考虑了它是否在一条数据序列中出现，而忽略了其在数据序列中出现的次数。在现实生活中，由一个批发型顾客所构成的一条数据序列，其中的某些商品应该是重复多次出现的，那么只考虑这些商品组成序列是否出现，而不考虑其出现的次数是很不公平的。因此，有人提出了一些基于重复支持度的序列模式挖掘算法，如GSgrow，CloGSgrow和RptGSP算法。它们在计算由商品所组成序列的支持度的时候均考虑了其在数据序列重复出现的情况，这使得此商品序列比传统方法可能具有更高的支持度，更有可能满足所设定的最小支持度而被挖掘出来。但是这些方法中只考虑了重复正序列模式挖掘，我们目前没有找到任何有关于重复负模式挖掘方法的研究。\n[0007] 电子商务平台中的网站用户购买订单数据为挖掘的数据源。以5个客户在2个月内的交易为例，如表1是由客户ID和交易时间为关键字所排序的事务数据库。一个事务数据库，一个事务代表一笔交易，一个单项代表交易的商品，单项属性中的字母记录的是商品ID。\n[0008] 表1事务数据库\n[0009]\n[0010] 进行数据预处理，将表1的事务数据库整理成表2的序列数据库。\n[0011] 表2序列数据库\n[0012]\n客户ID 客户购买序列\n1 〈{c}{i}〉\n2 〈{a,b}{c}{a,d,f,g}〉\n3 〈{c,e,g,h}〉\n4 〈{c}{c,d,g,h}{i}〉\n5 〈{i}〉\n[0013] 一个客户在某个时间段内所有的交易记录构成一个有序的序列，序列用<>表示。\n在序列中，项/项集是有顺序的，每个项都代表交易的一种商品，而元素则是指该客户在某一个具体的时间点一次性购买的所有商品，用{}或()表示，该客户可能在不同的时间段购买同一件产品，即一个项可能在一个序列的不同元素中发生。如表2中ID为2的客户购买序列为〈{a,b}{c}{a,d,f,g}〉，该客户分别在第一次和第三次购物时购买了商品a，其中{a,b}，{c}，{a,d,f,g}这三个项目集可称为序列的元素，a,b,c,d,f,g则称为项，如果一个元素中只有一个项，则括号可以省略，如该序列中的元素{c}可直接写c。\n发明内容\n[0014] 发明概述\n[0015] 针对现有技术的不足，本发明提供一种重复负序列模式在客户购买行为分析中的应用。本发明中提出一个名为e-RNSP的高效算法来挖掘重复负序列模式，所述算法的主要思想是首先通过RptGSP算法挖掘得到重复正序列模式，并且将挖掘出来的重复正序列模式以及包含它们的数据序列中的重复次数对应保存下来，然后用和e-NSP相同的方法生成负序列候选模式，最后通过公式来计算负序列侯选模式的重复支持度，而无需多次扫描数据库。所述e-RNSP是第一个重复负序列模式挖掘算法，通过该算法挖掘得到的重复负序列模式可以更全面的分析客户购买行为，使得售货方能够根据当前的商品销售情况来预测以后的商品销售，更能发现某些对特定商品重复购买的人群，合理安排商品摆放，提高商品销售量。\n[0016] 发明详述\n[0017] 本发明的技术方案如下：\n[0018] 一种重复负序列模式在客户购买行为分析中的应用，包括步骤如下：\n[0019] (1)定义一个负序列在一个数据序列中出现的次数\n[0020] MPS(ns)是指一个由客户购买的商品组成的负序列ns的最大正子序列，其由ns中包含的所有正元素按照原顺序组成；例如：一个负序列 代表没有购买的\n商品，而c d代表购买了的商品。它的最大正子序列为MPS(ns)＝，特别的，一个正序列的最大正子序列是它本身；\n[0021] 一个负序列在一个数据序列中出现的次数由它的左终止位置决定；令ds＝是一个数据序列，对一个负序列ns，如果 并且 使得\n则称m为左终止位置，定义为LAE(ns,ds)＝m,其\n中m≥1因为已经满足 如果 则LAE(ns,ds)＝1；\n[0022] 计算ns在ds中出现的次数t，并将该计算t的方法定义为t＝RptTimes(ns,ds)：\n[0023] 首先使用LAE(ns,ds)获得ns在ds中的左终止位置m，如果m>0，则t＝t+1，之后令ds＝，重复以上步骤直到\n[0024] 通过以上对于负重复的定义，我们可以发现对于一个负序列ns：\n[0025] RptTimes(ns,ds)＝RptTimes(MPS(ns),ds),如果\n[0026] 例如，给出s1＝， ds1＝，ds2＝，则LAE(s1,ds1)＝4，LAE(s1,ds2)＝2，RptTimes(s1,ds1)＝1，RptTimes(s1,ds2)＝3；LAE(s2,ds1)＝2，LAE(s2,ds2)不存在因为 RptTimes(s2,ds1)＝RptTimes(MPS(s2),ds1)＝2；\n[0027] (2)负序列的重复支持度计算\n[0028] 负序列ns的重复支持度是负序列在所有数据序列中重复出现的次数，定义为rps_count(ns)，那么ns在数据库D中的重复支持度为：\n[0029]\n[0030] (3)利用e-RNSP算法的步骤如下：\n[0031] 首先，使用重复正序列挖掘算法RptGSP挖掘得到所有的重复正序列模式，即在某一段时间内，客户重复购买量大的商品；\n[0032] 然后，基于所述重复正序列模式生成相应的重复负候选序列(repeated negative sequential candidates,RNSC)，该负候选序列用于判断在某一段时间内，哪些商品客户购买的多，哪些商品客户没有购买；\n[0033] 其次，利用相关的重复正序列模式的支持度来计算负侯选序列的重复支持度；\n[0034] 再从所述负侯选序列里筛选出符合最小支持度要求的重复负序列模式，再用现有适当的筛选方法将能用于决策的序列模式筛选出来，利用这些筛选后的重复负序列模式对客户的购买行为进行分析；商家根据分析结果针对客户提供个性化服务，根据客户购买习惯安排商品的推荐顺序和频率；\n[0035] (4)e-RNSP负侯选序列的生成\n[0036] 为了基于正序列模式生成无冗余的负侯选序列，我们用一种高效的方法来生成负侯选序列，其基本思想是改变正序列模式中任意不相邻元素为负元素；\n[0037] 对于大小为k的正序列模式，其负侯选序列是通过改变正序列模式中任意m个不相邻元素为负元素得到的： 其中 为大于k/2的最小整数；\n[0038] 例：基于<(ab)cd>的负侯选序列，其中a、b、c、d是指某种产品，包括：\n[0039] (5)计算负侯选序列的支持度\n[0040] 定义一个负侯选序列\n[0041] 1-negMSns：负序列ns的子序列，并且该子序列是由MPS(ns)以及一个负元素组成；\n[0042] 1-negMSSns：包含负序列ns的所有1-negMSns子序列的集合；\n[0043] p(1-negMS):序列1-negMS中的正元素不变，将负元素转换为相应的正元素；如：\n[0044] 一个大小为m并且含有n个负元素的序列ns，对于 (只含有一个负元素的序列)∈1-negMSSns(含有一个负元素的序列的集合)(1≤i≤n),在序列数据库D中ns的支持度sup(ns)由以下几个公式计算得出：\n[0045]\n[0046] 使用公式(iii)来获得所有包含ns的数据序列的sid，其中{MPS(ns)}是所有包含MPS(ns)的数据序列的sid， 是所有{p(1-negMSi)}组成的sid集合的并\n集；\n[0047] 所述ns的传统支持度由|{ns}|计算出，|{ns}|表示{ns}集合中sid的个数；但是我们为了计算ns的重复支持度，就必须要知道ns在每一个包含它的数据序列中重复出现的次数；所述ns的重复支持度为：\n[0048]\n[0049] 其中dsi是指包含ns的第i个数据序列，通过公式(i)计算RptTimes(ns,dsi)，而不需要重复扫描数据库；\n[0050] 如果ns的大小是1，意味着它只包含一个负元素，那么负序列ns的支持度是：\n[0051] sup(ns)＝|D|-sup(p(ns))  (v)\n[0052] 假设，包含序列的sid(包含序列的客户ID)集合为{10,20,30,40，50}，分别在这5个数据序列中重复的次数为{2,2,1,3,4}，支持序列的集合是{10,20},支持序列的sid的集合是{20,30},则\n[0053]\n[0054]\n[0055] (6)算法伪代码\n[0056] 为了高效的计算重复支持度，设计一个数据结构来存储e-RNSP相关数据，所述数据结构存储正侯选序列(Positive Sequential Candidates,PSC)和包含它的数据序列的{sid}以及重复次数；\n[0057] 所述e-RNSP算法是基于正序列模式来挖掘重复负序列模式，算法e-RNSP包括步骤如下：\n[0058] 其中，输入：D：客户购买序列数据库；min_sup:最小支持度；\n[0059] 输出：RNSP：用于分析客户购买行为的重复负序列模式的集合；\n[0060] (1)RPSP＝RptGSP(D)；\n[0061] (2)each RPSP:Hashtable sidHash＝CreateSidHashTable(sid,rt)；\n[0062] (3)Hashtable RPSPHash＝CreateRPSPHashTable(RPSP,sidHash)；\n[0063] (4)For(each rpsp in RPSP){\n[0064] (5)   int rsup＝0；\n[0065] (6)   RNSC＝e-RNSP_Candidate_Generation(rpsp)；\n[0066] (7)   For(each rnsc in RNSC){\n[0067] (8)      if(nsc.size＝＝1&&nsc.neg_size＝＝1){\n[0068] (9)       nsc.support＝|D|-p(nsc).support；\n[0069] (10)      }\n[0070] (11)    1-negMSSnsc＝{1-negMSi|1<＝i<＝nsc.neg_size}；\n[0071] (12)    For(i＝2；i<＝nsc.neg_size；i++){\n[0072] (13)       For(each sid in p(1-negMSi).sidHash.keySet){\n[0073] (14)      If(p(1-negMS1).sidHash.containKey(sid)＝＝false)[0074] (15)      p(1-negMS1).sidHash.put(sid,p(1-negMSi).sidHash.get(sid))；\n[0075] (16)       }\n[0076] (17)      }\n[0077] (18)      For(each sid in p(1-negMS1).sidHash.keySet){\n[0078] (19)         If(MPS(rnsc).sidHash.containKey(sid))\n[0079] (20)         MPS(rnsc).sidHash.remove(sid)；\n[0080] (21)      }\n[0081] (22)      For(int i:MPS(rnsc).value( )){\n[0082] (23)         rsup＝rsup+i；\n[0083] (24)      }\n[0084] (25)      If(rsup>＝min_sup)\n[0085] (26)        RNSP.add(rnsc)；\n[0086] (27)  }\n[0087] (28) }\n[0088] (29) return RNSP；\n[0089] 所述步骤(1)是用重复正序列模式挖掘算法RptGSP从序列数据库中挖掘出所有的重复正序列模式；步骤(2)和步骤(3)将所有的重复正侯选序列以及它的重复支持度和sid的集合都被存储到哈希表RNSPHash；\n[0090] 所述步骤(6)是对于每一个重复正序列模式，通过刚才所说的“负侯选序列的生成”方法来生成负侯选序列RNSC；\n[0091] 步骤(7)至步骤(24)，通过公式(i)-(v)计算出RNSC中的每一个rnsc的支持度；步骤(25)至步骤(27)然后判断出哪些是重复负序列模式RNSP；\n[0092] 其中步骤(8)至步骤(10)，通过公式(v)计算出只含有一个负元素的rnsc的支持度，对于包含多于一个负元素的rnsc的支持度，通过公式(i)到公式(iv)计算出，如步骤(12)至步骤(24)；\n[0093] 如果rnsc.support>＝min_sup那么rnsc被加入到RNSP中，如步骤(25)至步骤(27)；\n[0094] 返回结果，如步骤(29)，再用适当的筛选方法将能用于决策的序列模式筛选出来，利用这些筛选后的重复负序列模式来分析客户的购买行为。\n[0095] 本发明的优势\n[0096] 目前用于负序列模式挖掘的算法较少，但是这些算法在计算负序列支持度的时候，仅仅考虑了它是否在一条数据序列中出现，而忽略了其在数据序列中出现的次数。在现实生活中，由一个批发型顾客所构成的一条数据序列，其中的某些商品应该是重复多次出现的，那么只考虑这些商品组成序列是否出现，而不考虑其出现的次数是很不公平的。而现有的挖掘重复序列的方法都是针对重复正序列模式挖掘，本发明提出了一种高效挖掘重复负序列模式的算法，这使得由商品组成的负候选序列比传统方法可能具有更高的支持度，更有可能满足所设定的最小支持度而被挖掘出来。本发明应用在进行客户购买行为分析的过程中，可以充分考虑到序列重复出现的模式，从而发现用户购买量大或者被特定用户重复购买的商品，这样客户在购买产品时，利用本发明可以向他推荐一些其它客户购买频率比较大的类似相关产品，从而增加客户的交易机会，将网站浏览者转变为购买者，提高交叉销售能力，提高客户的忠诚度，以及提高网站的经济效益。\n具体实施方式\n[0097] 下面结合实施例对本发明做详细的说明，但不限于此。\n[0098] 实施例、\n[0099] 一种重复负序列模式在客户购买行为分析中的应用，包括步骤如下：\n[0100] (1)定义一个负序列在一个数据序列中出现的次数\n[0101] MPS(ns)是指一个由客户购买的商品组成的负序列ns的最大正子序列，其由ns中包含的所有正元素按照原顺序组成；例如：一个负序列 代表没有购买的\n商品，而c d代表购买了的商品。它的最大正子序列为MPS(ns)＝，特别的，一个正序列的最大正子序列是它本身；\n[0102] 一个负序列在一个数据序列中出现的次数由它的左终止位置决定；令ds＝是一个数据序列，对一个负序列ns，如果 并且 使得\n则称m为左终止位置，定义为LAE(ns,ds)＝m,其\n中m≥1因为已经满足 如果 则LAE(ns,ds)＝1；\n[0103] 计算ns在ds中出现的次数t，并将该计算t的方法定义为t＝RptTimes(ns,ds)：\n[0104] 首先使用LAE(ns,ds)获得ns在ds中的左终止位置m，如果m>0，则t＝t+1，之后令ds＝，重复以上步骤直到\n[0105] 通过以上对于负重复的定义，我们可以发现对于一个负序列ns：\n[0106] RptTimes(ns,ds)＝RptTimes(MPS(ns),ds),如果\n[0107] 例如，给出s1＝， ds1＝，ds2＝，则LAE(s1,ds1)＝4，LAE(s1,ds2)＝2，RptTimes(s1,ds1)＝1，RptTimes(s1,ds2)＝3；LAE(s2,ds1)＝2，LAE(s2,ds2)不存在因为 RptTimes(s2,ds1)＝RptTimes(MPS(s2),ds1)＝2；\n[0108] (2)负序列的重复支持度计算\n[0109] 负序列ns的重复支持度是负序列在所有数据序列中重复出现的次数，定义为rps_count(ns)，那么ns在数据库D中的重复支持度为：\n[0110]\n[0111] (3)利用e-RNSP算法的步骤如下：\n[0112] 首先，使用重复正序列挖掘算法RptGSP挖掘得到所有的重复正序列模式，即在某一段时间内，客户重复购买量大的商品；\n[0113] 然后，基于所述重复正序列模式生成相应的重复负候选序列(repeated negative sequential candidates,RNSC)，该负候选序列用于判断在某一段时间内，哪些商品客户购买的多，哪些商品客户没有购买；\n[0114] 其次，利用相关的重复正序列模式的支持度来计算负侯选序列的重复支持度；\n[0115] 再从所述负侯选序列里筛选出符合最小支持度要求的重复负序列模式，再用现有适当的筛选方法将能用于决策的序列模式筛选出来，利用这些筛选后的重复负序列模式对客户的购买行为进行分析；商家根据分析结果针对客户提供个性化服务，根据客户购买习惯安排商品的推荐顺序和频率；\n[0116] (4)e-RNSP负侯选序列的生成\n[0117] 为了基于正序列模式生成无冗余的负侯选序列，我们用一种高效的方法来生成负侯选序列，其基本思想是改变正序列模式中任意不相邻元素为负元素；\n[0118] 对于大小为k的正序列模式，其负侯选序列是通过改变正序列模式中任意m个不相邻元素为负元素得到的： 其中 为大于k/2的最小整数；\n[0119] 例：基于<(ab)cd>的负侯选序列，其中a、b、c、d是指某种产品，包括：\n[0120] (5)计算负侯选序列的支持度\n[0121] 定义一个负侯选序列\n[0122] 1-negMSns：负序列ns的子序列，并且该子序列是由MPS(ns)以及一个负元素组成；\n[0123] 1-negMSSns：包含负序列ns的所有1-negMSns子序列的集合；\n[0124] p(1-negMS):序列1-negMS中的正元素不变，将负元素转换为相应的正元素；如：\n[0125] 一个大小为m并且含有n个负元素的序列ns，对于 (只含有一个负元素的序列)∈1-negMSSns(含有一个负元素的序列的集合)(1≤i≤n),在序列数据库D中ns的支持度sup(ns)由以下几个公式计算得出：\n[0126]\n[0127] 使用公式(iii)来获得所有包含ns的数据序列的sid，其中{MPS(ns)}是所有包含MPS(ns)的数据序列的sid， 是所有{p(1-negMSi)}组成的sid集合的并\n集；\n[0128] 所述ns的传统支持度由|{ns}|计算出，|{ns}|表示{ns}集合中sid的个数；但是我们为了计算ns的重复支持度，就必须要知道ns在每一个包含它的数据序列中重复出现的次数；所述ns的重复支持度为：\n[0129]\n[0130] 其中dsi是指包含ns的第i个数据序列，通过公式(i)计算RptTimes(ns,dsi)，而不需要重复扫描数据库；\n[0131] 如果ns的大小是1，意味着它只包含一个负元素，那么负序列ns的支持度是：\n[0132] sup(ns)＝|D|-sup(p(ns))  (v)\n[0133] 假设，包含序列的sid(包含序列的客户ID)集合为{10,20,30,40，50}，分别在这5个数据序列中重复的次数为{2,2,1,3,4}，支持序列的集合是{10,20},支持序列的sid的集合是{20,30},则\n[0134]\n[0135]\n[0136] (6)算法伪代码\n[0137] 为了高效的计算重复支持度，设计一个数据结构来存储e-RNSP相关数据，所述数据结构存储正侯选序列(Positive Sequential Candidates,PSC)和包含它的数据序列的{sid}以及重复次数；\n[0138] 所述e-RNSP算法是基于正序列模式来挖掘重复负序列模式，算法e-RNSP包括步骤如下：\n[0139] 其中，输入：D：客户购买序列数据库；min_sup:最小支持度；\n[0140] 输出：RNSP：用于分析客户购买行为的重复负序列模式的集合；\n[0141] (1)RPSP＝RptGSP(D)；\n[0142] (2)each RPSP:Hashtable sidHash＝CreateSidHashTable(sid,rt)；\n[0143] (3)Hashtable RPSPHash＝CreateRPSPHashTable(RPSP,sidHash)；\n[0144] (4)For(each rpsp in RPSP){\n[0145] (5)   int rsup＝0；\n[0146] (6)   RNSC＝e-RNSP_Candidate_Generation(rpsp)；\n[0147] (7)   For(each rnsc in RNSC){\n[0148] (8)      if(nsc.size＝＝1&&nsc.neg_size＝＝1){\n[0149] (9)       nsc.support＝|D|-p(nsc).support；\n[0150] (10)      }\n[0151] (11)    1-negMSSnsc＝{1-negMSi|1<＝i<＝nsc.neg_size}；\n[0152] (12)    For(i＝2；i<＝nsc.neg_size；i++){\n[0153] (13)       For(each sid in p(1-negMSi).sidHash.keySet){\n[0154] (14)      If(p(1-negMS1).sidHash.containKey(sid)＝＝false)[0155] (15)      p(1-negMS1).sidHash.put(sid,p(1-negMSi).sidHash.get(sid))；\n[0156] (16)       }\n[0157] (17)      }\n[0158] (18)      For(each sid in p(1-negMS1).sidHash.keySet){\n[0159] (19)         If(MPS(rnsc).sidHash.containKey(sid))\n[0160] (20)         MPS(rnsc).sidHash.remove(sid)；\n[0161] (21)      }\n[0162] (22)      For(int i:MPS(rnsc).value( )){\n[0163] (23)         rsup＝rsup+i；\n[0164] (24)      }\n[0165] (25)      If (rsup>＝min_sup)\n[0166] (26)        RNSP.add(rnsc)；\n[0167] (27)  }\n[0168] (28) }\n[0169] (29) return RNSP；\n[0170] 所述步骤(1)是用重复正序列模式挖掘算法RptGSP从序列数据库中挖掘出所有的重复正序列模式；步骤(2)和步骤(3)将所有的重复正侯选序列以及它的重复支持度和sid的集合都被存储到哈希表RNSPHash；\n[0171] 所述步骤(6)是对于每一个重复正序列模式，通过刚才所说的“负侯选序列的生成”方法来生成负侯选序列RNSC；\n[0172] 步骤(7)至步骤(24)，通过公式(i)-(v)计算出RNSC中的每一个rnsc的支持度；步骤(25)至步骤(27)然后判断出哪些是重复负序列模式RNSP；\n[0173] 其中步骤(8)至步骤(10)，通过公式(v)计算出只含有一个负元素的rnsc的支持度，对于包含多于一个负元素的rnsc的支持度，通过公式(i)到公式(iv)计算出，如步骤(12)至步骤(24)；\n[0174] 如果rnsc.support>＝min_sup那么rnsc被加入到RNSP中，如步骤(25)至步骤(27)；\n[0175] 返回结果，如步骤(29)，再用适当的筛选方法将能用于决策的序列模式筛选出来，利用这些筛选后的重复负序列模式来分析客户的购买行为。\n[0176] 其中所述客户购买行为分析，其中序列模式分析的侧重点在于分析数据间的前后或因果关系。就是在时间有序的事务集中,找到那些“一些项跟随另一些项”的内部事务模式。例如：9个月以前购买奔腾Pc的客户很可能在一个月内订购新的CPU芯片。再例如，购买了PC的客户，可能接着买内存芯片，再买CD—ROM。\n[0177] 通过从客户购买记录中挖掘出很多客户在一段时间内都会购买的商品，来便于电子商务的组织者预测客户的行为对客户提供个性化服务，发现什么商品会在另外一些商品购买后购买,从而可以向客户提出推荐，把这些商品可以放到最显眼的位置。例如，当客户在线购买一台个人电脑时，系统可能根据以前挖掘出来的序列模式建议他考虑同时购买其他的一些东西，比如“购买这种个人电脑的人在三个月之内很可能要再买某种特殊的打印机或CD-ROM”，可以送给用户一个短期优惠券，从而促进产品销售。而负序列模式中的负项，即客户不购买的商品，我们则不需要向客户推荐，例如，<智能手机，游戏机，内存卡>该序列模式，当客户购买智能手机时，系统会向客户推荐购买内存卡而不推荐游戏机，因为购买智能手机的人，很可能在三个月内再购买内存卡，而不购买游戏机。\n[0178] 通过对客户购买行为进行分析，发现交易之间的关系规律，不仅可以根据当前的商品买卖情况来预测以后的商品买卖情况，还可以更好的调整商品的推荐顺序和频率，从而提高商品销售量。