爱站程序员基地问题领域
数据挖掘中的序列模式挖掘
问题描述
用户的行为与时间戳一起存储，使事件的时序性成为强大的信息源，日志提供了某段时间用户的全部活动，在顺序数据的情况下，一个小的动作序列很容易被几个人引用，从而让攻击者访问整个动作序列。现有的匿名技术没有考虑序列数据的内在敏感性。
所提方法
所提新技术提供一个匿名的序列数据集，同时保留序列模式挖掘到的结果。使用结合 k-匿名(所公开的数据集是这样的，任何序列都不能与至少 k1 个其他序列区分开来)和序列隐藏方法的方法。
方法在于将匿名化问题重新表述为隐藏 k-非频繁序列的问题，即转换原始序列数据库，使得原始数据集中支持度小于 k 的序列不能再被挖掘。假设攻击者知道属于一个人的部分序列，并且他/她也知道这个人存在于数据库中，那么他/她就有 1/k 的概率重建整个序列。
给定一个支持阈值，超过阈值的被定义为频繁序列。
算法
保证最后的匿名表满足K匿名，并且原表和匿名表是相似的。
The BF-P2kA algorithm：
- 第一步：构建前缀树PT：
- 第二步：前缀树匿名化：给定最小支持阈值k，小于k的阈值将被从前缀树中删除。然后这些不常见序列的一部分被重新附加到前缀树中。
实际上，该函数通过修剪所有不频繁的子树并更新到最后一个频繁节点的路径支持来修改树。
- 第三步:对前缀树进行后处理，生成序列的匿名数据集。
定义 4 (Levenshtein 距离)。S 和 T 之间的编辑距离由将一个序列转换成另一个序列所需的最小操作数给出，其中操作是插入、删除或替换单个元素。
例子：
两种衡量方式。
