前言
本篇博客出于学习交流目的，主要是用来记录自己学习后的理解，过程中遇到的问题和心路历程，方便之后回顾。过程中可能引用其他大牛的博客，文末会给出相应链接，侵删！
REMARK：本人菜鸟一枚，如有理解错误还望大家能够指出，相互交流。也是第一次以博客的形式记录，文笔烂到自己都看不下去，哈哈哈
本博客介绍一些高效用频繁模式挖掘以及传统高效用top-k挖掘的基本概念，具体算法在Top-k高效用项集挖掘学习笔记(二) TKU，Top-k高效用项集挖掘学习笔记(三) TKO 中详细记录，请手动跳转。
正文
Top-k挖掘算法研究意义：解决传统高效用模式频繁项集挖掘需要人为设置阈值的问题，太大或太小的阈值都不好，而重复计算不同阈值结果又造成多次无用重复执行。
一些可能会涉及到的定义：
高效用项集 (HUI)：high utility itemset ，如果一个项集不小于用户自定义的最小效用阈值；
有价值的交易效用 (TWU)：transaction-weighted utilization，一种高效用频繁挖掘模型，也作项集的效用值上界值；
高价值的交易效用项集 (HTWUI)：high transaction-weighted utilization itemset ，TWU中效用值大于阈值的项集，由于TWU是效用值上界，所以HTWUI一定包含HUI；
传统基于TWU的模型，包含两个步骤，phase I ：获得所有HTWUI集合（由于TWU是效用值上界，所以HTWUI一定包含HUI）；phase II：再基于HTWUI集合具体计算获得HUI；
Top-k高效用项集挖掘即在考虑效用值场景下进行Top-k挖掘。
Top-k高效用项集挖掘面临的主要挑战：
1）高效用项集不具有单调性或反单调性，所以剪枝是很有难度的；
2）怎么结合现有TWU算法和top-k概念。因为在phase I 时候如果确保所有HTWUI一定包含HUI，起始设置最小阈值为0，但这可能会带来一个很大的搜索空间；
3）没有给定的阈值，随着算法的进行不断更新边界阈值， min_utilBorder m i n _ u t i l B o r d e r (border minimum utility threshold), min_utilBorder m i n _ u t i l B o r d e r 最初为0，如果不能高效的更新将面临巨大的计算时间和存储开销；
4）如何在不丢失Top-k HUIs 的情况下高效的增大阈值 min_utilBorder m i n _ u t i l B o r d e r
论文中提出了两种算法：
(1)TKU (mining Top-K Utility itemsets) ；在Top-k高效用项集挖掘_学习笔记(二) TKU会介绍，其中还包括五种优化策略：PE、NU、MD、MC、SE
(2)TKO (mining Top-K utility itemsets in One phase) ；Top-k高效用项集挖掘_学习笔记(三) TKO 中介绍，还包括三个剪枝策略：RUC、RUZ、EPB；请手动跳转。
在开始正式算法之前，还是先看一堆枯燥的定义，我也很绝望，不过后面一直要用到，所以必须认真理解！！！大部分是我按自己的理解解释的，英语原版看原始论文。
高效用项集基本定义
总项集（distinct items） I∗={
I1,I2,⋯,Im} I ∗ = { I 1 , I 2 , ⋯ , I m } ；事务数据集（transactional database） D={
T1,T2,⋯,Tm} D = { T 1 , T 2 , ⋯ , T m } ；交易记录 Tr∈D T r ∈ D 是 I∗ I ∗ 的子集， r r 是
；并且对于每个 Ij∈Tr I j ∈ T r 都有一个内部效用值 Q(Ij,Tr) Q ( I j , T r ) ，同时对于每个 Ij∈I∗ I j ∈ I ∗ 都有一个外部效用值 P(Ij,D) P ( I j , D ) ；一个项集 X={
I1,I2,⋯,IL} X = { I 1 , I 2 , ⋯ , I L } 共有 L L 个不同的项，
也称作项集 X X 的长度；
表示项集长度为 L L 。
Definition 1. 项的绝对效用值(Absolute utility of an item)：
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/72731.html