本节书摘来自华章出版社《Python数据挖掘：概念、方法与实践》一书中的第2章，第2.3节，作者[美] 梅甘·斯夸尔（Megan Squire），更多章节内容可以访问云栖社区“华章计算机”公众号查看。

2.3　项目—发现软件项目标签中的关联规则

1997年，Freshmeat网站创立，它是一个跟踪免费、*和开放源码软件（FLOSS）项目的目录。2011年，该网站更名为Freecode。在出售、并购和多次网站重新设计之后，2014年，Freecode网站的所有更新都停止了。这个网站仍然在线，但是不再更新，目录中也不再加入任何新项目。现在，Freecode是20世纪90年代和21世纪初FLOSS项目相关信息的快照。每个软件项目的相关事实包括名称、描述、下载软件的URL、描述其特征的标签、代表其流行度的一个数值，等等。

作为我的FLOSSmole项目的一部分，我从2005年起就将来自Freshmeat/Freecode的数据编目。Freshmeat/Freecode提供定期的RDF下载，描述网站上的每个项目。我下载了这些RDF，解析出项目数据，将其组织为数据库表，并提供基本的数据可视化处理。对于本书，我们可使用这个数据回答关于哪些项目标签在FLOSS项目中最经常同时出现的问题。为此，我们将从项目标签中找出频繁项集，并生成后续的关联规则。频繁项集将采用{GPL, Linux, C}这样的形式。关联规则的样板形如：GPL, Linux -> C [s=.60, c=.90, av=.15]。

首先，登录MySQL服务器，选择本项目使用的数据库（我的是test），创建一个数据库表，保存项目的主列表及标签：

 

在这个数据集中，每个项目由Freecode网站提供的一个数字和将项目添加到目录中的人指定的一个标签列表标识。例如，编号为8的项目有标签GPL、多媒体和语音/音频标签。

要填入这个表的内容，可以使用本书GitHub网站（https://github.com/megansquire/mastering DM）上的数据文件，具体文件在chapter 2目录中：https://github.com/megansquire/ mastering DM/blob/master/ch2/fc_project_tags.sql.gz。

为了在命令行上将这些数据加载到MySQL数据库中，将该文件解压到你的工作目录，然后登录MySQL服务器，使用正确的数据库，发出source命令运行所有INSERT命令。过程如下：

 

在本章的项目中，每个项目仅由其编号标识。但是，如果你想要找出单独项目的更多相关细节，或者将这些数据用于另一个项目，所有Freshmeat/Freecode数据都可以从FLOSSmole网站上的如下目录免费访问：http://flossdata.syr.edu/data/fc/。我们用于本章的数据来自2014年3月，在FLOSSmole系统中，该数据集编号为8079。为简单起见，本章的例子不使用该编号。

为了回答前面的问题（哪些标签最经常同时被发现？），我们需要先对数据稍作研究。首先，可以计算项目标签组合的总数，注意，一个项目可能有多个标签：

 

接下来，可以计算项目的总数。按照相关规则的术语，可以将Freecode项目视为购物篮或者交易，每个项目标签等价于购物篮中的一件商品：

 

数据集中有多少个唯一的项目？

 

这样，有46 510个篮子，11 006件商品。为减少可能的相关规则数量，可以计算含有每个标签的项目有多少个（包含各个产品的篮子有多少个），并删除非常罕见的标签。下表展示了达到每个可能支持阈值所需的项目数：

标签支持率  需要的项目数

50%     23 255

40%     18 604

30%     13 953

10%     4651

5%      2325

 

例如，使用5%的阈值，我们可以将可能的项集从11 006降低为29个。精简后的标签集将成为单例。所有频繁出现的二元组将以这些单例为基础，三元组将从二元组构建。下面是生成单例列表、保持5%最小支持阈值的SQL：

 

下表列出了前几个结果：

标 签 名 称 项 目 数 量

GPL 21 182

POSIX 16 875

Linux    16 288

C   10 292

OS Independent      10 180

 

程序代码可以在本书的GitHub存储库上找到（https://github.com/megansquire/mastering DM/tree/master/ch2），这段程序计算篮子数量，然后使用最小支持阈值找出单例，代码如下。MINSUPPORTPCT是可以任意设置的常数，开始时设置为5：

 

 

 

接下来，计算篮子数量—数据库表中的项目数：

 

使用篮子数和前面设置的最小支持阈值，可以计算篮子的最小数量：

 

现在，可以得到一组符合最小支持阈值的标签：

 

接下来，使用频繁的单例创建候选二元组。将这一任务封装在find Doubletons()函数中。稍后，我们将讨论findDoubletons()、findTripletons()和generate Rules()函数。程序的最后一行在完成工作时关闭数据库连接：

 

正如已经讨论过的，前面在概述Apriori策略时讲过，预先用所有可能的候选二元组填写数据库，然后对其进行计数是不切实际的，因为可能的配对太多了。相反，我们在内存中生成候选二元组，计算其支持阈值，仅保留满足支持阈值条件的二元组。正如前面的单例计数，二元组和三元组的阈值都保持为5%（2325个项目），使用常数MINSUPPORT保存这个支持值。此外，依赖itertools.combinations()函数，从allSingletonTags列表中生成所有size=2的可能组合。最后，将这些频繁出现的标签添加到新列表allDoubletonTags中，将在下面的findTripletons()函数中使用这个列表：

 

 

程序将二元组（以及之后的三元组）写入两个新的数据库表，如果你不想这么做，可以删除INSERT语句。这两个表的CREATE语句在下面的代码中显示。这些SQL语句可以在additionalQueries.sql文件中找到，该文件可以从前面提到的本书GitHub网站上下载：

 

 

得到二元组列表之后，该程序使用列表找出候选三元组。findTripletons()函数与findDoubletons()函数类似，但是我们必须考虑闭包属性。意思是，我们不能生成其中的二元组本身不频繁出现的任何候选三元组。正如findDoubletons()函数结束之前那样，创建所有二元组的列表（doubletonList），现在我们用enumerate()函数获得候选三元组中的所有可能二元组，如果那些二元组不都在频繁二元组列表中，就可以拒绝该三元组。

这似乎有些混乱，所以举个例子来说明。假定已经生成了如下频繁二元组：

 

如果简单地使用列表中的所有项目创建一个候选三元组{foo, bar, baz}，则该三元组就是无效的，因为它包含了非频繁二元组{foo,baz}。因此，只能生成其中所有可能二元组都频繁出现的三元组。找出三元组的代码如下：

 

 

 

在Freecode数据集上运行时，程序生成了37个二元组，下表按支持度从高到低列出了这些二元组：

标签1   标签2   项　目　数

得到这些频繁项集之后，就可以开始从中设计关联规则，为每条规则指定支持度和置信度了。下面是从三元组中生成规则的例程代码。首先生成右侧有单一项目的规则，这是根据和生成频繁项集时相同的闭包属性。换言之，如果{香草威化，香蕉->棉花糖}这样的规则不令人感兴趣，那么计量其他右侧有棉花糖存在的选项（如{香草威化->香蕉，棉花糖}就毫无意义。

最后，这段代码还打印每条规则的附加值得分，这是通过从整条规则的置信度中减去右侧项支持值计算的：

 

 

 

从上述代码生成的Freecode规则如下所示。因为每个三元组可能生成3条规则，因此每条的右侧都有单一项目。为了显示的目的，我们将此分为包含3行的组：

 

 

 

根据上述结果，我们如何知道哪些规则是有意义的？只观察支持值并不能得到特别有意义的线索，因为我们规定所考虑的每条规则至少必须有5%的支持度。

置信度与支持度的组合可能是有趣的计量手段。例如，规则{GPL , Linux -> POSIX}的支持度最高（16%）且置信度超过90%。相反，规则{Linux , POSIX -> C++}的支持度刚好超过阈值（6%）且置信度最低（22%）。

附加值告诉我们，关联规则在预测方程右侧上与简单地观察右侧本身相比有多大的优势。这组规则没有任何直接负相关的项目，但是有几条规则极其接近于0，这表明仅使用右侧的效果与将其作为规则一部分相同。举个例子，{Internet , Web -> GPL}的附加值非常低，这表明仅使用GPL可能起到相同的效果，因为它作为单一项时的得分非常高。规则{Linux , POSIX -> C++}也属于附加值很低的类别，是列表中第二低的。加上非常低的支持度和置信度得分，使这条规则成为列表上价值最低的规则。

附加值得分较高的规则包括{Dynamic Content , Internet -> Web}和{Dynamic Content , Web -> Internet}。这两条规则特别有趣，因为分组中的第三条规则{Internet, Web -> Dynamic Content}的附加值（0.53）很平常。接下来我们注意到，列表中最高附加值的规则的右侧都有Web或者Internet，而另一个项目则出现在左侧的某个地方。这说明Web和Internet是本数据集中联系非常紧密的项目，它们对其他项目的预测能力不如相互预测的能力。

发现这种关系，意味着我们可以更深入地探究Web和Internet之间的关系。确切地说，我们应该关注规则Web -> Internet和 Internet -> Web。由于我们在数据库中保存了支持计数，因此可以使用SQL查询找出这两条规则的支持度、置信度和附加值：

 

上述SQL将得到如下结果：

 

上述SQL代码看起来很吓人，所以这里用一个小的Python脚本对数据库运行每个单独查询，使用得到的数值计算支持度、置信度和附加值。和以前一样，填写数据库连接细节，并将想要比较的两个术语填入常量X和Y中：

 

 

 

对于Internet和Web这两个术语，结果和前面较长的SQL查询一样：

 

这些结果似乎没有给人留下太深刻的印象—毕竟，Internet和Web紧密相关并不是特别令人震惊的事情。但是，我们从这一过程中得到了一些重要的教训。首先，结果可用于提出建议，如果有人为项目打上标签“Web”，我们可能也想建议用“Internet”作为相关的标签。此外，我们可能也想向关注Internet项目的人们交叉推销Web项目，反之亦然。和在商店中将商品放置在同一位置不同，在数字化环境中作出推荐或者建议的代价没有那么高。在任何情况下，找出频繁项集并生成关联规则都是有用的工作，其可以确认我们对数据产生的怀疑，或者帮助我们理解数据中的底层模式，而用其他手段不一定能发现这种模式。