aihot  2017-10-11 22:22:22  机器学习 |   查看评论   

使用Apriori算法进行关联分析

  一句话概要,Apriori算法首先根据所给数据构建只有一个元素的项集,然后判断每个项集的支持度,去掉支持度不足的项集,再组合一元素项集构建二元素项集,再去掉支持度不足的项集,如此不断迭代,直到不存在拥有更多元素的频繁项集。之后是发现关联规则,关联规则产生于频繁项集,一个频繁项集可以生成多条可能的关联规则,我们利用分级法,先生成右边只有一个元素的关联规则,然后判断每条规则的可信度,去掉可信度不足的规则,再将可信度足够的规则拆分子集,生成右边有两个元素的关联规则,再去掉可信度不足的规则,如此不断迭代,直到不存在右侧有更多元素的关联规则。

  关联分析包括发现频繁项集和关联规则,频繁项集是经常出现在一块的物品的集合,关联规则暗示两种物品之间可能存在很强的关系,而且这种关系是有方向性的,A->B和B->A是两条不同的关联规则。

  然后定义支持度与可信度,支持度用来描述频繁项集,可信度用来描述关联规则。一个项集的支持度被定义为数据集中包含该项集的记录所占的比例。如果一共有10条记录,5条记录中出现了A,那A的支持度就是1/2;如果3条记录中同时出现了AB,那AB的支持度就是3/10。可信度是针对由A->B这样的关联规则来定义的,可信度的计算基于支持度,上例中,A->B的可信度就是AB的支持度3/10除以A的支持度1/2,等于3/5;如果要计算B->A的支持度,那除以的就应该是B的支持度。

  上面提到,我们只用支持度足够的一元素项集构建二元素项集,这里用到了一个简单的原理,如果这个一元素项集的支持度未达到阈值,那所有包含该元素的多元素项集的支持度也不可能达到阈值,这个很好理解,因为包含该元素的每个多元素项集的出现次数都不可能高于该元素的出现次数。

  另外,如果某项集本身不是频繁项集,那由该项集生成出来的关联规则,在计算上确实是有可能有足够可信度的,比如A、B、AB均只出现了一次,那A->B,B->A的可信度都是100%,但我们不选择采信该关联规则,因为数据量太小。

  上面还提到,我们只选择拆分可信度足够的关联规则来找更进一步的关联规则,这里同样用到一个原理,如果某条规则不满足最小可信度要求,那该规则的所有子集也不可能满足最小可信度的要求。

  举个例子,我们找到一个频繁项集0123,首先它可以生成这样4条关联规则:123->0、023->1、013->2、012->3。如果012->3这条关联规则的可信度不够,则12->03、02->13、01->23这三条关联规则也不可能达到足够的可信度。因为如果012->3这条关联规则的可信度不够,那么表示0123的支持度/012的支持度已经不能满足可信度需求,而01、02、12的支持度必然大于012的支持度,这种条件下,可信度计算公式的分子不变而分母增大,总可信度必然是减小的,所以更不可能高于可信度的最小阈值。既然12->03、02->13、01->23不满足可信度要求,那就更不要说2->013、1->023、0->123了,证明同理。这种根据频繁项集找关联项集的方式也被叫做分级法。

FP-growth算法发现频繁项集

  一句话概要,FP指频繁项集(Frequent Pattern),FP-growth专门用来发现频繁项集,速度快于Apriori,只扫描数据集两次,一次构建FP树,一次从FP树中挖掘频繁项集。常被用来做输入联想,比如在百度搜索框里输入『为什么』,就会联想出一些有意思的东西。

  FP-growth速度快于Apriori,因为Apriori对于每个潜在的数据集都会扫描一遍数据集来判定其支持度是否达到要求。FP-growth只扫描数据集两次,一次构建FP树,一次从FP树中挖掘频繁项集。

  那什么是FP树?FP树通过链接来连接相似元素,被连起来的元素项可以看成一个链表,示例如下:

FP树

用于生成FP树的数据

  同搜索树不同的是,一个元素项可以在一棵FP树中出现多次。FP树会存储项集的出现频率,而每个项集会以路径的方式存储在树中。存在相似元素的集合会共享树的一部分。只有当集合之间完全不同时,树才会分叉。树节点上给出集合中的单个元素及其所在序列中的出现次数,路径会给出该序列的出现次数。

  上面的FP树就是由下面的数据集生成的,一点点来分析,z一共出现了5次,其中zr(不包括zxyrt)出现1次,zxyrt出现1次,zxyst出现2次,这样加起来,z出现了4次,看数据,发现z还单独出现了1次,所以一共5次。r一共出现了3次,是将3条路径(zrzryrtxsr)中的r出现次数相加。其实我们还可以发现,原数据当中还有一些hjpvuoqem没有在FP树中出现,这里也同样引入了支持度的概念,数据集中出现次数小于3次的字母不被放入树中。

  第一次遍历数据集会获得每个元素项的出现频率,接下来过滤掉不满足最小支持度的元素项,之后对数据集中的每条数据按照元素项的绝对出现频率来排序。在构建时,读入每个项集并将其添加到一条已经存在的路径中,如果该路径不存在,则创建一条新路径。除此之外,我们还要建立一个头指针表用来保持对每个满足最小支持度字母的引用。至此,就完成了FP树的构建。

  之后要做的是从FP树中挖掘频繁项集,挖掘频繁项集分为三个步骤:从FP树中获取条件模式基、利用条件模式基构建一个条件FP树、迭代直到树包含一个元素项为止。

  首先是查找条件模式基,条件模式基是以所查找元素为结尾的路径集合,通俗的来讲也就是前缀路径,一条前缀路径是介于所查找元素与树根节点之间的所有内容。我们可以先通过前面的头指针表找到每个频繁项每个元素项的位置,再向前上溯这棵树直到根节点为止,以此来找到所有的前缀路径,也就是条件模式基。

  下面是每个频繁项的条件模式基实例:

 

  大括号里面的,是该条前缀路径上的所有节点,z前面没有别的节点,所以大括号中为空,大括号后面的数字代表了这条前缀路径的出现次数。

  接下来我们要做的是根据条件模式基构建条件FP树,条件FP树的构建与FP树的构建非常相似,区别在于,条件FP树是针对某个频繁项来讲的,我们在上一步中已经找到了每个频繁项的条件模式基,构造该频繁项的条件FP树所使用的数据,就只是该频繁项所对应的条件模式基,也就是说构造初始FP树,我们用的是所有的数据,构建每个频繁项的条件FP树,我们只用这个频繁项的条件模式基。当然,构造条件FP树时,也需要先排序然后去掉不满足最低支持度的项,因为即便某项在全部的数据中是频繁项,但在某频繁项的条件模式基中却不一定是频繁项了。

  接下来再对构建的条件FP树去抽取条件模式基,再迭代构建条件FP树,直到条件树中没有元素为止,如此我们就能得到所有的频繁项集。

其他工具

利用PCA与SVD来简化数据

  PCA是主成分分析的简写,实际上就是将N维数据降维到最能代表数据集真实结构的K个正交维度上去(N>K),且这K个维度是重新构造而成的,而不是从原有N维中选取,这K维特征被称为主成分。其价值在于四点:使数据集更容易使用、降低很多算法的计算开销、去除噪声、使结果易懂。

  PCA对数据进行降维,我们要把高维度的数据去除噪声,只保留最重要的N个维度,那怎么确定需要保留的维度呢?第一个维度选择的是原始数据中方差最大的方向,通俗的讲,就是给定大量数据点,我们画出一条直线,尽可能的经过这些点,这条直线的方向就是方差最大的方向(下面会给出示例图)。接下来要找第二个维度,对第二个维度有这样的要求,它需要与第一个维度正交,我们要在与第一个坐标轴正交的所有坐标轴里找到方差最大的方向作为第二个坐标轴,第三个坐标轴同理,它需要与前两个坐标轴均正交。

  
 

除特别注明外,本站所有文章均为 人工智能学习网 原创,转载请注明出处来自浅谈机器学习基础(下)

留言与评论(共有 0 条评论)
   
验证码: