关联度算法

‘壹’ 关联分析 分析在哪些情况下，一种算法比其他算法好

灰色关联度分析法是一种多因素统计分析方法，它是以各因素的样本数据为依据用灰色关联度来描述因素间关系的强弱、大小和次序，若样本数据反映出的两因素变化的态势(方向、大小和速度等)基本一致，则它们之间的关联度较大

‘贰’ 关联算法(关联规则学习) 的理论定义假设中哪个地方用到(X È Y概率)哪个地方用到条件概率

关联规则，是量化一个蕴含表达式X->Y，的支持度和置信度，当表达式的支持度和执行度都超过我们设定的阈值的时候，找出这样的规则出来
其中支持度就是x和y的，共同出现的概率
知信度就是在x出现的条件下，Y出现的概率，就是你说的条件概率了

‘叁’ 关联算法除了支持度和置信度还有什么方法

apriori算法有支持度和置信度两个概念，都是在执行算法之前自己设定的，在每一次迭代过程后，大于支持度的项集被保留为频繁项集，最后生成的规则由最终的频繁项集组成，简单说也就是支持度越小，频繁项集越多，置信度越小

‘肆’ 如何进行关联度分析

关联度分析法是一种多因素统计分析方法，它是以各因素的样本数据为依据用灰色关联度来描述因素间关系的强弱、大小和次序。
（1）确定反映系统行为特征的参考数列和影响系统行为的比较数列

反映系统行为特征的数据序列，称为参考数列。影响系统行为的因素组成的数据序列，称比较数列。

（2）对参考数列和比较数列进行无量纲化处理

由于系统中各因素的物理意义不同，导致数据的量纲也不一定相同，不便于比较，或在比较时难以得到正确的结论。因此在进行灰色关联度分析时，一般都要进行无量纲化的数据处理。

（3）求参考数列与比较数列的灰色关联系数ξ（Xi）

4）求关联度
因为关联系数是比较数列与参考数列在各个时刻（即曲线中的各点）的关联程度值，所以它的数不止一个，而信息过于分散不便于进行整体性比较。因此有必要将各个时刻（即曲线中的各点）的关联系数集中为一个值，即求其平均值，作为比较数列与参考数列间关联程度的数量表示。

（5）关联度排序
因素间的关联程度，主要是用关联度的大小次序描述，而不仅是关联度的大小。

‘伍’ 如何计算两个指标间的关联程度

两个指标相关系数r 的计算公式为 r = Cov xi , xj x i x j , ( 2) 其中, r 表示两个指标之间的相关系数; 协方差Cov xi , xj 表示两个指标的相关性强弱程度; 标准差x i x j 表示指标的离散程度. 对于n 个评价指标, 可以分别计算出两两之间的相关系数, 形成相关系数阵 R= r 11 ! r1n   r n1 ! rnn . ( 3) 相关系数的大小可以证明两个指标之间的关联性强弱关系, 如果相关系数大, 就证明两个 指标间相互影响作用较强, 其关联性就较强; 反之, 相关系数小, 就证明两个指标间相互影响作 用较弱, 其关联性就较弱. 因此, 可以通过计算相关系数, 并通过取值大小的范围来分析评价指 标之间的关联性

‘陆’ 灰色关联度法的计算步骤

灰色系统关联分析的具体计算步骤如下：
（1）确定反映系统行为特征的参考数列和影响系统行为的比较数列
反映系统行为特征的数据序列，称为参考数列。影响系统行为的因素组成的数据序列，称比较数列。
（2）对参考数列和比较数列进行无量纲化处理
由于系统中各因素的物理意义不同，导致数据的量纲也不一定相同，不便于比较，或在比较时难以得到正确的结论。因此在进行灰色关联度分析时，一般都要进行无量纲化的数据处理。
（3）求参考数列与比较数列的灰色关联系数ξ（Xi）
所谓关联程度，实质上是曲线间几何形状的差别程度。因此曲线间差值大小，可作为关联程度的衡量尺度。对于一个参考数列X0有若干个比较数列X1, X2,…, Xn，各比较数列与参考数列在各个时刻（即曲线中的各点）的关联系数ξ（Xi）可由下列公式算出：
其中 ζ为分辨系数，0<ζ<1。
是第二级最小差，记为Δmin。 是两级最大差，记为Δmax。
为各比较数列Xi曲线上的每一个点与参考数列X0曲线上的每一个点的绝对差值。记为Δoi(k)。所以关联系数ξ（Xi）也可简化如下列公式：
（4）求关联度ri
因为关联系数是比较数列与参考数列在各个时刻（即曲线中的各点）的关联程度值，所以它的数不止一个，而信息过于分散不便于进行整体性比较。因此有必要将各个时刻（即曲线中的各点）的关联系数集中为一个值，即求其平均值，作为比较数列与参考数列间关联程度的数量表示，关联度ri公式如下：
（5）排关联序
因素间的关联程度，主要是用关联度的大小次序描述，而不仅是关联度的大小。将m个子序列对同一母序列的关联度按大小顺序排列起来，便组成了关联序，记为{x}，它反映了对于母序列来说各子序列的“优劣”关系。若r0i>r0j，则称{xi}对于同一母序列{x0}优于{xj}，记为{xi}>{xj} ；若r0i表1 代表旗县参考数列、比较数列特征值。

‘柒’ 啤酒尿布的关联算法怎么来的

一、故事背景：

在一家超市中，通过大数据分析发现了一个特别有趣的现象：尿布与啤酒这两种风马牛不相及的商品的销售数据曲线竟然初期的相似，于是就将尿布与啤酒摆
在一起。没想到这一举措居然使尿布和啤酒的销量大幅增加了。这可不是一个笑话，而是一直被商家所津津乐道的发生在美国沃尔玛连锁超市的真实大数据案例。原
来，美国的妇女通常在家照顾孩子，所 以她们经常会嘱咐丈夫在下班回家的路上为孩子买尿布，而丈夫在买尿布的同时又会顺手购买自己爱喝的啤酒。

这个发现为商家带来了大量的利润，但是如何从浩如烟海却又杂乱无章的大数据中，发现啤酒和尿布销售之间的联系呢?这又给了我们什么样的启示呢?

这就是关联!

关联，其实很简单，就是几个东西或者事件是经常同时出现的，“啤酒+尿布”就是非常典型的两个关联商品。所谓关联，反映的是一个事件和其他事件之间
依赖或关 联的知识。当我们查找英文文献的时候，可以发现有两个英文词都能形容关联的含义。第一个是相关性relevance，第二个是关联性
association，两者都可以用来描述事件之间的关联程度。其中前者主要用在互联网的内容和文档上，比如搜索引擎算法中文档之间的关联性，我们采用

的词是relevance;而后者往往用在实际的事物之上，比如电子商务网站上的商品之间的关联度我们是用association来表示的，而关联规则是
用associationrules来表示的。

如果两项或多项属性之间存在关联，那么其中一项的属性值就可以依据其
他属性值进行预测。简单地来说，关联规则可以用这样的方式来表示：A→B，其中A被称为前提或者左部(LHS)，而B被称为结果或者右部(RHS)。如果
我们要描述关于尿布和啤酒的关联规则(买尿布的人也会买啤酒)，那么我们可以这样表示：买尿布→买啤酒。

关联规则的发现过程可分为如下两步：

第一步是迭代识别所有的频繁项目集(FrequentItemsets)，要求频繁项目集的支持度不低于用户设定的最低值;

第二步是从频繁项目集中构造置信度不低于用户设定的最低值的规则，产生关联规则。识别或发现所有频繁项目集是关联规则发现算法的核心，也是计算量最大的部分。

支
持度和置信度两个阈值是描述关联规则的两个最重要的概念。一项目组出现的频率称为支持度，反映关联规则在数据库中的重要性。而置信度衡量关联规则的可信程
度。如果某条规则同时满足最小支持度(min-support)和最小置信度(min-confidence)，则称它为强关联规则。

关联规则数据挖掘阶段

第
一阶段必须从原始资料集合中，找出所有高频项目组(LargeItemsets)。高频的意思是指某一项目组出现的频率相对于所有记录而言，必须达到某一
水平。以一个包含A与B两个项目的2-itemset为例，我们可以求得包含{A,B}项目组的支持度，若支持度大于等于所设定的最小支持度
(MinimumSupport)门槛值时，则{A,B}称为高频项目组。一个满足最小支持度的k-itemset，则称为高频k-项目组
(Frequentk-itemset)，一般表示为Largek或Frequentk。算法并从Largek的项目组中再试图产生长度超过k的项目集
Largek+1，直到无法再找到更长的高频项目组为止。

关联规则挖掘的第二阶段是要产生关联规则。从高频项目组产生关联规则，是利用前一步骤的高频k-项目组来产生规则，在最小可信度(MinimumConfidence)的条件门槛下，若一规则所求得的可信度满足最小可信度，则称此规则为关联规则。

例如：经由高频k-项目组{A,B}所产生的规则，若其可信度大于等于最小可信度，则称{A,B}为关联规则。

就
“啤酒+尿布”这个案例而言，使用关联规则挖掘技术，对交易资料库中的记录进行资料挖掘，首先必须要设定最小支持度与最小可信度两个门槛值，在此假设最小

支持度min-support=5%且最小可信度min-confidence=65%。因此符合需求的关联规则将必须同时满足以上两个条件。若经过挖掘
所找到的关联规则{尿布，啤酒}满足下列条件，将可接受{尿布，啤酒}的关联规则。用公式可以描述为：

Support(尿布，啤酒)≥5%andConfidence(尿布，啤酒)≥65%。

其
中，Support(尿布，啤酒)≥5%于此应用范例中的意义为：在所有的交易记录资料中，至少有5%的交易呈现尿布与啤酒这两项商品被同时购买的交易行
为。Confidence(尿布，啤酒)≥65%于此应用范例中的意义为：在所有包含尿布的交易记录资料中，至少有65%的交易会同时购买啤酒。

因此，今后若有某消费者出现购买尿布的行为，我们将可推荐该消费者同时购买啤酒。这个商品推荐的行为则是根据{尿布，啤酒}关联规则而定，因为就过去的交易记录而言，支持了“大部分购买尿布的交易，会同时购买啤酒”的消费行为。

从上面的介绍还可以看出，关联规则挖掘通常比较适用于记录中的指标取离散值的情况。

如果原始数据库中的指标值是取连续的数据，则在关联规则挖掘之前应该进行适当的数据离散化(实际上就是将某个区间的值对应于某个值)，数据的离散化是数据挖掘前的重要环节，离散化的过程是否合理将直接影响关联规则的挖掘结果。

‘捌’ 关联分析的关联分析的方法

Apriori算法是挖掘产生布尔关联规则所需频繁项集的基本算法，也是最着名的关联规则挖掘算法之一。Apriori算法就是根据有关频繁项集特性的先验知识而命名的。它使用一种称作逐层搜索的迭代方法，k—项集用于探索（k+1）—项集。首先，找出频繁1—项集的集合．记做L1，L1用于找出频繁2—项集的集合L2，再用于找出L3，如此下去，直到不能找到频繁k—项集。找每个Lk需要扫描一次数据库。
为提高按层次搜索并产生相应频繁项集的处理效率，Apriori算法利用了一个重要性质，并应用Apriori性质来帮助有效缩小频繁项集的搜索空间。
Apriori性质：一个频繁项集的任一子集也应该是频繁项集。证明根据定义，若一个项集I不满足最小支持度阈值min_sup，则I不是频繁的，即P（I）<min_sup。若增加一个项A到项集I中，则结果新项集（I∪A）也不是频繁的，在整个事务数据库中所出现的次数也不可能多于原项集I出现的次数，因此P（I∪A）<min_sup，即（I∪A）也不是频繁的。这样就可以根据逆反公理很容易地确定Apriori性质成立。
针对Apriori算法的不足，对其进行优化：
1）基于划分的方法。该算法先把数据库从逻辑上分成几个互不相交的块，每次单独考虑一个分块并对它生成所有的频繁项集，然后把产生的频繁项集合并，用来生成所有可能的频繁项集，最后计算这些项集的支持度。这里分块的大小选择要使得每个分块可以被放入主存，每个阶段只需被扫描一次。而算法的正确性是由每一个可能的频繁项集至少在某一个分块中是频繁项集保证的。
上面所讨论的算法是可以高度并行的。可以把每一分块分别分配给某一个处理器生成频繁项集。产生频繁项集的每一个循环结束后．处理器之间进行通信来产生全局的候选是一项集。通常这里的通信过程是算法执行时间的主要瓶颈。而另一方面，每个独立的处理器生成频繁项集的时间也是一个瓶颈。其他的方法还有在多处理器之间共享一个杂凑树来产生频繁项集，更多关于生成频繁项集的并行化方法可以在其中找到。
2）基于Hash的方法。Park等人提出了一个高效地产生频繁项集的基于杂凑（Hash）的算法。通过实验可以发现，寻找频繁项集的主要计算是在生成频繁2—项集Lk上，Park等就是利用这个性质引入杂凑技术来改进产生频繁2—项集的方法。
3）基于采样的方法。基于前一遍扫描得到的信息，对它详细地做组合分析，可以得到一个改进的算法，其基本思想是：先使用从数据库中抽取出来的采样得到一些在整个数据库中可能成立的规则，然后对数据库的剩余部分验证这个结果。这个算法相当简单并显着地减少了FO代价，但是一个很大的缺点就是产生的结果不精确，即存在所谓的数据扭曲（Dataskew）。分布在同一页面上的数据时常是高度相关的，不能表示整个数据库中模式的分布，由此而导致的是采样5%的交易数据所花费的代价同扫描一遍数据库相近。
4）减少交易个数。减少用于未来扫描事务集的大小，基本原理就是当一个事务不包含长度为志的大项集时，则必然不包含长度为走k+1的大项集。从而可以将这些事务删除，在下一遍扫描中就可以减少要进行扫描的事务集的个数。这就是AprioriTid的基本思想。 由于Apriori方法的固有缺陷．即使进行了优化，其效率也仍然不能令人满意。2000年，Han Jiawei等人提出了基于频繁模式树（Frequent Pattern Tree，简称为FP-tree）的发现频繁模式的算法FP-growth。在FP-growth算法中，通过两次扫描事务数据库，把每个事务所包含的频繁项目按其支持度降序压缩存储到FP—tree中。在以后发现频繁模式的过程中，不需要再扫描事务数据库，而仅在FP-Tree中进行查找即可，并通过递归调用FP-growth的方法来直接产生频繁模式，因此在整个发现过程中也不需产生候选模式。该算法克服了Apriori算法中存在的问颢．在执行效率上也明显好于Apriori算法。

‘玖’ 地质关联度（R值）法

灰色系统理论是20世纪80年代初期由中国学者邓聚龙教授创立的一门系统科学新学科。它以“部分信息未知”的“小样本”，“贫信息”不确定性系统为研究对象，主要通过对“部分”已知信息的生成、开发，提取有价值的信息，实现对系统规律的正确描述和有效控制。

用关联度圈定地质异常的基本原理与地质相似系数相同。关联度的含义也是单元之间的相似程度，只是计算方法不同而已。关联分析是灰色系统中定量研究两个事物之间关联程度的一种方法。其实质是通过曲线间几何形状的分析和对比来计算曲线间的关联程度，并认为几何形状越接近（相似）的曲线，其发展变化的态势越接近，则关联程度越大。在研究地质异常时，单元之间的关联度越大，则该两个单元的地质条件越相似，否则地质条件发生很大的变化。因此，我们可以和相似系数一样，统计地质图中能取得的地层、构造、岩浆岩等变量的取值。计算每个单元（称为参考单元）与周围8个单元（称为被比较单元）之间的关联度，取其平均值作为该单元与周围单元的关联程度。公式：

ξ_i（k）=A/B （5-8）

其中

ξ_i（k）是第k个变量的被比较单元与参考单元的相对差值，这种相对差值称为关联系数，ζ称为分辨系数，一般取0.5。

根据p个变量的关联系数，取其平均值作为两个单元之间的关联度：

西南三江中段成矿规律与成矿预测研究

其中R_ij表示参考单元（i）与被参考单元（j）之间的关联度。计算了某一个单元（参考单元）与周围8个单元（被比较单元）的关联度之后，可取其平均值作为该单元与周围单元的关联度：

西南三江中段成矿规律与成矿预测研究

为了便于圈定地质异常，我们将关联度转换成不关联度：不关联度=1-关联度，最后可通过圈定等值线或进行趋势分析确定地质异常，除了计算每个方格与周围方格的不关联程度（不关联系数）外，还计算每个方格与平均值之间的不关联程度。

在邓聚龙教授定义的这个关联系数公式（5-8）中，含有分辨系数ζ，分辨系数取不同的值可能得到完全相反的结果，大连舰艇学院的吴焕芹在《灰色理论中关联系数公式的改进及新的数据生成方法》一文中，给予了讨论，这里不作探讨，按常规取0.5处理。

‘拾’ 关联规则算法的关联规则的定义

所谓关联，反映的是一个事件和其他事件之间依赖或关联的知识。当我们查找英文文献的时候，可以发现有两个英文词都能形容关联的含义。第一个是相关性relevance，第二个是关联性association，两者都可以用来描述事件之间的关联程度。
设I={i1,i2…,im}为所有项目的集合，设A是一个由项目构成的集合，称为项集。事务T是一个项目子集,每一个事务具有唯一的事务标识Tid。事务T包含项集A，当且仅当AT。如果项集A中包含k个项目，则称其为k项集。D为事务数据库，项集A在事务数据库D中出现的次数占D中总事务的百分比叫做项集的支持度（support）。如果项集的支持度超过用户给定的最小支持度阈值，就称该项集是频繁项集（或大项集）。
关联规则就是形如XY的逻辑蕴含关系，其中XI，YI且XY=Φ，X称作规则的前件，Y是结果，对于关联规则XY，存在支持度和信任度。
支持度是指规则中所出现模式的频率，如果事务数据库有s%的事务包含XY，则称关联规则XY在D中的支持度为s%，实际上，可以表示为概率P（XY），即support（XY）= P（XY）。信任度是指蕴含的强度，即事务D中c%的包含X的交易同时包含XY。若X的支持度是support(x)，规则的信任度为即为：support(XY)/support(X)，这是一个条件概率P（Y|X），即confidence（XY）= P（Y|X）。