写在前面：序列模式挖掘已经是一个被广泛研究的领域，为了解决因寻找合适的阈值而需要的无效时间问题，top-k思想自然提上议程。而在top-k领域，如何快速提升阈值是最关键的环节，因此，主要学习本算法的局部优先探索思路。

Efficient Mining of Top-K Sequential Patterns

介绍

序列模式挖掘（sequential pattern mining）是一个被广泛研究的数据挖掘问题，对网络点击流、程序执行、医学数据、生物数据等方面的分析有很大的帮助。这类算法的判断标准是支持度阈值（support threshold），通过给定一个最低阈值（minsup），寻找那些其支持度（support）大于该指定阈值的子序列，这些序列被认为是有趣的。但问题在于绝大多数情况下，合适的阈值并不是那么容易获得，需要反复测试才能得到比较满意的结果。因此，融合top-k思想，抛开设定阈值问题，选取最好的那一部分作为自己想要的结果，这种思路在一定程度上减少了算法在内存和时间上的开支，也更加让人容易理解。本文介绍的算法TKS是基于SPAM算法改进的，通过新的数据结构PMAP (Precedence Map)减少交操作，当然还有一些阈值提升策略和剪枝策略

解决问题

和其它top-k效用挖掘算法的目标一致，都是在数据集中找出前k个（按支持度从大到小排序）patterns，而minsup通常是第k个pattern的支持度，是一个在挖掘过程中不断变化的值

策略

阈值提升

类似于kHMC算法中的常规阈值提升策略，在每得到一个符合阈值条件的候选项（不是真正的频繁patterns），就把该候选项记录下来，并存储其支持度，当收集数量大于k时，就把第k大的支持度作为当前阈值，然后用与下一个挖掘过程

扩展策略

序列挖掘常见的扩展有 s-extension 和 i-extension，在情节效用挖掘中已经有过详细介绍，这里不做过多阐述。TKS算法提供了一种思路，即对支持度最大的项/序列进行扩展（局部最优思想）。该算法使用了一个变量来记录当前是在对哪些项/序列进行深度扩展，总是优先扩展具有最高支持度的patterns

剪枝策略

上图左边是SPAM算法提供的每个项的bit vector，其实是将数据集视作一条长序列，当一个项集中出现该项那么就置为1，否则为0，这样很自然能想到的一个问题是，如果数据集很大，要花多少时间来得到这些bit vectors？其次，仅仅通过bit vectors相交来计算更长序列的支持度，有可能会得到数据集中没有出现的序列；所以，上图右边是TKS算法提供的每个项的Map结构。通过一次扫描数据集，记录每个项的可扩展项，这些扩展项的符合扩展条件的频次，以及扩展方式（s-extension 或 i-extension），而且为了减小规模，该算法把构建时间点放在了删除低频次项之后进行，虽然这就需要第二次扫描数据集。原理是和Aprioir一致，低频次的项不可能构成高频次的项集，通过这个新构建的PMAP，可以很容易得知哪些构造不出来高频次高阶项集，进而避免使用bit vector进行交运算

Ps. 论文中也提到优化bit vector的效率办法，这一点可以参考下面的代码实现过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

	/**
	 * Set a bit to 1 in this bitmap
	 * @param sid the sid corresponding to that bit
	 * @param tid the tid corresponding to that bit
	 * @param sequencesSize the list of sequence length to know how many bits are allocated to each sequence
	 */
	public void registerBit(int sid, int tid, List<Integer> sequencesSize) {
		// calculate the position of the bit that we need to set to 1
		int pos = sequencesSize.get(sid) + tid;
		// set the bit to 1
		bitmap.set(pos, true);
		
		// Update the count of bit set to 1
		if(sid != lastSID){
			support++;
			sidsum += sid;
		}

		if(firstItemsetID == -1 || tid < firstItemsetID){
			firstItemsetID = tid;
		}
		
		// remember the last SID with a bit set to 1
		lastSID = sid;
	}

算法

TKS main procedure

Output procedure

Search procedure

总结

从最后的实验数据来看，TKS算法 的优异性很明显，在k值很大的情况下仍然能够短时间内得出正确的结果。但个人认为bit vector不一定得记录整个长序列的出现情况，可以对每条序列进行id编号，只需要用map记录每个项在哪些id中出现即可，这在一定程度上是可以减少计算的工作量；个人认为最值得借鉴的地方在于尽可能对高支持度的pattern进行深度探索，因为是top-k算法，本身高支持度情况下就有可能产生更高的支持度（虽然概率是变得越来越低），但同样也能够在后续提前剪掉其它低支持度的项集，避免多余的工作量