当前位置:网站首页>单调性约束与反单调性约束的区别 monotonicity and anti-monotonicity constraint
单调性约束与反单调性约束的区别 monotonicity and anti-monotonicity constraint
2022-07-07 08:39:00 【Xminyang】
▚ 01 Monotone Constraints 单调性约束
1.1 Definitions 定义
【Monotone Constraints | SpringerLink 】
A constraint C is monotone if and only if for all itemsets S and S′:
if S ⊇ S′ and S violates C, then S′ violates C.
1.2 Key Points 要点
Monotone constraints possess the following property. If an itemset S violates a monotone constraint C, then any of its subsets also violates C. Equivalently, all supersets of an itemset satisfying a monotone constraint C also satisfy C (i.e., C is upward closed). By exploiting this property, monotone constraints can be used for reducing computation in frequent itemset mining with constraints. As frequent itemset mining with constraints aims to find frequent itemsets that satisfy the constraints, if an itemset S satisfies a monotone constraint C, no further constraint checking needs to be applied to any superset of S because all supersets of S are guaranteed to satisfy C. Examples of monotone constraints include min(S. Price) ≤ $30, which expresses that the minimum price of all items in an itemset S is at most $30. Note that, if the minimum price of all items in S is at most $30, adding more items to S would not increase its minimum price (i.e., supersets of S would also satisfy such a monotone constraint).
▚ 02 Anti-monotone Constraints 反单调性约束
2.1 Definitions 定义
【Anti-monotone Constraints | SpringerLink】
A constraint C is anti-monotone if and only if for all itemsets S and S′:
if S ⊇ S′and S satisfies C, then S′ satisfies C.
2.2 Key Points 要点
Anti-monotone constraints possess the following nice property. If an itemset S satisfies an anti-monotone constraint C, then all of its subsets also satisfy C (i.e., C is downward closed). Equivalently, any superset of an itemset violating an anti-monotone constraint C also violates C. By exploiting this property, anti-monotone constraints can be used for pruning in frequent itemset mining with constraints. As frequent itemset mining with constraints aims to find itemsets that are frequent and satisfy the constraints, if an itemset violates an anti-monotone constraint C, all its supersets (which would also violate C) can be pruned away and their frequencies do not need to be counted. Examples of anti-monotone constraints include min(S. Price) ≥ $20 (which expresses that the minimum price of all items in an itemset S is at least $20) and the usual frequency constraint support(S) ≥ minsup (i.e., frequency(S) ≥ minsup). For the former, if the minimum price of all items in S is less than $20, adding more items to S would not increase its minimum price (i.e., supersets of S would not satisfy such an anti-monotone constraint). For the latter, it is widely used in frequent itemset mining, with or without constraints. It states that (i) all subsets of a frequent itemset are frequent and (ii) any superset of an infrequent itemset is also infrequent. This is also known as the Apriori property.
▚ 03 Explanation 解释
假设:我们将S violates C作为事件A,S′ violates C作为事件B;则 S satisfies C为事件not A,then S′ satisfies C为事件not B.
此时,根据Monotone Constraints定义知(A → B),也即(not B → not A);
根据Anti-monotonicity Constraints定义知(not A → not B),也即(B → A);
因为(A → B)并不一定意味着(B → A),所以这两者 (Monotone Constraints & Anti-monotonicity Constraints) 的声明是不同的。
▚ 04 Example 示例
For an example. Consider-
C1 = Sum of elements is greater than 5
C2 = Sum of elements is at most 5
U(universe) = Set of non-negative real numbers
In case of C1,
If S violates C1, then S’ obviously violates C1 as well (S being a superset of S’)
Eg. S = {1, 2}, S’ = {2}
Hence C1 is monotonic.
In case of C2,
If S satisfies C2, then S’ obviously satisfies C2 as well (S being a superset of S’)
Eg. S = {1, 2}, S’ = {2}
Hence C2 is anti-monotonic.
▚ 05 数据挖掘的约束限制
Constraint-Based Mining — A General Picture
参考文章
边栏推荐
- 深入分析ERC-4907协议的主要内容,思考此协议对NFT市场流动性意义!
- 【推荐系统 01】Rechub
- 浅谈日志中的返回格式封装格式处理,异常处理
- Gym installation pit records
- 使用 load_decathlon_datalist (MONAI)快速加载JSON数据
- 中级网络工程师是什么?主要是考什么,有什么用?
- P2788 数学1(math1)- 加减算式
- String formatting
- About hzero resource error (groovy.lang.missingpropertyexception: no such property: weight for class)
- ArrayList thread insecurity and Solutions
猜你喜欢
1323:【例6.5】活动选择
Summary of router development knowledge
Leetcode-560: subarray with sum K
[STM32] solution to the problem that SWD cannot recognize devices after STM32 burning program
小程序跳转H5,配置业务域名经验教程
P2788 数学1(math1)- 加减算式
What are the contents of the intermediate soft test, the software designer test, and the test outline?
SQL Server 知识汇集9 : 修改数据
想考中级软考,一般需要多少复习时间?
ThreadLocal会用可不够
随机推荐
深入分析ERC-4907协议的主要内容,思考此协议对NFT市场流动性意义!
BigDecimal数值比较
2022.7.3DAY595
Schnuka: machine vision positioning technology machine vision positioning principle
Leetcode-560: subarray with sum K
Applet jump to H5, configure business domain name experience tutorial
A small problem of bit field and symbol expansion
[detailed explanation of Huawei machine test] tall and short people queue up
Study summary of postgraduate entrance examination in July
[dai6] mirror image of JZ27 binary tree
Trajectory planning for multi-robot systems: Methods and applications 综述阅读笔记
多线程-异步编排
Jump to the mobile terminal page or PC terminal page according to the device information
IDA中常见快捷键
中级网络工程师是什么?主要是考什么,有什么用?
Application of OpenGL gllightfv function and related knowledge of light source
求最大公约数与最小公倍数(C语言)
Review of the losers in the postgraduate entrance examination
施努卡:机器人视觉抓取工作原理 机器视觉抓取
Multithreaded asynchronous orchestration