图情大数据-文本关联分析

基于关键字的关联分析主要发现经常一起出现的关键字或关键词，并找出其关联或相互关系。与基于文本数据集的多数分析一样，关联分析要先对文本数据进行预处理，然后调用关联规则挖掘算法。基于关键字的文本关联分析与传统关系数据库项集间的关联分析类似。如果把文本看成事务，文本中的特征词或关键词看成事务中的项，那么文本事务可表示成：｛document-ID，keyword1，keyword2，keyword3，…，keyword n｝。文本数据库的关键字关联分析问题就转化成事务数据库中事务项的关联挖掘。为便于叙述，以下将文本集中的特征词也称为项或者特征项。与传统关联规则挖掘算法相同，文本关联分析也包括两个主要步骤：

①挖掘频繁共现的关键词，即频繁项集。

②根据频繁项集产生关键词间的关联规则。

这里主要介绍两种挖掘频繁项集的算法，一种是Apriori算法，另一种是FP-Growth算法。而对于相关性分析，这里主要介绍CCA算法。

1）Apriori算法

频繁项集是指经常出现在一起的物品的集合，关联规则暗示两种物品之间可能存在很强的关系。一个项集的支持度被定义为数据集中包含该项集的记录所占的比例。可信度或置信度是针对一条诸如“｛尿布｝→｛葡萄酒｝”的关联规则来定义的。这条规则的可信度被定义为“支持度（｛尿布→啤酒｝）／支持度（｛尿布｝）”。尽管大部分关联规则分析的实例来自零售业，但该技术同样可以用于其他行业，比如文本的关联分析等。

Apriori算法原理：如果某个项集是频繁的，那么它的所有子集也是频繁的。反过来看，也就是说，如果一个项集是非频繁集，那么它的所有超集也是非频繁的。

Apriori算法过程：Apriori算法的两个输入参数分别是最小支持度和数据集。该算法首先会生成所有单个项的项集列表，接着扫描交易记录来查看哪些项集满足最小支持度的要求，那些不满足最小支持度的项集会被去掉。然后，对剩下的集合进行组合以生成包含两个元素的项集。接下来，再重新扫描记录，去掉不满足最小支持度的项集。重复该过程，直到所有项集都被去掉。

Apriori算法主要流程如下：

①当集合中项的个数大于0时。

②构建一个k个项组成的候选项集的列表。

③检查数据以确认每个项集都是频繁的。(www.xing528.com)

④保留频繁项集并构建k+1项组成的候选项集的列表。

⑤从频繁项集中挖掘关联规则。

关联规则的量化指标称为可信度。一条规则P→H的可信度定义为support（P｜H）／support（P）。类似于频繁项集的产生，我们可以为每个频繁项集产生许多关联规则。如果能够减少规则数目来确保问题的可解性，那么计算起来就会好很多。如果每条规则并不满足最小可信度要求，那么该规则的所有子集也不会满足最小可信度要求。

2）FP-Growth算法

FP-Growth算法使用一种压缩的数据结构FP-Tree，该数据结构可存储关联规则挖掘所需的全部数据信息。该算法通过对给定的源数据进行两次扫描，将数据信息存储到这种结构里，避开了产生候选项集的步骤，极大地减少了数据交换和频繁匹配的开销。实验表明，FP-Growth对不同长度的规则都有很好的适应性，同时在效率上较之Apriori算法有很大的提高。

由于在FP-Growth算法生成PT-Tree的过程中，事务集的数目越多，需要遍历的节点数目也越多，理想条件出现的可能性也就越低，这必然使得搜索共享前缀变得非常耗时。因此有人提出改进算法，确保在理想条件下，遍历节点的第一个子女节点就发现相同前缀。为此，把事务集的每个事务按照满足最小支持度的频繁1-项集依支持度降序排列得到数据库D，再对D′的整个数据集按照L的次序进行排序得到数据库D″，在D″数据库的基础上建立PT-Tree挖掘频繁项目集。

3）CCA与KCCA算法

CCA是典型关联分析（canonical correlation analysis）的简写。KCCA是核典型关联分析（kernel canonical correlation analysis）的简写。

通常，对于一维的数据而言，相关系数就可以很好地帮助我们得到数据之间的相关性，但是当我们面对高维数据的时候，相关系数就无法直接使用。而CCA算法给我们提供了另一种思路，就是将多维的数据X 和Y都用线性变换为一维的X′和Y′，然后再用相关系数来看两者之间的相关性。将数据从多维变到一维，也可以理解为CCA是在进行降维，将高维数据降到一维，然后再用相关系数进行相关性的分析。

CCA的算法思想是：假设我们的数据集是X和Y，X为m×n1的样本矩阵，Y为m×n2的样本矩阵，其中m为样本个数，而n1，n2分别为X和Y的特征维度。对于X矩阵，我们将其投影到一维，或者说进行线性表示，对应的投影向量或者说线性系数向量为a；对于Y矩阵，我们将其投影到一维，或者说进行线性表示，对应的投影向量或者说线性系数向量为b。这样X，Y 投影后得到的一维向量分别为X′，Y′。我们有X′=aT X，Y′=bTY。CCA的优化目标是最大化ρ（X′，Y′），得到对应的投影向量a，b。也就是说，CCA算法的目标最终转化为一个优化过程，只要求出了这个优化目标的最大值，就是前面提到的多维X和Y的相关性度量，而对应的a，b则为降维时的投影向量，或者说线性系数。这个函数优化一般有两种方法，第一种是奇异值分解SVD，第二种是特征分解，两者得到的结果一样，具体的方法就不在这里详细叙述。

CCA算法被广泛应用于数据相关度的分析，同时还是偏最小二乘法的基础。但是由于它依赖于数据的线性表示，当我们的数据无法线性表示时，CCA就无法使用，此时我们可以利用核函数的思想，将数据映射到高维后，再利用CCA的思想降维到一维，求对应的相关系数和线性关系，这个算法一般称为KCCA。KCCA算法相较于CCA算法，可以处理高维非线性数据，但是计算量相对来说会大一些。