寻找公共序列的算法

数据挖掘 算法
2021-09-29 02:46:32

假设“1,2,3”是用户的id,active表示最近一个月访问过stackoverflow的人(0=passive,1=active),有正票和负票之分。

id  question       votes                 active
 1     1        -1, +1, -1, -1, -1         0
 1     2        -1, +1, -1, -1, +1         0
 2     1        +1, +1, -1, -1             0
 3     1        +1, +1, +1, -1, +1         1
 3     2        +1, +1, -1, +1, +1, +1     1
 3     3        -1, +1                     1

我想知道是什么让用户停止使用 stackoverflow。想一想,我已经计算了他们获得反对票的次数、总票数、每个问题的平均票数……

我想知道我能从这些序列中得到什么样的信息。我想找到这样的东西:这些被动的用户依次有两个反对票。例如,在用户 1 的第二个问题中,在两次反对票之后的一次赞成票并不能防止用户流失。用户 3 在他的任何问题中都没有任何 2 个连续的反对票。因此,他仍然活跃。

我正在寻找类似 PrefixSpan 算法的东西,但顺序对我来说很重要。我的意思是,我不能像这样写序列

<(-1 +1 -1 -1 -1) (-1 +1 -1 -1 +1 )> 

或者

<(-1) (+1) (-1) (-1) (-1) (-1) (+1) (-1) (-1) (+1 )>. 

因为第一个丢了顺序,第二个把问题混在一起了。是否有任何算法可以找到这些流失者常见的序列?

2个回答

确实不是典型的问题表述。我建议两种方法:

  1. 使用简单的贝叶斯模型,其中状态或节点是您的每个特征。当节点具有直接时间依赖性时直接连接节点(例如 vote1 -> vote2 -> vote3,但不是 vote3 -> vote1)并计算最终(输出)节点成为某物的概率(例如用户类型 1,用户类型 2 等)。您还可以使用一个隐藏的马尔可夫模型,该模型自然地模拟状态之间的转换。在您的情况下,它只会输出 1 个状态(预测)。对于您的问题,我不太喜欢这种模型,但尝试一下可能会很好。不过,您将需要大量数据。
  2. 您可以使用模糊归纳推理 (FIR)。这绝对不是一个简单的算法,但对于具有时间序列或时间相关特征的分类非常有效。在 FIR 中,您希望找到给定深度的最佳掩码。例如,如果您每个样本有 5 个特征,例如,您想知道要选择哪些特征,您将为您的数据学习一个最佳掩码来解决这个问题(并创建模糊规则等)。此外,如果您想关联两个或更多示例,您将为蒙版定义大于 1 的深度。这将允许您找到一个掩码,例如使用样本 t 的特征 1,2 和 4,样本 t+1 的特征 2,3,4 和 5 以及样本 t+2 的特征 1 和 4。将 t 从 1 个样本移动到 N 个样本。因此,从具有时间关系(或某种序列)的样本中创建了有趣的特征组合。

您可以做的一件事是使用关联规则方法,即找到与被动相关的最常见模式,或与被动过度相关的模式:

  1. 设置频率阈值
  2. 找出你正在寻找什么样的模式,例如频繁的序列。如果您可以对它们进行部分排序,这很好,类似于在先验算法中设置包含。例如,查找序列,并按“is subsequence of”对它们进行排序。
  3. 从您正在寻找的一个相当小的最小模式列表开始,通过您的数据计算这些模式的出现次数。
  4. 保持最频繁的模式(高于您的阈值),这是您的第一步频繁模式集。
  5. 通过向您的 step-i 模式添加一些内容来生成 step-i +1模式的候选者。
  6. 计算候选项出现的次数。转到步骤 4,直到步骤i没有更多频繁模式
  7. 然后你有一堆候选规则,你想使用关联规则度量来找到最能预测被动的模式。