关联规则分析（association rule analysis）是一个普遍用于挖掘商业数据的工具。其目标是在数据中找到一组变量 $X=(X_1,X_2,\dots,X_p)$ 最频繁出现的联合取值。最普遍的应用是在二元取值变量 $X_j\in\{0,1\}$ 的场景中，也被称为购物篮分析（market basket analysis）。在这个场景中，观测样本为销售交易记录，比如在某个商店收银台发生的那些交易。样本 $i$ 中每个变量 $X_j$ 有两个取值；如果这个交易中购买了物品 $j$ 则 $x_{ij}=1$，如果没有购买则 $x_{ij}=0$。频繁地同时取值为一的那些变量就代表了被频繁地同时购买的物品。这些信息对货架摆放、促销中的交叉营销（cross marketing）、商品目录设计、以及根据购买模式的用户分层都很有帮助。
更一般性地来说，关联规则分析的基本目标是为一个特征向量 $X$ 寻找一组典型的取值（$v_1$、……、$v_L$），从而使得在那些取值点处的概率密度 $\operatorname{Pr}(v_l)$ 相对较大。在这个一般性框架中，这个问题可看作为“众数搜寻”（mode finding）或“凸块搜寻”（bump hunting）。通过这样的表述后，发现这个问题很难解决。每个 $\operatorname{Pr}(v_l)$ 自然的估计量是每个 $X=v_l$ 的观测样本比例。当问题中的变量个数稍微大一些，满足 $X=v_l$ 的观测样本个数总是太小从而无法获得可靠的估计。为了使问题易于处理，对分析的目标以及分析可适用数据的一般性都需要进行大幅地简化。
首先对分析目标进行简化。不再寻找 $\operatorname{Pr}(x)$ 较大的取值点 $x$，而是在 $X$ 空间中寻找相对于其大小或支撑集（support）概率比较大的区域。用 $\mathcal{S}_j$ 代表变量 $j$ 所有可能取值的集合（它的支撑集），并用 $s_j\subseteq\mathcal{S}_j$ 代表这些取值的一个子集。简化的目标可表述为寻找一组变量取值的子集 $s_1$、……、$s_p$，使得每个变量同时取值在对应子集中的概率（式 14.2）相对较大。
$$\operatorname{Pr} \left[ \bigcap^{p}_{j=1} (X_j = s_j) \right] \tag{14.2}$$子集的交集 $\cap_{j=1}^p(X_j\in s_j)$ 被称为 合取规则（conjunctive rule）。数值变量的子集 $s_j$ 为连续的区间；分类变量的子集为直接列举出的元素。需要注意通常会出现情况，当子集 $s_j$ 实际上就是所有取值的集合 $s_j=\mathcal{S}_j$ 时，称变量 $X_j$ 没有 出现在 14.2 的合取规则中。
14.2.1 购物篮分析
第 14.2.5 节会介绍求解式 14.2 的一般方法。这些方法在很多应用中都非常有用。然而购物篮分析场景中通常会使用很大的商业数据库（$p\approx10^4$，$N\approx10^8$），这些方法就不再可行了。需要对式 14.2 做进一步的一些简化。首先，只考虑两种子集：$s_j$ 或者只有一个 $X_j$ 的取值，$s_j=\{v_{0j}\}$，或者是 $X_j$ 的所有取值集合，$s_j=\mathcal{S}_j$。这将问题 14.2 简化为寻找一组整数的子集 $\mathcal{J}\subset\{1,\dots,p\}$ 和对应的取值 $v_{0j}$，$j\in\mathcal{J}$，使得式 14.3 取值较大。
$$\operatorname{Pr} \left[ \bigcap_{j \in \mathcal{J}} (X_j = v_{0j}) \right] \tag{14.3}$$图 14.1 演示了这个假设。
可以利用哑变量（dummy variable）将式 14.3 变为一个只涉及二元取值变量的问题。假设每个 $X_j$ 的支撑集 $\mathcal{S}_j$ 是有限集合。具体来说是要创建一组新的变量 $Z_1$、……、$Z_K$，每个变量对应了原变量 $X_1$、……、$X_p$ 中的每个取值 $v_{lj}$。哑变量的个数 $K$ 为：
$$ K = \sum^p_{j=1} | \mathcal{S}_j | $$其中 $|\mathcal{S}_j|$ 代表了 $X_j$ 可能取值的个数。每个哑变量在其对应的变量取值为其对应的值时 $Z_k=1$，否则 $Z_k=0$。这就将式 14.3 转变为寻找一组整数的子集 $\mathcal{K}\subset\{1,\dots,K\}$，使得式 14.4 取值较大。
$$\operatorname{Pr} \left[ \bigcap_{k\in\mathcal{K}} (Z_k = 1) \right] = \operatorname{Pr} \left[ \prod_{k\in\mathcal{K}} Z_k = 1 \right] \tag{14.4}$$这便是购物篮问题的标准表达式。集合 $\mathcal{K}$ 被称为“项集”（item set）。项集中变量 $Z_k$ 的个数被称为项集的大小（size），注意它不能大于 $p$。式 14.4 的估计值为数据集中满足式 14.4 的合取规则的观测样本点的比例：
$$\widehat{\operatorname{Pr}} \left[ \prod_{k \in \mathcal{K}} Z_k = 1 \right] = \frac{1}{N} \sum_{i=1}^N \prod_{k \in \mathcal{K}} z_{ik} \tag{14.5}$$其中的 $z_{ik}$ 为 $Z_k$ 在样本 $i$ 的取值。这被称作项集 $\mathcal{K}$ 的支持度（support）或普遍性（prevalence）$T(\mathcal{K})$。样本 $i$ 若满足 $\pi_{k\in\mathcal{K}}z_{ik}=1$，则被称为包含了（contain）项集 $\mathcal{K}$。
在关联规则挖掘中，会指定一个支持度的下界 $t$，然后在变量 $Z_1$、……、$Z_k$ 组成的项集 $\mathcal{K}_l$ 中寻找所有在数据集的支持度高于下界 $t$ 的项集：
$$\{ \mathcal{K}_l | T(\mathcal{K}_l) > t \}\tag{14.6}$$14.2.2 先验算法
若将阈值 $t$ 调整到使得所有的 $2^K$ 个项集中只有一小部分满足式 14.6，那么在很大的数据集上问题 14.6 的求解在计算上也是可行的。先验（apriori）算法（Agrawal et al., 1995）利用了维数灾难的一些特性，可通过对数据的少量几次遍历计算求解 14.6。具体来说，对于一个给定的阈值 $t$，（利用的特性是）：
- 基数（cardinality）$|\{\mathcal{K}|T(\mathcal{K})>t\}|$ 相对较小。
- 对于项集 $\mathcal{K}$ 的一个子项集 $\mathcal{L}$，它的支持度必然大于等于 $\mathcal{K}$ 的支持度：$\mathcal{L}\subseteq\mathcal{K}\Rightarrow T(\mathcal{L}\geq T(\mathcal{K})$。
第一次对数据的遍历计算每个单项集的支持度。舍弃掉支持度小于阈值的单项集。第二次遍历，用第一次遍历后留存的单个项目两两组成项集，计算所有这些包含两个项目的项集的支持度。也就是说，要生成所有 $|\mathcal{K}|=m$ 的频繁项集，我们只需要考虑来自于大小为 $m-1$ 的频繁项集的那些项集作为备选。（第二次遍历后）舍弃掉支持度小于阈值的两个项目的项集。后续每次对数据的遍历都只考虑由上一次遍历留存下的的项集和第一次遍历留存的单个项目的组合。持续这样的遍历，知道所有备选规则的支持度都小于指定的阈值。对每个 $|\mathcal{K}|$ 的大小，先验算法只需要对数据进行一次遍历；由于我们通常假定所有的数据无法全部读取到计算机的内存中，所以这是个很关键的特性。如果数据足够稀疏（或者阈值 $t$ 足够大），则即使在很大的数据集上这个计算过程也会在一个合理的时间内结束。
此外在这个计算策略中也有其他一些可提升速度和收敛性质的技巧（Agrawal et al., 1995）。先验算法是数据挖掘技术领域中的主要进展之一。先验算法得出的每个高支持度项集 $\mathcal{K}$（14.6）可表达为一组“关联规则”。将其中的项目 $Z_k,k\in\mathcal{K}$ 分隔为两个不相交的子集，$A\cup B=\mathcal{K}$，并记为：
$$A \Rightarrow B \tag{14.7}$$第一个项目子集 $A$ 被称为“先导”（antecedent），第二个子集 $B$ 被称为“后继”（consequent）。根据关联规则的定义，先导和后继项集在数据集上的普遍性（prevalence）会满足一些性质。一个规则 $T(A\Rightarrow B)$ 的支持度（support）为先导和后继项集的并集中的观测样本比例，也就等于它们所构成的项集 $\mathcal{K}$ 的支持度。可将它看作是对在一个随机选择的购物篮中同时观测到两个项集的概率 $\operatorname{Pr}(A\text{ and }B)$ 的一个估计（式 14.5）。这个规则的 置信度（confidence） 或 可预测性（predictability），$C(A\Rightarrow B)$，为它的支持度除以先导的支持度。
$$C(A \Rightarrow B) = \frac{T(A \Rightarrow B)}{T(A)} \tag{14.8}$$这可以看作是对 $\operatorname{Pr}(B|A)$ 的一个估计值。购物篮中出现一个项集 $A$ 的概率 $\operatorname{A}$，可看作是 $\operatorname{Pr}(\prod_{k\in A}Z_k=1)$ 的简写。定义 期望置信度（expected confidence） 为后继的支持度 $T(B)$，也就是对无条件概率 $\operatorname{Pr}(B)$ 的一个估计值。最后，规则的 提升度（lift） 的定义是置信度除以期望置信度：
$$L(A \Rightarrow B) = \frac{C(A \Rightarrow B)}{T(B)}$$这也是对关联测度 $\operatorname{Pr}(A\text{ and }B)/\operatorname{Pr}(A)\operatorname{Pr}(B)$ 的一个估计值。
举个例子，假设项集 $\mathcal{K}=\{\text{花生酱},\text{果酱},\text{面包}\}$，规则为 $\{\text{花生酱},\text{果酱}\}\Rightarrow\{\text{面包}\}$。若这个规则的支持度为 0.03，意味着花生酱、果酱、和面包在 3% 的购物篮中同时出现。若这个规则的置信度为 0.82，意味着在已经购买了花生酱和果酱的情况下，有 82% 的购物篮中也会购买面包。如果有 43% 的购物篮中购买了面包，那么这个规则 $\{\text{花生酱},\text{果酱}\}\Rightarrow\{\text{面包}\}$ 的提升度为 1.95（$0.82/0.43\approx1.95$）。
这个分析的目标是得出支持度和置信度（式 14.8）都比较高的关联规则（式 14.7）。先验算法可得出由支持度阈值 $t$（式 14.6）所控制的所有高支持度项集。再指定一个置信度阈值 $c$，由那些项集（式 14.6）产生规则中，所有置信度高于阈值的规则为：
$$\{A \Rightarrow B | C(A \Rightarrow B) > c\} \tag{14.9}$$对于每个大小为 $|\mathcal{K}|$ 的项集 $\mathcal{K}$，共有 $2^{|\mathcal{K}|-1}-1$ 个形式为 $A\Rightarrow(\mathcal{K}-A),A\subset\mathcal{K}$ 的规则。Agrawal et al. (1995) 介绍了一个先验算法的变体，可以快速地判断出由项集解（式 14.6）中产生的所有可能的规则里面，那些规则可以满足置信度阈值（式 14.9）。
整个分析的结果是一系列满足以下条件的关联规则（式 14.7）：
$$T(A \Rightarrow B) > t \text{ and } C(A \Rightarrow B) > c$$这些结果一般会被保存到用户可以查询的数据库中。用户通常可能会要求将这些规则按置信度、提升度、或支持度的排序进行展示。更具体地，用户可能想要一个条件于在先导中、或（特别是）后继中存在某个特定项目的规则列表。举一个可能的需求例子：
展示出所有后继项集中存在滑冰鞋、置信度高于 80%、并且支持度高于 2% 的所有交易。
这为可预测滑冰鞋销售的那些项目（先导）提供了些信息。若是聚焦于特定一个后继中的项目，那么问题就可转入监督学习的框架。
在购物篮相关的场景中，关联规则已经成为分析大型商业数据库的一个流行的工具。当数据可被转化成多维列联表（contingency table）的形式，即可适用购物篮分析。分析的结果是合取规则（式 14.4）的形式，易于理解和解释。先验算法可以使这个分析可应用于大型的数据库上，而其他类型的分析则难以适用于这么大规模的数据库。关联规则是数据挖掘领域中最成功的技术之一。
除了对可适用的数据形式上的约束外，关联规则也存在其他的局限。支持度阈值（式 14.6）对计算的可行性至关重要。随着这个下界的降低，项集解的数量、项集的大小、和对数据所需要的遍历次数都可能会指数级地增长。所以那些置信度或提升度高但支持度低的规则可能不会被发掘出。例如 $\text{伏特加}\Rightarrow\text{鱼子酱}$ 的规则，置信度可能较高，但由于后继中鱼子酱的销量较低，所以规则可能无法被发掘出。
14.2.3 例：购物篮分析
我们在一个大小适中的人口统计数据库上演示先验算法的应用。数据库中包含了旧金山湾区商场中的顾客填写的 $N=9409$ 个调查问卷（Impact Resource, Inc., Columbus OH, 1987）。这里为了演示仅使用了前 14 个关于人口统计相关问题的回答。表 14.1 中列出了这些问题。这个数据混合了有序变量和（无序）分类变量，其中一些分类变量的取值数量可能比较多。这里也存在缺失值。
| 特征编号 | 人口统计特征 | 取值个数 | 类型 | 变量名 |
|---|---|---|---|---|
| 1 | 性别 | 2 | 分类 | sex |
| 2 | 婚姻状态 | 5 | 分类 | marstat |
| 3 | 年龄 | 5 | 有序 | age |
| 4 | 教育程度 | 5 | 有序 | educ |
| 5 | 职业 | 9 | 分类 | occup |
| 6 | 收入水平 | 9 | 有序 | income |
| 7 | 湾区生活时长 | 5 | 有序 | yrs-bay |
| 8 | 是否双收入家庭 | 3 | 分类 | dualinc |
| 9 | 家庭人数 | 9 | 有序 | perhous |
| 10 | 家庭儿童数 | 9 | 有序 | peryoung |
| 11 | 住房状态 | 3 | 分类 | house |
| 12 | 住房类型 | 5 | 分类 | typehome |
| 13 | 种族分类 | 8 | 分类 | ethnic |
| 14 | 家庭语言 | 3 | 分类 | language |
表 14.1：人口统计数据的输入变量。
我们使用了来自 Christian Borgelt 的一个先验算法的开源实现。1去除了含有缺失值的观测样本后，将每个有序自变量从它的中位数处截断，并编码为两个哑变量；将每个类别数为 $k$ 的分类变量编码为 $k$ 个哑变量。这样处理的结果是一个 $6876\times50$ 的矩阵，共有 6876 个样本和 50 个哑变量。
算法共发掘出了共 6288 个关联规则，涉及到的自变量小于等于 5 个，要求支持度至少为 10%。对这个庞大的规则集合的理解本身就是一个很有挑战的数据分析工作。我们在这里不会进行深入展开，而只在图 14.2 中演示下每个哑变量（上图）和关联规则（下图）在数据中的相对频率。普遍的（prevalent）类别往往会更频繁地出现在规则中，例如家庭语言中最普遍的是英语（English）。不过其他变量频率不高，例如职业变量中只有第一个和第五个取值出现在规则中。
以下为先验算法发掘出的三个示例关联规则：
- 关联规则一：支持度 25%，置信度 99.7%，提升度 1.03。 $$\begin{bmatrix} \text{家庭人数} &=& 1 \\ \text{家庭儿童数} &=& 0 \end{bmatrix} \Rightarrow \text{家庭语言} = \text{英语}$$
- 关联规则二：支持度 13.4%，置信度 80.8%，提升度 2.13。 $$\begin{bmatrix} \text{家庭语言} &=& \text{英语} \\ \text{住房状态} &=& \text{所有} \\ \text{职业} &=& \{ \text{专家} / \text{管理} \} \end{bmatrix} \Rightarrow \text{收入水平} \geq \text{\$40,000}$$
- 关联规则三：支持度 26.5%，置信度 82.8%，提升度 2.15。 $$\begin{bmatrix} \text{家庭语言} &=& \text{英语} \\ \text{收入水平} &<& \text{\$40,000} \\ \text{婚姻状态} &=& \text{未婚} \\ \text{家庭儿童数} &=& 0 \end{bmatrix} \Rightarrow \text{教育程度} \notin \{ \text{大学毕业}, \text{研究生} \}$$
第一个和第三个规则是由于它们的高支持度而被选中。第二个规则是有高收入后继的关联规则，可能会被用于定位高收入的目标个体。
如之前所述，我们为每个分类变量的类别创建了哑变量，例如 $Z_1=I(\text{收入水平}<\text{\$40,000})$ 以及 $Z_2=I(\text{收入水平}\geq\text{\$40,000})$ 分别代表了低于和高于收入中位数。如果我们只对高收入类别中的关联规则有兴趣，那么可以只包含 $Z_2$ 而排除 $Z_1$。在实际的购物篮分析问题中这样的情景很常见，我们感兴趣的是发掘某个相对稀少项目存在时的关联规则，而不是缺失时的关联规则。
14.2.4 无监督问题使用监督学习方法
这里我们将介绍一个将概率密度估计问题转化为一个有监督的函数估计问题。这也是组成下一节中一般关联规则的基础。
令 $g(x)$ 为待估计的未知概率密度函数，$g_0(X)$ 为作为参考的一个特定的概率密度函数。例如，$g_0(x)$ 可能为变量取值范围上的均匀密度函数。之后会介绍其他可能的密度函数。数据集 $x_1$、$x_2$、……、$x_N$ 假设为从 $g(x)$ 独立同分布抽样得到的随机样本。同时可以通过蒙特卡罗（Monte Carlo）方法从 $g_0(x)$ 抽取大小为 $N_0$ 的一个样本。将这两个数据集合并到一起，为从 $g(x)$ 抽样的那些样本赋权重 $w=N_0/(N+N_0)$，为从 $g_0(x)$ 抽样的那些样本赋权重 $w_0=N/(N+N_0)$，结果会是一个从混合密度函数 $(g(x)+g_0(x))/2$ 的随机抽样。如果定义从 $g(x)$ 抽样的样本点取值为 $Y=1$，而从 $g_0(x)$ 抽样的样本点取值为 $Y=0$，
$$\begin{align} \mu(x) = \operatorname{E}(Y|x) &= \frac{g(x)}{g(x) + g_0(x)} \\ &= \frac{g(x)/g_0(x)}{1 + g(x)/g_0(x)} \tag{14.10}\end{align}$$那么上式的条件期望可用合并后样本作为训练集的监督学习进行估计。
$$(y_1, x_1), (y_2, x_2), \dots, (y_{N+N_0, x_{N+N_0}}) \tag{14.11}$$估计结果 $\hat{\mu}(x)$ 可转化成为对 $g(x)$ 的一个估计：
$$\hat{g}(x) = g_0(x) \frac{\hat{\mu}(x)}{1-\hat{\mu}(x)} \tag{14.12}$$广义版本的对数几率回归（第 4.4 节）特别地适用于这个场景中，因为它会直接地对下式的对数几率进行估计。
$$f(x) = \log \frac{g(x)}{g_0(x)} \tag{14.13}$$在这个场景中，有下式的关系：
$$\hat{g}(x) = g_0(x) e^{\hat{f}(x)} \tag{14.14}$$
图 14.3 展示了一个示例。左图中展示的是我们生成的一个 200 个样本的训练集。右图中展示的是在包含了训练集范围的方形区域上均匀分布的参考数据点（蓝色点）。训练样本被标记为类别 1，参考样本被标记为类别 0，然后通过使用了自然样条张量积（第 5.2.1 节）的对数几率回归模型来拟合数据。右图中也展示了一些 $\mu(x)$ 的概率等高线；由于 $\hat{g}(x)=\hat{\mu}(x)/(1-\hat{\mu}(x))$ 是一个单调函数，所以这些也是概率密度估计 $\hat{g}(x)$ 的等高线。这些等高线大致地显示出了数据的概率密度。
原则上任意的参考概率密度都可被用作式 14.14 中的 $g_0(x)$。在实践中，$\hat{g}(x)$ 估计的准确性可能极大地取决于特定（$g_0(x)$）的选择。而好的选择会依赖于数据的概率密度函数 $g(x)$ 和用于估计式 14.10 与 14.13 的具体方法。如果是以准确性为目标，那么 $g_0(x)$ 的选择应该是能够使得所生成的函数 $\mu(x)$ 或 $f(x)$ 易于被所使用的方法进行估计。不过准确性不一定总是第一目标。$\mu(x)$ 和 $f(x)$ 都是概率密度比率 $g(x)/g_0(x)$ 的单调函数。因此它们也可被看成是一种“对比”统计量，表现了数据的概率密度 $g(x)$ 与所选的参考概率密度 $g_0(x)$ 的偏离程度。所以在数据分析的场景中，$g_0(x)$ 的选择通常取决于具体问题的背景下最关注（概率分布）偏离的类型。例如，如果关注的是与均匀性质的偏离，那么 $g_0(x)$ 可以是变量取值范围上的一个均匀分布概率密度函数。如果关注的是与联合正态性质的偏离，那么 $g_0(x)$ 可以是以数据样本均值和协方差为参数的高斯分布概率密度函数。与独立性的偏离可以用下式作为参考概率密度：
$$g_0(x) = \prod_{j=1}^p g_j(x_j) \tag{14.15}$$其中 $g_j(x_j)$ 为 $X$ 中的第 $j$ 个变量 $X_j$ 的边际密度函数。对数据样本中输入变量的取值进行随机组合（permutation），就可以很容易地从数据中生成一个服从式 14.15 的独立密度函数的随机抽样。
如上所述，无监督学习关注的是寻找数据中概率密度 $g(x)$ 的性质。每个方法会聚焦于一个或一组特定的性质。虽然将（无监督）问题转化为一个监督学习问题的方法（式 14.10～14.14）可能在统计学的圈子内（statistics folklore）讨论了很长时间了，而且即使它有可能将发展成熟的监督学习方法引入到无监督学习的问题中，但它好像从未产生什么影响。一个可能的原因是必须要通过蒙特卡洛方法模拟来扩大数据集。由于这个模拟的数据集应该至少要大于数据样本集 $N_0\geq N$，估计计算过程对计算和内存的要求会至少增加一倍。而同时，生成蒙特卡洛样本的计算量本身可能就会比较大。尽管这在过去可能是一个不小的障碍，但随着计算资源越来越丰裕，这些额外的计算需求已经变得没有那么难以承担了。在下一节我们将演示将监督学习方法应用在无监督学习中。
14.2.5 一般关联规则
在数据空间中寻找高概率密度的区域的更一般性的问题（式 14.2），可以通过上述的监督学习方法来解决。 即便这在购物篮分析所适用的大型数据库上不可用，但在中型数据集上可以得到一些有用的信息。 问题（式 14.2）可以被表述为寻找一个整数集的子集 $\mathcal{J}\subset\{1,2,\dots,p\}$，以及对应变量 $X_j$ 的对应取值子集 $s_j,j\in\mathcal{J}$，使得下式的取值较大：
$$\widehat{\operatorname{Pr}} \left( \bigcap_{j \in \mathcal{J}} (X_j \in s_j) \right) = \frac{1}{N} \sum_{i=1}^N I \left( \bigcap_{j \in \mathcal{J}} (x_{ij} \in s_j) \right) \tag{14.16}$$按照关联规则分析的命名方法，$\{(X_j\in s_j)\}_{j\in\mathcal{J}}$ 被称为一个“广义“项集。数值变量对应的子集 $s_j$ 为变量取值范围上的连续区间，分类变量对应的子集中可以包含多个取值。对这个问题激进又宏大2的定义方式，就排除了对所有支持度（式 14.16）大于一个预设最小阈值的所有广义项集全面搜寻的可能性，而这在约束性更强的购物篮分析中这是可行的。所以必须要适用启发式（heuristic）搜索方法，而且希望搜索得出的这些广义项集是有意义的。
购物篮分析（式 14.5）和它的广义定义方式（式 14.16）都隐含地参考了均匀概率分布。所要寻找的项集的出现频率，高于当所有的联合数据取值 $(x_1,x_2,\dots,x_N)$ 为均匀分布时的预期频率。这样就会更倾向于发现那些所包含项目（$X_j\in s_j$）各自都频繁出现的项集，也就是下式的取值较大：
$$\frac{1}{N} \sum_{i=1}^N I(x_{ij} \in s_j)\tag{14.17}$$在高支持度的项集（式 14.16）中，高频率子集（14.17）的合取（conjunction）要比低频率子集的合取更经常出现。这就是规则 $\text{伏特加}\Rightarrow\text{鱼子酱}$ 即使是个高关联（提升度高），但也不太可能被发掘出的原因；其中的两个项目的编辑支持度都不高，所以它们的联合支持度更低。以均匀分布作为参考可能会导致在高支持度项集的列表中，大部分都是高频率但成分之间关联程度低的项集。
高频率子集 $s_j$ 是从最高频的 $X_j$ 取值中分离出的。若使用变量的边际样本概率密度的乘积（式 14.15）作为参考概率分布，可去除在发掘出的项集中对单个变量中高频率取值的偏向。这是因为若在变量中不存在关联性（完全独立），则不管单个变量取值的频率分布如何，概率密度比率 $g(x)/g_0(x)$ 是均匀分布的。类似 $\text{伏特加}\Rightarrow\text{鱼子酱}$ 这样的规则就有机会被发掘出。不过尚不清除如何在先验算法中使用不同于均匀分布的参考概率分布。但如在第 14.2.4 节所述，在给定了原始数据集后，从乘积概率密度（式 14.15）生成一个样本是比较容易的。
选定了一个参考概率分布，并且从中抽取一个如式 14.11 的样本后，就得到了一个二元取值数处变量 $Y\in\{0,1\}$ 的监督学习问题。问题的目标是通过训练集数据，寻找到这样的区域：
$$R = \bigcap_{j \in \mathcal{J}} (X_j \in s_j) \tag{14.18}$$使得目标函数 $\mu(x)=\operatorname{E}(Y|x)$ 相对较大。另外，也需要要求这些区域的样本支持度（下式）不要太小。
$$T(R) = \int_{x \in R} g(x) dx \tag{14.19}$$14.2.6 监督学习方法的选择
式 14.18 的区域被合取规则所定义。因此也应选择在这个背景下最恰当的监督学习方法来学习这些规则。CART 决策数的终节点的定义规则与式 14.18 的形式完全一致。在合并的数据（式 14.11）上应用 CART 模型可以得出一个决策树，它会将整体数据集分成一组不相交的区域（终节点）来对目标函数（式 14.10）进行预测。每个区域都可用式 14.18 形式的规则定义。那些平均 $y$ 值（下式）较高的终节点 $t$ 就是高支持度的一般项集（式 14.16）的备选集合。
$$\bar{y}_t = \operatorname{ave}(y_i | x_i \in t)$$实际的样本支持度为：
$$T(R) = \bar{y}_t \cdot \frac{N_t}{N + N_0}$$其中 $N_t$ 为（合并的）样本数据在终节点代表的区域中的数量。在得出的决策树中，就可以发掘出所关注的相对高支持度的一般项集。然后可以将这些项集划分出先导和后继，搜寻出高置信度和（或）高提升度的一般关联规则。
另一个自然地适用于此的学习方法是第 9.3 节介绍的耐心规则归纳方法（patient rule induction method，PRIM）。PRIM 也会产生与式 14.18 形式完全一致的规则，但它是专门设计用于寻找在区域内最大化平均目标函数（式 14.10）取值的高支持度区间，而不是在整体样本空间上对目标函数的预测。它也对支持度与平均目标函数取值之间的权衡提供了更多控制。
练习 14.3 介绍当我们从边际概率分布的乘积中生成随机样本时，这两个方法都会遇到的一个问题。
14.2.7 例：购物篮分析（续）
本节用表 14.1 中的人口统计数据来演示 PRIM 的应用。
从 PRIM 分析中发掘出的三个高支持度的一般项集如下：
- 项集一：支持度 24%。 $$\begin{bmatrix} \text{婚姻状态} &=& \text{已婚} \\ \text{住房状态} &=& \text{所有} \\ \text{住房类型} &\neq& \text{公寓} \end{bmatrix}$$
- 项集二：支持度 24%。 $$\begin{bmatrix} \text{年龄} &\leq& 24 \\ \text{婚姻状态} &\in& \{ \text{未婚同居}, \text{单身} \} \\ \text{职业} &\notin& \{ \text{专家}, \text{建筑}, \text{退休} \} \\ \text{住房状态} &\in& \{ \text{租房}, \text{住父母家} \} \end{bmatrix}$$
- 项集三：支持度 15%。 $$\begin{bmatrix} \text{住房状态} &=& \text{租房} \\ \text{住房类型} &\neq& \text{独栋} \\ \text{家庭人数} &\leq& 2 \\ \text{家庭儿童数} &=& 0 \\ \text{职业} &\notin& \{ \text{建筑}, \text{学生}, \text{未就业} \} \\ \text{收入水平} &\in& [\text{\$20000}, \text{\$150000}] \end{bmatrix}$$
从这些项集中推导出的置信度（式 14.8）高于 95% 的一般关联规则如下：
- 关联规则一：支持度 25%，置信度 99.7%，提升度 1.35。 $$\begin{bmatrix} \text{婚姻状态} &=& \text{已婚} \\ \text{住房状态} &=& \text{所有} \end{bmatrix} \Rightarrow \text{住房类型} \neq \text{公寓}$$
- 关联规则二：支持度 25%，置信度 98.7%，提升度 1.97。 $$\begin{bmatrix} \text{年龄} &\leq& 24 \\ \text{职业} &\notin& \{ \text{专家}, \text{建筑}, \text{退休} \} \\ \text{住房状态} &\in& \{ \text{租房}, \text{住父母家} \} \end{bmatrix} \Rightarrow \text{婚姻状态} \in \{ \text{单身}, \text{未婚同居} \}$$
- 关联规则三：支持度 25%，置信度 95.9%，提升度 2.61。 $$\begin{bmatrix} \text{住房状态} &=& \text{所有} \\ \text{住房类型} &\neq& \text{公寓} \end{bmatrix} \Rightarrow \text{婚姻状态} = \text{已婚}$$
- 关联规则四：支持度 15%，置信度 95.4%，提升度 1.50。 $$\begin{bmatrix} \text{住房状态} &=& \text{租房} \\ \text{住房类型} &\neq& \text{独栋} \\ \text{家庭人数} &\leq& 2 \\ \text{职业} &\notin& \{ \text{建筑}, \text{学生}, \text{未就业} \} \\ \text{收入水平} &\in& [\text{\$20000}, \text{\$150000}] \\ \end{bmatrix} \Rightarrow \text{家庭儿童数} = 0$$
这些规则中没有什么出奇的发现。它们很大程度上是对直觉的验证。在其他先验信息不多的场景中，更可能会发掘出一些出乎意料的结果。这些结果演示了一般关联规则可提供的信息，以及转化监督学习的方法和例如 CART 和 PRIM 的规则归纳方法可发掘出包含高关联度成分的项集。
那么这些一般关联规则与之前那些从先验算法发掘出的关联规则有什么区别？先验算法会给出上千个规则，所以不太容易对它们进行比较。不过有几个一般性的区别点。先验算法是穷尽的，它会搜寻出所有支持度高于某个预设值的规则。而与之相比，PRIM 是一个贪心算法而并不会保证得出“最优”的一组规则。另外先验算法只能处理哑变量，所以无法找出上面的那些规则。例如，因为“居住类型”是一个分类变量，每个类别对应一个哑变量，所以先验算法无法得出含有下面这个集合的规则：
$$\text{住房类型} \neq \text{公寓}$$要想获得这个集合（的规则），就需要为“公寓”和“其他类型”的居住类型编码一个哑变量。为所有这些潜在的对比预编码哑变量，一般来说是不太可行的。
本节练习
练习 14.3
第 14.2.6 节 讨论了使用 CART 或 PRIM 来构建一般关联规则。请说明在从边际概率分布的乘积生成随机数据样本时，即对每个变量的样本取值进行随机排列，这两个方法都会出现的一个问题。请找出一个解决这个问题的方法。
练习 14.4
用分类树模型对表 14.1 中的人口统计数据进行分类。具体来说，先通过对每个特征变量取值的随机排列，生成一个与训练集一样大小的参考样本。在训练样本（类别 1）和参考样本（类别 0）上构建一个分类树模型，并描述其中类别 1 的估计概率最高的终节点。将结果与在同样数据上 PRIM 的结果和 K 均值聚类的结果进行比较。