数据挖掘中的模式发现(一)频繁项集、频繁闭项集、最大频繁项集_SuPhoebe的博客-程序员宝宝_最大频繁项集

技术标签: 模式发现  机器学习与数学模型  频繁项集  数据挖掘  

Frequent Itemset(频繁项集)

I = { i 1 , i 2 , . . . , i m } I=\{i_1, i_2, ..., i_m\} I={ i1,i2,...,im}项(Item)的集合 D = { T 1 , T 2 , . . . , T n } D=\{T_1, T_2, ...,T_n\} D={ T1,T2,...,Tn} i ∈ [ 1 , n ] i∈[1,n] i[1,n]事务数据集(Transaction Data Itemsets),事务 T i T_i Ti I I I中若干项组成。

S S S为由项组成的一个集合, S = { i ∣ i ∈ I } S=\{i|i∈I\} S={ iiI},简称项集(Itemset)。包含k个项的项集称为k-项集

t t t为一条事务, 如果 S ⊆ t S\subseteq t St, 则称事务 t t t包含 S S S

S S S的支持度 s u p ( S ) = ( 包 含 S 的 事 务 数 量 D 中 总 的 事 务 数 量 ) × 100 % sup(S) = ({包含S的事务数量\over D中总的事务数量})\times 100\% sup(S)=(DS)×100%

S S S的支持度≥给定最小支持度,称 S S S频繁项集(Frequent Itemset)

例如,有交易数据库

TID item
1 abc
2 abcd
3 bce
4 acde
5 de

TID为事务编号,item为事务数据集的内容。

现在有项集 S 1 = { b , c } S_1 = \{b,c\} S1={ b,c},它出现在TID为1,2,3的事务中,也就是 S 1 ⊆ { a , b , c } S_1\subseteq \{a,b,c\} S1{ a,b,c} S 1 ⊆ { a , b , c , d } S_1\subseteq \{a,b,c,d\} S1{ a,b,c,d} S 1 ⊆ { b , c , e } S_1\subseteq \{b,c,e\} S1{ b,c,e}

所以 S 1 S_1 S1的支持度计数为3,支持度为 3 5 3\over 5 53

如果支持度阈值小于 60 % 60\% 60%,那么 S 1 S_1 S1就是一个频繁项集。

Superset(超集)

若一个集合 S 2 S_2 S2中的每一个元素都在集合 S 1 S_1 S1中,且集合 S 1 S_1 S1中可能包含 S 2 S_2 S2中没有的元素,则集合 S 1 S_1 S1就是 S 2 S_2 S2的一个超集。 S 1 S_1 S1 S 2 S_2 S2的超集,则 S 2 S_2 S2 S 1 S_1 S1的真子集,反之亦然。

接着上面的例子,

TID item
1 abc
2 abcd
3 bce
4 acde
5 de

现在有项集 S 1 = { b , c } S_1 = \{b,c\} S1={ b,c},那么它就是 { b } \{b\} { b} { c } \{c\} { c}的超集。 S 1 S_1 S1也是 { a , b , c } \{a,b,c\} { a,b,c}等的真子集。

Max Pattern/Maximal Frequent Itemset(最大频繁项集)

如果频繁项集L的所有超集都是非频繁项集,那么称L为最大频繁项集称最大频繁模式,记为MFI (Maximal Frequent Itemset)。

频繁项集是最大频繁项集的子集。最大频繁项集中包含了频繁项集的频繁信息,且通常项集的规模要小几个数量级。所以在数据集中含有较长的频繁模式时挖掘最大频繁项集是非常有效的手段。

综上,最大频繁项集是各频繁k项集中符合无超集条件的频繁项集。

接着上面的例子,

TID item
1 abc
2 abcd
3 bce
4 acde
5 de

现在有项集 S 1 = { b , c } S_1 = \{b,c\} S1={ b,c},且有支持度阈值 = 60 % =60\% 60%

那么 S 1 S_1 S1就是一个频繁项集,那么我们来看看它的超集。

Superset count
abc 2
bcd 1
bce 1
abcd 1
abce 0
bcde 0
abcde 0

由此可见,它们的支持度都小于 60 % 60\% 60%,所以它们都不是频繁项集。

所以 S 1 S_1 S1的所有超集都不是频繁项集,则它是最大频繁项集。

close pattern(闭合频繁项集)

所谓闭项集,就是指一个项集X,它的**直接超集(最小的严格超集)**的支持度计数都不等于它本身的支持度计数。如果闭项集同时是频繁的,也就是它的支持度大于等于最小支持度阈值,那它就称为闭频繁项集。

接着上面的例子,

TID item
1 abc
2 abcd
3 bce
4 acde
5 de

因为项集{b,c}出现在TID为1,2,3的事务中,所以{b,c}的支持度计数为3。而{b,c}的直接超集:{a,b,c}的支持度计数为2,都不等于{b,c}的支持度计数3,所以{b,c}为闭项集,如果支持度阈值为40%,则{b,c}也为闭频繁项集。

项集{a,b}出现在TID为1,2的事务中,其支持度计数为2。而它的直接超集{a,b,c}支持度计数也为2,所以{a,b}不是闭项集。

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/u013007900/article/details/54743395

智能推荐

centos7 安装rmp mysql 5.7过程_LittleLeFans的博客-程序员宝宝

1. 查看系统中是否已安装 MySQL 服务:rpm -qa | grep mysql或yum list installed | grep mysql2. 如果已安装则删除 MySQL 及其依赖的包:yum -y remove mysql-libs.x86_643. 下载 mysql57-community-release-el7-8.noarch.rpm 的 YU

突破select的FD_SETSIZE限制_sukhoi27smk的博客-程序员宝宝

前言: 在很多比较各种网络模型的文章中,但凡提到select模型时,都会说select受限于轮询的套接字数量,这个数量也就是系统头文件中定义的FD_SETSIZE值(例如64)。但事实上这个算不上真的限制。 C语言的偏方: 在C语言的世界里存在一个关于结构体的偏门技巧,例如:  typedefstruct _str_type{   int _len;

【splishsplash】splishsplash入门使用_beidou111的博客-程序员宝宝

本文档的目地为总结splishsplash的使用方法splishsplash是一个C++开源流体引擎,主要用于产生流体动画。 它的核心算法是SPH法。资源汇总github: https://github.com/InteractiveComputerGraphics/SPlisHSPlasH文档:https://splishsplash.readthedocs.io/en/latest/算法论文:https://interactivecomputergraphics.github.io/SPH-T

复试占比低的985计算机,考研调剂有多难?本科985计算机调剂双非竟然都没法进复试!..._weixin_39710003的博客-程序员宝宝

一名本科天津大学计算机的考生21年报考的复旦大学计算机专硕,分数354分无奈今年复旦扎堆复试线355分,他只能进行调剂,开始想着往上海大学、西南大学、中国地质大学武汉等211高校调剂,结果到现在想要往天津科技大学、武汉科技大学等双非院校调剂都没有得到回复,本科985分数也不算低调剂都这样,今年调剂多难可见一斑!1.考研调剂其实非常玄学,结果更是无法预测!考研一旦进入调剂阶段就非常玄学,你说考研调剂...

【Less-7】into outfile写入webshell_多学点技术的博客-程序员宝宝_into outfile 写shell

目录一、测试注入点二、判断字段数三、into outfile写入webshell一、测试注入点源码:$sql="SELECT * FROM users WHERE id=(('$id')) LIMIT 0,1";$result=mysql_query($sql);$row = mysql_fetch_array($result); if($row) { echo '<font color= "#FFFF00">'; echo 'You are in.... Us

随便推点

百度人脸识别python调用例子_diaojiao6326的博客-程序员宝宝

# 首先pip install baidu-aip# SDK文档链接http://ai.baidu.com/docs#/Face-Python-SDK/topimport base64from aip import AipFaceAPP_ID = '16374788'API_KEY = 'KZvxjNG1BI1eP4uubRADf9DT'SECRET_...

AVFoundation框架理论+实战一(文本语音转换)_星宇大前端的博客-程序员宝宝

前言:本专栏主要是AVFoundation开发秘籍一书的总结和学习。下面是这本书的扫描版:链接: https://pan.baidu.com/s/1miy0K7A 密码: ateq  (仅供学习使用)AVFoundation 相关知识涉及类:AVSpeechSynthesizer:   这是语音播放的关键API类,相当于一个发声器,他可以播放一条

luoguP1965转圈游戏[快速幂]_liaoxiyan123的博客-程序员宝宝

题目描述n 个小伙伴(编号从0到 n-1)围坐一圈玩游戏。按照顺时针方向给 n个位置编号,从0到n-1。最初,第 0号小伙伴在第 0号位置,第1号小伙伴在第1号位置,……,依此类推。游戏规则如下:每一轮第0号位置上的小伙伴顺时针走到第m 号位置,第 11号位置小伙伴走到第 m+1号位置,……,依此类推,第n − m号位置上的小伙伴走到第 0 号位置,第n- m+1号位置上的小伙伴走到第1 号位置,……,第n-1号位置上的小伙伴顺时针走到第m-1号位置。现在,一共进行了10k{10^k}10k轮,请问x号

DM9161_u010977327的博客-程序员宝宝_dm9161的应用电路

DM9161AEP是一款完全集成的和符合成本效益单芯片快速以太网PHY,是采用较小工艺0.25um的10/100M自适应的以太网收发器。DM9161AEP通过可变电压的 MII 或 RMII 标准数字接口连接到 MAC 层,支持 HP Auto-MDIX†。是目前常见的一款物理层收发器,由于全球的MCU集成度不断提高,由早先的MAC+PHY+MII的衍生到现在的PHY,在以太网部分的成本,逐渐降低

小波分析用于阈值去噪_正经人708的博客-程序员宝宝_小波阈值去噪

文章目录目录文章目录前言一、小波去噪概述二、小波阈值去噪介绍关于阈值去噪的方法阈值的选取优缺点仅供参考前言在去噪领域中,小波理论由于其特殊的优点受到了许多学者的重视,他们应用小波进行去噪,并获得了非常好的效果。一、小波去噪概述噪声可以理解为妨碍人的视觉器官或系统传感器对所接收信息进行理解或分析的各种因素。一般噪声是不可预测的随机信号,它只能用概率统计的方法去认识。噪声主要在信号的获取(量化)和传输中产生...

OPENCV学习笔记二:numpy用法_<YU>的博客-程序员宝宝_opencv的numpy

二、numpy简单用法NumPy(Numerical Python) 是 Python 语言的一个扩展程序库,支持大量的维度数组与矩阵运算,此外也针对数组运算提供大量的数学函数库。而图片本质上是一个个像素点叠加,一整张图片就像一个数组一样,所以numpy的使用对于opencv的学习来说必不可少本文资料主要来自于菜鸟教程https://www.runoob.com/numpy/numpy-tut...

推荐文章

热门文章

相关标签