机器学习（二十三）——常见算法（关联、相似、TF-IDF等）_关联分析类似的算法

笔者是一个痴迷于挖掘数据中的价值的学习人，希望在平日的工作学习中，挖掘数据的价值，找寻数据的秘密，笔者认为，数据的价值不仅仅只体现在企业中，个人也可以体会到数据的魅力，用技术力量探索行为密码，让大数据助跑每一个人，欢迎直筒们关注我的公众号，大家一起讨论数据中的那些有趣的事情。

我的公众号为：livandata

1） Apriori算法：

通过apriori算法来实现频繁项集的查询：

支持度：数据集中包含该项集记录所占的比例，上例中{豆奶}的支持度=2/5，{啤酒，尿布}的支持度=3/5。

置信度：针对像频繁集数量>=2的情况，例如{啤酒，尿布}，那么置信度=支持度({尿布，啤酒})/支持度(尿布)。

置信度的顺序对结果存在影响：

        

两个公式的结果未必一致。

需要注意的是，b和a的位置不同代表着的意思不一样，就像是你买一次啤酒同时去买了十次尿布，和买了十次尿布只买了一次啤酒的感觉时很不同的。

所以利用置信度阈值(ConfidenceThreshold)，将不满足的置信度(Confidence)都过滤掉，剩下的就是该数据集的强关联规则。

2） FP-Growth算法：

我们从头表的底部开始挖掘FP-tree中的频繁模式。在FP-tree中以p结尾的节点链共有两条，分别是<(f:4)，(c:3)，(a:3)，(m:2)，(p:2)>和<(c:1)，(b:1)，(p:1)>。其中，第一条节点链表表示客户购买的物品清单<f，c，a，m，p>在数据库中共出现了两次。需要注意到是，尽管<f，c，a>在第一条节点链中出现了3次，单个物品<f>出现了4次，但是它们与p一起出现只有2次，所以在条件FP-tree中将<(f:4)，(c:3)，(a:3)，(m:2)，(p:2)>记为<(f:2)，(c:2)，(a:2)，(m:2)，(p:2)>。同理，第二条节点链表示客户购买的物品清单<c，b，p>在数据库中只出现了一次。我们将p的前缀节点链<(f:2)，(c:2)，(a:2)，(m:2)>和<(c:1)，(b:1)>称为p的条件模式基（conditional pattern base）。我们将p的条件模式基作为新的事务数据库，每一行存储p的一个前缀节点链，根据第二节中构建FP-tree的过程，计算每一行记录中各种物品的支持度，然后按照支持度降序排列，仅保留频繁项集，剔除那些低于支持度阈值的项，建立一棵新的FP-tree，如下图，基于这一数据图进行频繁项集的挖掘：

比如：以m结尾的频繁项集可以表示为<(f:4)，(c:3)，(a:3)，(m:2)>和<(f:4)，(c:3)，(a:3)，(b:1)，(m:1)>，对应的CPB为{<fcam:2>,<fcabm:1>}。累加每个CPB上的Item计数，低于阈值的删除，得到条件FPTree(Conditional FP-tree)。得到f:3，c:3，a:3，m:3，b:1。E的计数小于阈值3，所以删除，得到C的条件FP Tree如下：

{fcam:3}，这一频繁项集可以循环发掘为：mine(<(f:3)，(c:3)，(a:3)|(m:3)>)。按照<(a:3)，(c:3)，(f:3)>的顺序递归调用mine(<(f:3)，(c:3)|a，m>)，mine(<(f:3)|c，m>)，mine(null|f，m)。

对应的算法为：

输入：数据集、最小值尺度
输出：FP树、头指针表
1. 遍历数据集，统计各元素项出现次数，创建头指针表
2. 移除头指针表中不满足最小值尺度的元素项
3. 第二次遍历数据集，创建FP树。对每个数据集中的项集：
    3.1 初始化空FP树
    3.2 对每个项集进行过滤和重排序
    3.3 使用这个项集更新FP树，从FP树的根节点开始：
        3.3.1 如果当前项集的第一个元素项存在于FP树当前节点的子节点中，则更新这个子节点的计数值
        3.3.2 否则，创建新的子节点，更新头指针表

        3.3.3 对当前项集的其余元素项和当前元素项的对应子节点递归3.3的过程

 

3） PageRank算法：

Ø   如果一个网页被很多其他网页链接到的话说明这个网页比较重要，也就是PageRank值会相对较高

Ø   如果一个PageRank值很高的网页链接到一个其他的网页，那么被链接到的网页的PageRank值会相应地因此而提高。

预先给每个网页一个PR值（下面用PR值指代PageRank值），由于PR值物理意义上为一个网页被访问概率，所以一般是1/N，其中N为网页总数。

这时A的PR值就可以表示为：

4） 深度遍历与广度遍历：

对于一颗二叉树，深度优先搜索(Depth First Search)是沿着树的深度遍历树的节点，尽可能深的搜索树的分支。以上面二叉树为例，深度优先搜索的顺序

为：ABDECFG。怎么实现这个顺序呢？深度优先搜索二叉树是先访问根结点，然后遍历左子树接着是遍历右子树，因此我们可以利用堆栈的先进后出的特点，

现将右子树压栈，再将左子树压栈，这样左子树就位于栈顶，可以保证结点的左子树先与右子树被遍历。

　　广度优先搜索(Breadth First Search),又叫宽度优先搜索或横向优先搜索，是从根结点开始沿着树的宽度搜索遍历，上面二叉树的遍历顺序为：ABCDEFG.

可以利用队列实现广度优先搜索。

5） 动态规划：

隐马模型中维特比算法为常用的动态规划算法，另外有其他的算法为：

下图给出了一个地图，地图中每个顶点代表一个城市，两个城市间的连线代表道路，连线上的数值代表道路长度。

现在，我们想从城市a到达城市E。怎样走才能使得路径最短，最短路径的长度是多少？设

DiS［x］为城市x到城市E的最短路径长度（x表示任意一个城市）；

map[i，j]表示i，j两个城市间的距离，若map[i，j]=0，则两个城市不通；

我们可以使用回溯法来计算DiS［x］：

这个程序的效率如何呢？我们可以看到，每次除了已经访问过的城市外，其他城市都要访问，所以时间复杂度为O（n！），这是一个“指数级”的算法。那么，还有没有效率更高的解题方法呢？

首先，我们来观察上述算法。在求b1到E的最短路径的时候，先求出从C2到E的最短路径；而在求从b2刭E的最短路径的时候，又求了一遍从C2刭E的最短路径。也就是说，从C2到E的最短路径求了两遍。同样可以发现，在求从Cl、C2刭E的最短路径的过程中，从Dl到E的最短路径也被求了两遍。而在整个程序中，从Dl到E的最短路径被求了四遍，这是多么大的一个浪费啊！如果在求解的过程中，同时将求得的最短路径的距离“记录在案”，以便将来随时调用，则可以避免这种重复计算。至此，一个新的思路产生了，即

由后往前依次推出每个Dis值，直到推出Dis「a」为止。

问题是，究竟什么是“由后往前”呢？所谓前后关系是指对于任意一对城市i和j来说，如果满足“或者城市i和城市j不连通或者dis[i]+map[i，j]≥dis[j]”的条件，则定义为城市i在前、城市j在后。因为如果城市i和城市j连通且Dis[i]＋map[i，j]＜Dis「j」，则说明城市j至城市E的最短路径长度应该比Dis[j]更优。可城市j位于城市i后不可能推出此情况，以至于影响最后的解。那么，我们应该如何划分先后次序呢？

如上图所示，从城市a出发，按照与城市a的路径长度划分阶段。

阶段0包含的出发城市有{a}

阶段1所含的城市有{b1，b2}

阶段2包含的出发城市有{C1，C2，C3，C4}

阶段3包含的出发城市有{D1，D2，D3}

阶段4包含城市{E}

这种划分可以明确每个城市的次序，因为阶段的划分具有如下性质

⑴阶段i的取值只与阶段i+1有关，阶段i+1的取值只对阶段i的取值产生影响：

⑵每个阶段的顺序是确定的，不可以调换任两个阶段的顺序；

我们从阶段4的城市E出发，按照阶段的顺序倒推至阶段0的城市a。在求解的各个阶段，利用了k阶段与k+1阶段之间的如下关系

dis[k][x]=

dis[4][E]=0

这个程序的时间复杂度为W(n2)，比回溯法的时间复杂度O（n!）要小得多。

数学之美中动态规划的算法：

大概意思就是北京到广州，横切15刀划出15条线（假使最多经过15个城市，也就划了15条线），假设每条线上有且只有10个城市，通过动态规划算法寻求最短路径相比穷举法，能把问题从10的15次方降到10*10*15。

当时思路上看似懂了的样子，可是对于10*10*15复杂读如何来的，还是不甚明了。（其实压根没完全明白）

最近在poj上A题的时候，遇到一个动态规划问题，一下也卡住了。同时想起了这个最短路径的问题。于是又好好想了下。现记录理解如下，备忘。

可以这么理解最短路径中的动态规划，每往前走一条线，不是基于整个所有可能的线路，而是基于当前最优的路径进行。比如说，从北京到广州，我们简化出模型如下：

Ø  （见上图）层次略去多层，每层个数减少到4。其实问题本质不变，只是缩小了下规模，便于图片说明。图中带箭头的表示是到达该节点的当前最短路径。从北京出发点算作第一层的话，现在已经到了第三层。

再往下走一层，此时分析比较穷举与动态规划的区别。

穷举不区分对待所有路径，没有当前最优之说（没有带箭头与不带箭头的区别），此时相当于任何一条路径往下走都可能构成最短路径，那么其复杂度就是4*4*4。回到原情景，每层10个，共15层，那么10的15次方。这个很好理解。

动态规划实际上就是以空间换时间，基于当前局部最优往下逐步构建全局最优。

首先，以时间换空间，就是我每次记录到达当前层每个节点的最短路径（即用额外空间存储箭头信息），这时往下走的基数直接由整体所有路线变为每个节点只有1条，共10条路线。即基数从10的n次方变为10。因为如果经过节点A，那么全局最优路径肯定是在现有最优路径的基础上往下走。我们可以反推一下，如果不是，那必然存在用当前到达节点A的最优路径取代全局最优路径该那路段，那么就出来了一条新的全局最优路径，这是矛盾的。

到这里就比较明显了。如图

Ø  （见左图）从第三层往第四层走，基于我已记录的带箭头最优路径往下即可、其余的可以忽略，反正也构不成最优路径。这样直接就把复杂度从4*4*4降到了2*4*4。其实关键还在于其往下走的基数缩小。由原本所有路径n的m次方级变成了n。还是回到原情景，每步两层之间10*10这个是没法避免的，但逐层都是基于已有的最优路径，新出10*10的层间路径，直接在已有最优路径上并更新层次和最优信息即可。那么每层都是10*10，共15层。

即复杂度10*10*15。

小结：动态规划实际上就是以空间换时间，基于当前局部最优往下逐步构建全局最优。更细说来，先是划分阶段，然后逐段求取当前局部最优并记录，进而基于记录的局部最优往下推进（相当于局部最优取代了所有可能的路径，相当于剪枝了，降低复杂度也就在这儿了）。

6） TF-IDF算法与余弦定理：

如果要确定一篇文章的主题，可以通过两种方式搞定：TF-IDF算法和余弦定理两种。

第一个：TF-IDF算法：通过主题词确定文章主题。

词频（TF）：某一词汇在本片文档中出现的次数。

停用词："的"、"是"、"在"----这一类最常用的词。

逆文档频率（IDF）：一个重要性调整系数，衡量一个词是不是常见词。如果某个词比较少见，但是它在这篇文章中多次出现，那么它很可能就反映了这篇文章的特性，正是我们所需要的关键词。用统计学语言表达，就是在词频的基础上，要对每个词分配一个"重要性"权重。最常见的词（"的"、"是"、"在"）给予最小的权重，较常见的词（"中国"）给予较小的权重，较少见的词（"蜜蜂"、"养殖"）给予较大的权重，这个权重叫做“逆文档频率”。

知道了"词频"（TF）和"逆文档频率"（IDF）以后，将这两个值相乘，就得到了一个词的TF-IDF值。某个词对文章的重要性越高，它的TF-IDF值就越大。所以，排在最前面的几个词，就是这篇文章的关键词。

具体步骤为：

第一步:计算词频。

考虑到文章有长短之分，为了便于不同文章的比较，进行"词频"标准化。

或者:

第二步:计算逆文档频率。

这时，需要一个语料库（corpus），用来模拟语言的使用环境。

如果一个词越常见，那么分母就越大，逆文档频率就越小越接近0。分母之所以要加1，是为了避免分母为0（即所有文档都不包含该词）。log表示对得到的值取对数。

第三步:计算TF-IDF。

可以看到，TF-IDF与一个词在文档中的出现次数成正比，与该词在整个语言中的出现次数成反比。所以，自动提取关键词的算法就很清楚了，就是计算出文档的每个词的TF-IDF值，然后按降序排列，取排在最前面的几个词。

第二个：余弦定理：确定两篇文章相似度。

为了简单起见，我们先从句子着手。

　　句子A：我喜欢看电视，不喜欢看电影。

　　句子B：我不喜欢看电视，也不喜欢看电影。

请问怎样才能计算上面两句话的相似程度？

基本思路是：如果这两句话的用词越相似，它们的内容就应该越相似。因此，可以从词频入手，计算它们的相似程度。

第一步：分词。

　　句子A：我/喜欢/看/电视，不/喜欢/看/电影。

　　句子B：我/不/喜欢/看/电视，也/不/喜欢/看/电影。

第二步：列出所有的词。

　　我，喜欢，看，电视，电影，不，也。

第三步：计算词频。

　　句子A：我 1，喜欢 2，看 2，电视 1，电影 1，不 1，也 0。

　　句子B：我 1，喜欢 2，看 2，电视 1，电影 1，不 2，也 1。

第四步：写出词频向量。

　　句子A：[1, 2, 2, 1, 1, 1, 0]

　　句子B：[1, 2, 2, 1, 1, 2, 1]

到这里，问题就变成了如何计算这两个向量的相似程度。

我们可以把它们想象成空间中的两条线段，都是从原点（[0, 0, ...]）出发，指向不同的方向。两条线段之间形成一个夹角，如果夹角为0度，意味着方向相同、线段重合；如果夹角为90度，意味着形成直角，方向完全不相似；如果夹角为180度，意味着方向正好相反。因此，我们可以通过夹角的大小，来判断向量的相似程度。夹角越小，就代表越相似。

            

假定a向量是[x1, y1]，b向量是[x2, y2]，那么可以将余弦定理改写成下面的形式：

           

由此，我们就得到了"找出相似文章"的一种算法：

（1）使用TF-IDF算法，找出两篇文章的关键词；

（2）每篇文章各取出若干个关键词（比如20个），合并成一个集合，计算每篇文章对于这个集合中的词的词频（为了避免文章长度的差异，可以使用相对词频）；

（3）生成两篇文章各自的词频向量；

（4）计算两个向量的余弦相似度，值越大就表示越相似。

7） Jaccard相似系数：

评价相似系数主要有两种：Jaccard和皮尔逊。

Ø  Jaccard相似系数

主要用于计算符号度量或布尔值度量的个体间的相似度，因为个体的特征属性都是由符号度量或者布尔值标识，因此无法衡量差异具体值的大小，只能获得“是否相同”这个结果，所以Jaccard系数只关心个体间共同具有的特征是否一致这个问题。如果比较X与Y的Jaccard相似系数，只比较xn和yn中相同的个数，公式如下： 
如集合A={1,2,3,4};B={3,4,5,6}; 
那么他们的J(X,Y)=1{3,4}/1{1,2,3,4,5,6}=1/3;

Ø  皮尔逊相关系数

相关系数的分类： 
0.8-1.0 极强相关 
0.6-0.8 强相关 
0.4-0.6 中等程度相关 
0.2-0.4 弱相关 
0.0-0.2 极弱相关或无相关