?
?
?
关联式规则
关联式规则(Association Rules,AR)，又称关联规则，是数据挖掘的一个重要课题，用于从大量数据中挖掘出有价值的数据项之间的相关关系。关联规则解决的常见问题如：“如果一个消费者购买了产品A，那么他有多大机会购买产品B?”以及“如果他购买了产品C和D，那么他还将购买什么产品？”正如大多数数据挖掘技术一样，关联规则的任务在于减少潜在的大量杂乱无章的数据，使之成为少量的易于观察理解的静态资料。
关联规则一个经典的实例是购物篮分析(Market Basket Analysis)。超市对顾客的购买记录数据库进行关联规则挖掘，可以发现顾客的购买习惯，例如，购买产品X的同时也购买产品Y，于是，超市就可以调整货架的布局，比如将X产品和Y产品放在一起，增进销量。
基本概念
| TID | 网球拍 | 网 球 | 运动鞋 | 羽毛球 |
|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 0 |
| 2 | 1 | 1 | 0 | 0 |
| 3 | 1 | 0 | 0 | 0 |
| 4 | 1 | 0 | 1 | 0 |
| 5 | 0 | 1 | 1 | 1 |
| 6 | 1 | 1 | 0 | 0 |
根据韩家炜等[1]，关联规则定义为：
假设
用一个简单的例子说明。表1是顾客购买记录的数据库D，包含6个事务。项集I={网球拍,网球,运动鞋,羽毛球}。考虑关联规则：网球拍
分类
关联规则有以下常见分类[1]：
根据关联规则所处理的值的类型
- 如果考虑关联规则中的数据项是否出现，则这种关联规则是布尔关联规则(Boolean association rules)。例如上面的例子。
- 如果关联规则中的数据项是数量型的，这种关联规则是数量关联规则(quantitative association rules)。例如年龄("20-25")
购买("网球拍")，年龄是一个数量型的数据项。在这种关联规则中，一般将数量离散化(discretize)为区间。
根据关联规则所涉及的数据维数
- 如果关联规则各项只涉及一个维，则它是单维关联规则(single-dimensional association rules)，例如购买("网球拍")
购买("网球")只涉及“购买”一个维度。 - 如果关联规则涉及两个或两个以上维度，则它是多维关联规则(multi-dimensional association rules)，例如年龄("20-25")
购买("网球拍")涉及“年龄”和“购买”两个维度。
根据关联规则所涉及的抽象层次
- 如果不涉及不同层次的数据项，得到的是单层关联规则(single-level association rules)。
- 在不同抽象层次中挖掘出的关联规则称为广义关联规则(generalized association rules)。例如年龄("20-25")
购买("HEAD网球拍")和年龄("20-25")
购买("网球拍")是广义关联规则，因为"HEAD网球拍"和"网球拍"属于不同的抽象层次。
算法
Apriori 算法
Apriori算法是种最有影响的挖掘布尔关联规则频繁项集的算法。它的核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。在这里，所有支持度大于最小支持度的项集称为频繁项集(简称频集)，也常称为最大项目集。
在Apriori算法中，寻找最大项目集(频繁项集)的基本思想是：算法需要对数据集进行多步处理。第一步，简单统计所有含一个元素项目集出现的频数，并找出那些不小于最小支持度的项目集，即一维最大项目集。从第二步开始循环处理直到再没有最大项目集生成。循环过程是：第k步中，根据第k-1步生成的(k-1)维最大项目集产生k维侯选项目集，然后对数据库进行搜索，得到侯选项目集的项集支持度，与最小支持度进行比较，从而找到k维最大项目集。
下面以图例的方式说明该算法的运行过程： 假设有一个数据库D，其中有4个事务记录，分别表示为：
| TID | Items |
|---|---|
| T1 | I1,I3,I4 |
| T2 | I2,I5 |
| T3 | I1,I2,I5 |
| T4 | I2,I5 |
这里预定最小支持度minSupport=2,下面用图例说明算法运行的过程：
| TID | Items |
|---|---|
| T1 | I1,I5 |
扫描D，对每个候选项进行支持度计数得到表C1:
| 项集 | 支持度计数 |
|---|---|
| {I1} | 2 |
| {I2} | 3 |
| {I3} | 3 |
| {I4} | 1 |
| {I5} | 3 |
比较候选项支持度计数与最小支持度minSupport，产生1维最大项目集L1：
| 项集 | 支持度计数 |
|---|---|
| {I1} | 2 |
| {I2} | 3 |
| {I3} | 3 |
| {I5} | 3 |
由L1产生候选项集C2：
| 项集 |
|---|
| {I1,I2} |
| {I1,I3} |
| {I1,I5} |
| {I2,I3} |
| {I2,I5} |
| {I3,I5} |
扫描D，对每个候选项集进行支持度计数:
| 项集 | 支持度计数 |
|---|---|
| {I1,I2} | 1 |
| {I1,I3} | 2 |
| {I1,I5} | 1 |
| {I2,I3} | 2 |
| {I2,I5} | 3 |
| {I3,I5} | 2 |
比较候选项支持度计数与最小支持度minSupport，产生2维最大项目集L2：
| 项集 | 支持度计数 |
|---|---|
| {I1,I5} | 2 |
由L2产生候选项集C3：
| 项集 |
|---|
| {I2,I5} |
比较候选项支持度计数与最小支持度minSupport，产生3维最大项目集L3：
| 项集 | 支持度计数 |
|---|---|
| {I2,I5} | 2 |
算法终止。
从算法的运行过程，我们可以看出该Apriori算法的优点：简单、易理解、数据要求低，然而我们也可以看到Apriori算法的缺点：(1)在每一步产生侯选项目集时循环产生的组合过多，没有排除不应该参与组合的元素;(2)每次计算项集的支持度时，都对数据库D中的全部记录进行了一遍扫描比较，如果是一个大型的数据库的话，这种扫描比较会大大增加计算机系统的I/O开销。而这种代价是随着数据库的记录的增加呈现出几何级数的增加。因此人们开始寻求更好性能的算法，如下面要介绍的F-P算法。
F-P算法
针对Apriori算法的性能瓶颈问题-需要产生大量候选项集和需要重复地扫描数据库，2000年Jiawei Han等人提出了基于FP树生成频繁项集的FP-growth算法。该算法只进行2次数据库扫描且它不使用侯选集，直接压缩数据库成一个频繁模式树，最后通过这棵树生成关联规则。研究表明它比Apriori算法大约快一个数量级。
FP-growth算法是一种不产生候选模式而采用频繁模式增长的方法挖掘频繁模式的算法。算法只需要扫描2次数据库：第一次扫描数据库，得到1维频繁项集；第二次扫描数据库，利用1维频繁项集过滤数据库中的非频繁项，同时生成FP树。由于FP树蕴涵了所有的频繁项集，其后的频繁项集的挖掘只需要在FP树上进行。FP树挖掘由两个阶段组成:第一阶段建立FP树，即将数据库中的事务构造成一棵FP树；第二阶段为挖掘FP树，即针对FP树挖掘频繁模式和关联规则。
FP-growth算法描述：
输入：事务数据库D，最小支持度minSupport。
输出：频繁模式的完全集。
方法：
1 构建FP树:
1.1 扫描事务数据库，收集频繁项集F并统计支持度，对F按支持度降序排序，得到频率排序好的项表L。
1.2 创建FP树的根节点，用“null”标记它。对于D中每个事务T，执行：选择T中的频繁项，并按L中的次序排序。设排序后的频繁项表为[p|P]，其中p是第一个元素，而P是剩余元素的表。调用insert_tree([p|P],T)。该过程执行情况如下：如果T有子女N使得N.itemName=p.itemName，则N的计数增加1；否则创建一个新节点N，将其计数设置为1，链接到它的父节点T，并且通过节点链结构将其链接到具有相同itemName的节点。如果P非空，递归地调用insert_tree(P,N)。
2 FP树的规则挖掘(通过FP-growth(Tree,α)函数来实现，初始调用FP-growth(Tree,null)):
if Tree含单个路径P then {
for 路径P中节点的每个组合(记作β)
产生模式β∪α，其支持度support=β中节点的最小支持度; }
else for each αi 在Tree的头部 do {
产生模式β=αi ∪ α,其支持度support=αi.support;
构造β的条件模式基,然后构造β的条件FP树Treeβ;
if Treeβ≠空集 then
调用FP_growth(Treeβ,β) }
end
F-P算法实现
Bash版本：请参考文章FP-growth算法实现
Eclat算法
与fp-growth 和apriori算法不同，Eclat算法加入了倒排的思想，具体就是将事务数据中的项作为key，每个项对应的事务ID作为value。
原输入数据为
| tid | item |
|---|---|
| 1 | A,B |
| 2 | B,C |
| 3 | A,C |
| 4 | A,B,C |
转换后为：
| item | tids |
|---|---|
| A | 1,4 |
| B | 1,4 |
| C | 2,4 |
通过转换后的倒排表可以加快频繁集生成速度。 其算法思想是 由频繁k项集求交集，生成候选k+1项集 。对候选k+1项集做裁剪，生成频繁k+1项集，再求交集生成候选k+2项集。如此迭代，直到项集归一。 根据上述数据的情况，具体计算过程为
算法过程：
1.计算频繁1项集，结果为：
| item | freq |
|---|---|
| A | 3 |
| B | 3 |
| C | 3 |
2.由频繁1项集生成频繁2项集
| item | freq |
|---|---|
| A,B | 2 |
| A,C | 2 |
| B,C | 2 |
3.由频繁2项集生成频繁3项集
| item | freq |
|---|---|
| A,C | 1 |
频繁k项集生成频繁k+1项集的过程与由1项集生成2项集的过程完全一致。
这里有个隐含的条件是，两个频繁k项集生成k+1项集时，前k-1项是一致的,A,B+A,C==>A,C
Eclat算法实现
eclat的核心思想就是倒排，这种数据处理方式很适合用关系型数据表示和实现。 具体可参考用关系型数据结构实现Eclat算法——Hive
参考文献
- ^?1.0?1.1?J. Han,M. Kamber. Data Mining: Concepts and Techniques. Morgan Kaufmann: 2000
关联规则算法
关联规则的定义
（二）关联规则的算法
关联规则
关联规则是形如X→Y的蕴涵式，其中且， X和Y分别称为关联规则的先导(antecedent或left-hand-side,LHS)和后继(consequent或right-hand-side,RHS) 。
什么是关联规则
从啤酒与尿布的故事说起
数据关联
关联规则的定义
关联规则的简单例子
|
TID
|
网球拍
|
网 球
|
运动鞋
|
羽毛球
|
|
1
|
1
|
1
|
1
|
0
|
|
2
|
1
|
1
|
0
|
0
|
|
3
|
1
|
0
|
0
|
0
|
|
4
|
1
|
0
|
1
|
0
|
|
5
|
0
|
1
|
1
|
1
|
|
6
|
1
|
1
|
0
|
0
|
关联规则挖掘的过程
两个阶段
案例分析
关联规则的分类
关联规则挖掘的相关算法
Apriori算法
基于划分的算法
FP-树频集算法
该领域在国内外的应用
关联规则发掘技术在国内外的应用
近年来关联规则发掘技术的一些研究
作??? 者： 康耀红著
I S B N： 7560604196
页??? 数： 222
封面形式： 简装本
出 版 社： 西安电子科技大学出版社
出版日期： 2006-5-1
内容简介
数据融合是许多传统学科和新兴工程领域相结合而产生的一个新的前沿技术领域，是现代C3I系统的重要组成部分。本书是我国第一本关于多传感器数据融合理论的专著。
全书共分12章。第一章阐述数据融合的意义、理论基础、实现技术和研究现状；第二章和第三章研究多传感器目标检测理论和性能评估；第四章至第八章论述数据关联和目标跟踪的算法与理论；第九章介绍身份估计的基本思想与方法；第十章至第十二章介绍态势评估和威胁估计的基本理论，以及在这一领域有广泛应用前景的条件事件代数理论和规划识别理论。
本书适用于通信、控制和信号处理等领域的大学生、研究生和相关领域的科研、工程技术人员。
本书目录
第一章概论
*1.1数据融合的目的和应用
1.2数据融合的理论基础
1.2.1数据融合的一般处理模型
1.2.2数据融合的概念与结构分类
1.3数据融合的实现技术
1.3.1目标跟踪
1.3.2目标识别
1.3.3态势评估和威胁估计(STA)
1.4数据融合的研究现状和如何推动我国数据融合研究的进展
1.4.1理论研究应着眼未来、强调创新
1.4.2技术研究应面向世界、追求突破
1.4.3人才培养应面向教育
1.4.4加强学术交流，全方位协调发展
补记
参考文献
第二章多传感器目标检测的基本理论
2.1问题描述
2.2贝叶斯方法
2.3Neyman??Pearson方法
2.4系统检测率和系统虚警率
2.5同类传感器情形下的讨论
补记
参考文献
第三章多传感器目标检测的性能评估
3.1传感器检测的基本特性
3.2传感器检测性能分析
3.3传感器的检测性能评估
补记
参考文献
第四章目标跟踪与数据关联概论
4.1多目标跟踪的基本思想
4.2数据关联的概念与方法
4.2.1“最近邻”方法
4.2.2“全邻”最优滤波器
4.2.3概率数据关联滤波器
4.2.4多模型方法
4.2.5相互作用多模型—概率数据关联滤波器
4.2.6联合概率数据关联滤波器
4.2.7多假设方法
4.2.8航迹分裂方法
4.2.9分布式多传感器多目标跟踪与数据关联的一般理论
4.2.10基于神经网络的多目标数据关联方法
补记
参考文献
第五章相互作用多模型—概率数据关联算法
5.1概率数据关联滤波器
5.1.1预备知识
5.1.2概率数据关联滤波器的基本思想
5.1.3关联概率βi(k)的计算
5.1.4协方差P(k|k)的计算
5.2多模型算法(MultipleModelApproach)
5.3相互作用多模型—概率数据关联算法
5.4多传感器相互作用多模型—概率数据关联算法
5.4.1多传感器概率数据关联滤波器
5.4.2多传感器多模型—概率数据关联滤波器
*5.5目标运动模型(TargetMotionModels)
5.5.1基本理论
5.5.2几个典型的目标运动模型
补记
参考文献
第六章联合概率数据关联和多假设滤波器
6.1联合概率数据关联算法
6.1.1联合概率数据关联算法的基本思想
6.1.2联合事件的概率计算
6.1.3协方差计算
6.1.4n=1时JPDA和PDA等价性证明
6.2多假设滤波器
6.2.1假设的产生和假设树的形成
6.2.2假设估计
6.2.3假设管理
补记
参考文献
第七章多传感器多目标跟踪的一般理论
7.1分布式多传感器多目标跟踪的基本思想与功能结构
7.2单目标分布式跟踪
7.2.1中心估计
7.2.2分布式估计
7.3多假设多目标跟踪
7.3.1航迹和假设
7.3.2递归假设估计
7.3.3成批假设估计
7.4分布式多目标跟踪
7.4.1等级多目标跟踪
7.4.2分布式多目标跟踪
补记
参考文献
第八章多目标跟踪系统的性能评估
8.1航迹分类
8.2跟踪评估指标
8.3混合评价指标的设计
8.4一般评价模型
补记
参考文献
第九章身份识别
9.1基于Bayes统计理论的身份识别
9.1.1古典概率理论及其在身份识别中的应用
9.1.2基于Bayes统计理论的身份识别
9.2基于DempsterShafer证据理论的身份识别
9.2.1基本理论
9.2.2单传感器多测量周期可信度分配的融合
9.2.3多传感器多测量周期可信度分配的融合
9.3面向对象的数据融合算法及其神经网络实现[7]
9.3.1分类和跟踪处理模型
9.3.2数据融合算法
9.3.3融合算法的神经网络实现
补记
参考文献
第十章态势评估和威胁估计的基本理论
10.1指挥、控制和通信系统的基础理论
10.1.1兰切斯特(Lanchester)战斗模型
*10.1.2指挥、控制和通信模型
10.2军事问题的一般求解模型
10.2.1状态转移模型
10.2.2SHOR模型
补记
参考文献
第十一章条件事件代数理论
11.1问题提出
11.1.1逻辑与概率表示不相容
11.1.2Simpson悖论[5，6]
11.2条件事件代数的定义及其性质
11.2.1布尔代数
11.2.2Lewis定理
11.2.3GNW(GoodmanNguyenWalker)条件事件代数
11.2.4条件事件代数的运算性质
补记
参考文献
第十二章规划识别理论及其应用
12.1基本概念
12.1.1规划识别理论概述
12.1.2规划识别与规划(Planning)
12.1.3规划识别与态势评估
12.2真实环境下的规划识别的要求
12.2.1真实环境的特点
12.2.2动态性问题
12.3锁孔式规划识别的研究
12.3.1规划识别模型
12.3.2规划识别中认知属性的分析
12.3.3真实环境下规划识别逻辑完备性分析
12.3.4真实环境下的规划识别过程模型
12.3.5FIND过程的研究与设计
12.3.6监测过程的策略
12.4预测式规划识别的理论研究与实现
12.4.1预测式规划识别与态势评估
12.4.2Bayes概率理论和D-S推理
12.4.3Bayes因果网络
12.4.4预测与Bayes因果网络
12.5真实环境下的规划识别模型及其性能分析
12.5.1综合模型
12.5.2综合模型性能分析
补记
参考文献
强关联
强关联，又称强关联电子系统(Strongly correlated electronic systems)，是指电子间的交互作用不可忽略的系统，这类材料又称强关联材料(Strongly correlated material)。
在最简单的固体理论中，固体中的电子之间的静电相互作用被忽略了，不会出现在哈密顿算符里。故各个电子被看成是独立的，不会相互影响（唯一的影响来自泡利不相容原理）。然而，在许多物质中（以过渡金属氧化物和镧系氧化物最典型，下面以前者为例），3d电子轨道之间交叠很大，d轨道上的电子相互靠近，静电能的增加将不能忽略。把这一部分能量写入哈密尔顿量，就得到强关联模型（又称赫巴德模型(Hubbard model))。
顾名思义，电子此时相互影响，故称强关联。用这个模型，可以很容易的阐述莫特绝缘体(Mott insulator)。多数具有铁磁性或反铁磁性的物质，以及高温超导体、自旋材料、铁磁超导体等也是强关联的结果。