[转载]前缀树trie预测与热度扩散预测模型

trie分类

从根节点到叶子节点，从根节点开始搜索，在其节点上搜索其子节点的内容与之相匹配，迭代搜索，直到搜索到叶子结点或者内容结束（不局限于叶子结点），读取该节点上的内容，即为所查找的内容，trie又被称为字典树，如果被搜索的内容是字典内容的子集，那么可以在字典树中搜索到该内容。在预测或者说查询过程中，如果遇到这样的情况：被搜索的内容不是字典的子集，那么将搜索不到。搜索不到的时候，需要将该内容增加到树上，使得下次可以被搜索到。其中分类部分，主要是对没被标记的内容，依据前缀树的经验进行分类，例如：冷/热预测；好/坏预测。二分类，多分类都可以。

热度扩散

主要解决的问题是：对于非字典树中的内容进行预测和分类过程中，借助：树模型的热度值，兄弟节点的热度扩散值，以及具有相关性的节点的热度扩散值，得到可靠的分类结果。在最大可搜索的父节点下面，其兄弟子节点的热度关系，往往影响其新来的兄弟节点热度。

实现过程

分为3个过程。其中第1点和第2点通过训练数据集实现，第3点在验证数据集实现。

  1. 树的建立与节点数据内容的初始化。

利用训练数据集预先建立非完备（如果可以完备更好）的trie树，节点数据包括：例如，每个节点上记录了该节点的被访问频次，代表该节点的热度值（多级热度：不仅仅包含本节点的热度，同样来源于兄弟节点的热度，相关节点的热度扩散值等等），设置阈值划分节点的多种分类类别。划分好类别的节点，如果预测的内容被该节点覆盖，那么可以将该节点的热度值做为预测内容的分类结果。节点的数据内容根据实际情况可进行伸缩设定，并在树的建立过程中进行初始化。

  1. 树的生长与剪枝，即T时间段的树更新学习，同时支持可持久化。

在树建立完成之后，需要实时对树节点内容的热度更新，确保树的时效性，类似于动态LRU，即某个节点的分类类别是不固定的，在前一点时间是热的分类类别，在后一点时间是冷的类别，这也是这个模型的灵活分类优势。为了方便下次很快加载该模型，可通过将整棵树进行保存。

  1. 树的预测与验证。

在测试数据集上，完成对内容的分类，对准确率进行验证。