I-PrefixSpan 用于个性化路线推荐系统

该文章主要是对Generating touring path suggestions using time-interval sequential pattern mining(点击可查看)论文的算法讨论

背景介绍

我们通过算法的名字可以知道，这两个算法是在PrefixSpan算法上进行的改进，但是我更加倾向于说是两者都是用到了PrefixSpan算法中的中心思想。

个性化推荐是根据用户的兴趣和行为，向用户推荐用户感兴趣的信息。个性化推荐系统是建立在海量数据挖掘的基础上的一种智能平台向顾客提供个性化的信息服务和决策支持。

我们可以将用户的行走路线看做是一个序列，这样在海量的数据中我们就可以挖掘到比传统的路线推荐算法更加人性化的路线。(在旅游与参观游览路线推荐方面是最实用的。)

I-PrefixSpan算法为核心的推荐系统

背景介绍

一个包含时间间隔的序列模式会提供更加有价值的信息。例如在大型的超市中我们就可以在时间间隔序列模式的帮助下，零售商不仅了解顾客的习惯、兴趣和需求，而且了解他们购物的时间。因此，零售商可以在适当的时候将最好的适当目录邮寄给不同类型的客户，并且他可以决定订购哪种产品和多少产品，以及何时满足未来的需求。

我们的背景：博物馆内向游客推荐参观路线，游客需要输入的信息为Gender和Education以及总的游玩时间，我们已经获取了部分游客游玩的路线，将其作为数据库进行挖掘和推荐出合理的路线。下图为博物馆的展示图。

I-PrefixSpan算法就是在PrefixSpan算法的思想下，运用于时间间隔序列模式挖掘的。

系统体系的介绍

整个路线推荐系统分为两个部分，一部分为频繁时间序列模式的挖掘，另一部分是路线检索机制。
我们通过算法挖掘出频繁的（满足最小支持度的）时间序列模式，通过筛选得到了满足条件的候选路线，但是我们需要路径检索机制，检索出满足我们推荐要求的路线，从而向游客推荐。

挖掘预处理步骤

因为不同的游客对于博物馆中感兴趣的东西是不相同的，因此我们将游客根据不同的性别和受教育程度分为了四种情况，从而使得原始数据库分为了四种小的数据库。

我们通过子数据库III作为例子：

这里我们要解释一下VID表示的是用户的ID(每一个用户对应一个单独的id) Visting paths表示的是用户参观的路线。(Ei-表示为博物馆内第i个展台其中E0和E449分别表示博物馆的入口和出口，Ei后面的数字表示的是在这个展台参观的时间戳) Total visiting time表示该游客总共游玩的时间。

I-PrefixSpan算法详解

1、我们的第一步需要找到数据库中的频繁单项集，这一步的过程和PrefixSpan算法一样，是PrefixSpan算法的简化版，在这一步中我们不需要考虑展台后面的时间戳。

整个过程是遍历找到所有满足最小支持度的频繁单项集（即所有频繁的展台）

2、将原数据库中的非频繁单项集以及其后的时间戳去掉，生成新的数据库。

3、然后到第三步构造投影数据库，
4-1、再次挖掘频繁单项集，这里的频繁单项集的挖掘和PrefixSpan就有区别了，不在是简单的遍历计数。这里不仅项目（展台）要满足最小支持度，时间间隔也要满足这个要求。
我们的题目是时间序列模式的挖掘，这里我们需要知道我们还有一个很重要的因素-时间要考虑。
时间间隔：指的是两个展台之间我们所需要的时间。

在A展台的时间戳是x，在B展台的时间的时间戳为y，则A-B之间的时间间隔为y-x。y-x是一个具体的数值，我们再次需要对这个数值进行一下离散化。
例如：y-x = 3.4 和y-x = 4.3，是相差不大的因此我们可以将次归为 I1 = (0，5]，其中0表示为I1的下界，5表示为I1的上界。

为什么一定要离散化呢？我的理解是因为这样我们可以找到较多的满足最小支持度的序列，否则我们很难找到合适的路线。
4-2、因此我们可以建表去寻找满足条件的频繁项。

下面我们用一个例子来说明这个过程：min_sup = 2

Sid	Path	Total—time
1	A,1 B,7 C,15 D,20 E31	30
2	A,1 B,4 C,15 E,26	25
3	A,1 C,10 H,16 D,22 E,31	30
4	A,1 B,6 D,18 E,31	30

因为展台后面的数字表示在该展台参观的时间戳，因此总的时间为最后的时间戳减去进入的时间戳。
我们可以轻易的看出来，H是不满足最小支持度的（H为非频繁单项集），因此我们去掉非频繁的展台，则原始的数据库将会更新为：

Sid	Path	Total—time
1	A,1 B,7 C,15 D,20 E31	30
2	A,1 B,4 C,15 E,26	25
3	A,2 C,10 D,22 E,32	30
4	A,1 B,6 D,18 E,31	30

因为A展台为频繁单项集，我们以A作为前缀构造投影数据库:

Sid	Prefix	projection_database
1	A – 1	B,7 C,15 D,20 E31
2	A – 1	B,4 C,15 E,26
3	A – 2	C,10 D,22 E,32
4	A – 1	B,6 D,18 E,31

Prefix项中我们要记录其频繁单项集所在路线中的时间戳，我们设置的时间间隔界限为5，则I0 = (0，5], I1 = (5，10]，以此类推，然后构建表格：

1-frequent item	I0	I1	I2	I3	I4	I5
B	2	1	0	0	0	0
C	0	1	2	0	0	0
D	0	0	0	2	0	0
E	1	2	0	0	1	3

解释一下上面数字的来历，我们知道前缀是A，构建了投影数据库，我们需要知道的是满足时间间隔和频繁单项两个条件的项。左边的为除去前缀的其他的频繁单项集。
例如B，在Sid1中的时间戳是7，而A点的时间戳是1，因此Sid1中的B与A的时间间隔为7-1 = 6∈I1 = (5，10]，因此我们在表格中的该出加1，因为Sid4中的B与A的间隔为6-1 = 5∈I0 = (0，5]，Sid2中的B与A的间隔为4-1 = 3∈I0 = (0，5]，因此（I0，B）处为2满足最小支持度。
我们就能找到满足最小支持度的项（此处指的是二元组）
注意：我们减去前缀的时间戳，是减去该序列中前缀所包含的时间戳。

我们知道（I0，B）是满足最小支持度的，因此我们就生成了新的前缀（A，I0 , B）以此项来构建投影数据库：

Sid	Prefix	projection_database
1	（A，I0 , B） – 7	C,15 D,20 E31
2	（A，I0 , B） – 4	C,15 E,26
4	（A，I0 , B） – 6	D,18 E,31

前缀后面的数字是前缀中的最后一个展台的时间戳，然后建表去寻找频繁项，

1-frequent item	I0	I1	I2	I3	I4	I5
C	0	1	1	0	0	0
D	0	0	2	0	0	0
E	1	2	0	0	3	0

因此我们知道满足条件的项为（I2，D）和（I4，E）所以我们得到的新的频繁序列为（A，I0 , B，I2，D）与（A，I0 , B，I4，E）我们在继续构造投影数据库，然后进行挖掘直到不会再产生满足最小支持度的项。因此我们就会得到一系列的频繁序列，这个就是我们挖掘到的路径信息。
如果用到实际的运用中我们挖掘的信息也不是去找你不都能用的，例如我们推荐的是一整条路线，整条路线就要包含出口和入口，我们在例子中是的A是入口，E是出口，因此要满足这个条件。
上面的两条序列，（A，I0 , B，I2，D）不满足出入口条件因此不能作为候选路线，（A，I0 , B，I4，E）满足条件因此可以作为候选路线。
（A，I0 , B，I4，E）我们可以理解为推荐用户从A进入，大约会花费I0时间到达B，然后花费I4时间到达E。

I-PrefixSpan与PrefixSpan的区别

I-PrefixSpan算法用的思想是与PrefixSpan一样的。都是通过前缀生成投影数据库，挑选满足条件（就是满足最小支持度）的项。

两者也有一些区别：

PrefixSpan算法是单项中的遍历，寻找满足最小支持度的项
I-PrefixSpan算法不仅点要满足最小支持度，时间间隔也要满足最小支持度，因此除寻找单项集后续的寻找是包含两种信息的元组要满足最小支持度。
I-PrefixSpan是不会出现ab这样的项的，可以理解为不会出现一次参观两个地方。

有错误希望指出，小编会尽快改正的。