12.计算题知识点

1. 支持度/置信度/提升度

1.1. 基础概念

1. 支持度（Support）：同时包含A和B的事务所占有事务的比例：

   $Support = P (A \cap B)$

2. 置信度（Conficence）：表示使用包含A事务中同时包含B的比例

   $Confidence = P (A \cap B) / P(A)$

3. Lift提升度：“包含A事务中同时包含B的比例”和“包含B事务中比例”的比值

   $Lift = P (A \cap B) / P(A) / P(B)$

注意：上边三个指标在定义的时候有一个方向问题，描述的是A -> B的方向，支持度的计算是直接计算，无关方向，但置信度和提升度的计算的分母部分则关联到方向问题。

1.2. 「例」

1.2.1. 计算参数

事务ID	购买项集
1	A,B,C
2	A,C
3	A,D
4	B,E,F

    计算A -> C的各个参数：

1. 支持度：

   $A = \frac{3}{4} = 0.75$ $C = \frac{1}{2} = 0.5$ $Support = P (A \cap B) = 0.5 = 50\%$

   备注：此处的 $\cap$ 运算是取交集，即最大公约概率，并非使用乘法的方式将两个概率相乘。

2. 置信度：

   $P ( A \cap B ) = 0.5$ $P (A) = 0.75$ $Confidence = P ( A \cap B ) / P(A) = 0.5 / 0.75 = 0.66 = 66\%$ $Confidence = Support / P(A)$

   运算细节：$0.5 / 0.75 = \frac{1}{2} \times \frac{4}{3} = \frac{2}{3} \approx 0.66$

3. 提升度：

   $P ( A \cap B ) = 0.5$ $P (A) = 0.75$$P (B) = 0.5$$Lift = P( A \cap B) / P(A) / P(B) = 0.5 / 0.75 / 0.5 = 4/3 = 1.33 = 133\%$$Lift = Conficence / P(B)$

2. 杰卡德Jaccard

2.1. 基本概念

    A contingency table for binary variables:

	Object j
	1	0	Sum
Object i	1	q	r	q + r
...	0	s	t	s + t
...	Sum	q + s	r + t	p

1. 杰卡德相似系数：

   $J(A,B) = \frac{|A \cap B|}{|A \cup B|} = \frac{q}{q + r + s}$
2. 杰卡德距离：

   $J = 1 - J(A,B) = \frac{|A \cup B| - |A \cap B|}{|A \cup B|} = \frac{r + s}{q + r + s}$

    杰卡德的应用场景：

• 相似度很高的新闻（网页去重）

• 考试防作弊系统

• 论文查重系统

• 对象距离计算、聚类

    在聚类（Clustering）问题中，如果数据字段属性都是二元属性（Binary Variable），根据上述表，Jaccard Coefficient计算数据间的距离公式为：

$d(i,j) = (r + s) / (q + r + s)$

3. 频繁项计算

3.1. 基本概念

    项的集合称为项集，包含k个项的项集称为k-项集，项集的出项频率是包含项集的事务数，简称为项集的事务集，支持度计数或计数。注意，定义项集的支持度有时称为相对支持度，而出现的频率称为绝对支持度。如果项集I的相对支持度满足预定义的最小支持度阈值，则I是频繁项集。

• 置信度——是指某个关联规则的概率，可以用P(B|A)表示。

• 关联规则——表示的是在某个频繁项集的条件下推出另一个频繁项集的频率，如果该关联规则的置信度大于等于最小置信度，则为强关联规则。

• 闭频繁项集（Closed Frequent Itemset）——当项集X是频繁项集，且数据集D中不存在X的真超集Y，是的X和Y的支持度相等，则X就是闭频繁项集。闭频繁项集的表示是无损压缩，不会丢失支持度的信息。通过闭频繁项集可以反推出所有的频繁项集以及相应的支持度。

• 极大频繁项集（Maximal Frequent Itemset）——当项集X是频繁项集，且数据集D中不存在X的真超集，使得Y是频繁项集，则X是极大频繁项集。极大频繁项集的表示是有损压缩，失去了频繁项集的支持度信息，我们可以根据极大频繁项集判断任意项集是否频繁的，但无法得到相应的支持度。

• 最大规则对象数——规则中对象组所包含的最大对象数量。

• 最小支持——规则中对象或是对象组必须匹配的最低案例数。

• 最小信心水准——计算规则所必须匹配的最低信心水准门槛。

3.2. 「例」

3.2.1. 基本计算

    考虑下面的频繁3-项的集合：

• {1,2,3}

• {1,2,4}

• {1,2,5}

• {1,3,4}

• {1,3,5}

• {1,4,5}

• {2,3,4}

• {2,3,5}

• {3,4,5}

    假定数据集中只有5个项，采用合并策略，由候选产生过程中得到的4-项集不包括：

• A.1,2,3,4

• B.1,2,3,5

• C.1,2,4,5

• D.1,3,4,5

    验证每个结果如下：

选项	根据结果提取所需的三项集
1,2,3,4	123, 124, 234, 134
1,2,3,5	123, 125, 235, 135
1,2,4,5	125, 125, 245（该项不存在于于3-项集）, 145
1,3,4,5	134, 135, 345, 145

3.2.2. Apriori算法

    根据Apriori算法回答下边问题：

TID	项集
1	面包、牛奶
2	面包、尿布、啤酒、鸡蛋
3	牛奶、尿布、啤酒、可乐
4	面包、牛奶、尿布、啤酒
5	面包、牛奶、尿布、可乐

    利用Apriori算法计算频繁项集可以有效降低计算频繁项集的时间复杂度，上述购物篮中产生支持度不小于3的候选3-项集，在候选2-项集中需要剪枝的是

• A.啤酒、尿布

• B.啤酒、面包

• C.面包、尿布

• D.啤酒、牛奶

    详细解析，根据频繁项集执行计算

用户	面包 A	牛奶 B	尿布 C	啤酒 D	鸡蛋 E	可乐 F
1	v	v
2	v	v	v	v
3	v	v	v	v
4	v	v	v	v
5	v	v	v		v

支持度 >= 3

    从1-项集开始计算：

• 1项：

  • 项集：{A,B,C,D,E,F}

  • 剪枝移除得到频繁项集：{A,B,C,D}

• 2项：

  • 项集：{(A,B), (B,C), (C,D), (A,C), (A,D), (B,D)}

  • 剪枝移除得到频繁项集：{(A,B), (B,C), (C,D), (A,C)}

    验证结果

• A. {C, D}

• B. {A, D} - 剪枝移除

• C. {A, C}

• D. {B, D} - 剪枝移除

3.2.3. 频繁闭项集

    下表是一个购物篮，假定支持度阈值为40%，其中（ ）是频繁闭项集

• abc

• abcd

• bce

• acde

• de

• A.abc

• B.ad

• C.cd

• D.de

    详细解析：

答案	项集	直接超集	间接超集
A	abc = 40%	abcd = 20%
B	ad = 40%	acd = 40%	abcd, acde
C	cd = 40%	acd = 40%, cde = 20%	abcd, acde
D	de = 40%	cde = 20%	acde

根据统计结果可以知道，只有A和D满足频繁闭项集的条件，B和C中acd = 40%使得这两个项集不可能成为频繁闭项集，直接超集的占比和当前频繁项集的占比一样则表示该集合不是频繁闭项集，如结果中ad和acd都是40%，那么这种场景下，ad就不是频繁闭项集。

4. Gini Index计算

4.1. 基本概念

    在决策树的CART算法中划分决策树的条件是使用Gini Index，该定义如下（标识数据集的纯度）：

$Gini(D) = 1 - \sum_{j=1}^n p_j^2$

    直观来说，数据集的基尼系数反应了从数据集D中随机抽取两个样本，其类别不一样的概率，于是Gini系数越小证明数据集纯度越高。

4.2.「例」

4.2.1. Gini计算

    给定以下的便利店选点数据集，并采用CART的分类树算法构建分类树（目标字段为最后一个字段）时，请回答以下题目：

1. 当左子树是道路距离<=30，右子树是道路距离31~40或>40时，请计算此树的Gini值为何？

• A.0.335

• B.0.247

• C.0.249

• D.0.394

  计算方法：道路距离

  道路距离	Yes	No	总
  <=30	2	3	5
  31~40, >40	7	2	9

  左Gini：$1 - (\frac{2}{5})^2 - (\frac{3}{5})^2 = 0.48$ 左占比：$\frac{5}{5 + 9} = \frac{5}{14}$ 右Gini：$1 - (\frac{7}{9})^2 - (\frac{2}{9})^2 \approx 0.34568$ 右占比：$\frac{9}{5 + 9} = \frac{9}{14}$ 最终Gini: $0.48 \times \frac{5}{14} + 0.34568 \times \frac{9}{14}$ $\approx 0.17143 + 0.22222$ $\approx 0.394$

1. 当左子树是人口密度=中，右子树是人口密度=高或人口密度=低时，请计此树的Gini值为何？

• A.0.378

• B.0.398

• C.0.102

• D.0.458

  计算方法：人口密度

  人口密度	Yes	No	总
  中	4	2	6
  高、低	5	3	8

  左Gini：$1 - (\frac{4}{6})^2 - (\frac{2}{6})^2 \approx 0.4444$ 左占比：$\frac{6}{6 + 8} = \frac{6}{14}$ 右Gini：$1 - (\frac{5}{8})^2 - (\frac{3}{8})^2 = 0.46875$右占比：$\frac{8}{6 + 8} = \frac{8}{14}$ 最终Gini： $0.4444 \times \frac{6}{14} + 0.46875 \times \frac{8}{14}$ $\approx 0.19047 + 0.26786$ $\approx 0.458$

1. 当子树是区域类别=住宅区，右子树是区域类别=商业区时，请计算此树的Gini值为何？

• A.0.457

• B.0.367

• C.0.459

• D.0.347

  计算方法：区域类型

  区域类型	Yes	No	总
  住宅区	3	4	7
  商业区	6	1	7
  左Gini：$1 - (\frac{3}{7})^2 - (\frac{4}{7})^2 \approx 0.48980$
  左占比：$\frac{7}{7 + 7} = \frac{7}{14}$
  右Gini：$1 - (\frac{6}{7})^2 - (\frac{1}{7})^2 \approx 0.24490$
  右占比：$\frac{7}{7 + 7} = \frac{7}{14}$
  最终Gini：
  $0.48980 \times \frac{7}{14} + 0.24490 \times \frac{7}{14}$
  $\approx 0.2449 + 0.12245$
  $\approx 0.367$

1. 当左子树是捷运车站=有，右子树是捷运车站=没有时，请计算此树的Gini值为何？

• A.0.398

• B.0.489

• C.0.429

• D.0.217

  计算方法：捷运车站

  捷运车站	Yes	No	总
  有	6	2	8
  没	3	3	6
  左Gini：$1 - (\frac{6}{8})^2 - (\frac{2}{8})^2 = 0.375$
  左占比：$\frac{8}{8 + 6} = \frac{8}{14}$
  右Gini：$1 - (\frac{3}{6})^2 - (\frac{3}{6})^2 = 0.5$
  右占比：$\frac{6}{8 + 6} = \frac{6}{14}$
  最终Gini：
  $0.375 \times \frac{8}{14} + 0.5 \times \frac{6}{14}$
  $\approx 0.21429 + 0.21429$
  $\approx 0.429$

5. 贝叶斯公式

5.1. 基本概念

1. 条件概率是事件A在另一个事件B已经发生条件下的发生概率，记作：

   $P(B|A)$
2. 联合概率表示两个事件共同发生的概率，A和B的联合概率记作：

   $P(BA) 或 P(A \cap B)$
3. 先验概率是某个事件的概率，A的先验概率和B的先验概率分别记作：

   $P(A), P(B)$
4. 贝叶斯公式

   $P(A|B) = \frac{P(A \cap B)}{P(B)}$ $P(B|A) = \frac{P(A \cap B)}{P(A)}$ 通过代换得到

   $P(A|B) = \frac{P(B|A) \times P(A)}{P(B)}$ $P(A|B) \times P(B) = P(B|A) \times P(A)$

5.2.「例」

5.2.1. 概率计算

1. 设某公路上经过的火车与客车的数量之比为2：1，货车中途停车修理的概率为0.02，客车为0.01，今有一辆汽车中途停车修理，求该汽车是货车的概率？

• A.0.013

• B.0.80

• C.0.40

• D.0.60

  解析： $P(A_1)$：经过的车是货车的概率：$\frac{2}{3}$ $P(A_2)$：经过的车是客车的概率：$\frac{1}{3}$ $P(B|A_1)$：货车中途停车修理的概率 = 0.02 $P(B|A_2)$：客车中途停车修理的概率 = 0.01 根据上述四个结果，计算： $P(B) = P(A_1) \times P(B|A_1) + P(A_2) \times P(B|A_2)$ $P(A_1|B) = \frac{P(B|A_1) \times P(A_1)}{P(B)} = \frac{P(B|A_1) \times P(A_1)}{P(A_1) \times P(B|A_1) + P(A_2) \times P(B|A_2)}$ $P(A_1|B) = \frac{0.02 \times \frac{2}{3}}{0.02 \times \frac{2}{3} + 0.01 \times \frac{1}{3}} = \frac{4}{5} = 0.8$

6. 混淆矩阵

6.1. 基本概念

6.1.1. 基本参数

1. 正确率

   $Accuracy = \frac{TP + TN}{TN + FN + TP + FP}$ （对角线\）
2. 错误率

   $1 - Accuracy = \frac{FN + FP}{TN + FN + TP + FP}$ （对角线/）
3. 查全率/查准率

   $Precision = \frac{TP}{TP + FP} = P$ （预测正）
4. 查全率/召回率

   $Recall = \frac{TP}{TP + FN} = R$ （真实正）
5. F-指标

   $F-Measure = \frac{2 \times Precision \times Recall}{Precision + Recall} = \frac{2 \times P \times R}{P + R}$
6. 灵敏度

   $Sensitivity = Recall = S$
7. 特异性

   $Specificity = \frac{TN}{TN + FP}$ （预测负）

下边是变化过后的值，主要用于计算，可以不用理睬。

6.1.2. 特定参数

1. 灵敏度，又称为正样本召回率

   $TPR = \frac{TP}{TP + FN}$
2. 特异度，又称为负样本召回率

   $TNR = \frac{TN}{TN + FP}$
3. 假正率

   $FPR = 1 - TNR = \frac{FP}{TN + FP}$
4. 假负率

   $FNR = 1 - TPR = \frac{FN}{TP + FN}$

6.2.「例」

6.2.1. ROC曲线

1. ROC曲线的x轴，实际上可以由每个阈值下混淆矩阵的（ ）计算而来

• A.C / (C+D)

• B.D / (A+D)

• C.B / (B+C)

• D.C / (B+C)

1. ROC曲线的y轴，实际上可以由每个阈值下混淆矩阵的（ ）计算而来

• A.A / (A+B)

• B.A / (A+D)

• C.B / (B+C)

• D.C / (B+C)

6.2.2. 基础参数

1. 对于属性值YES的响应率（Precision）应如何计算

• A.A / (A+B)

• B.A / (A+C)

• C.C / (A+C)

• D.B / (A+B)

1. 对于属性值YES的查全率（Recall）应如何计算

• A.A / (A+B)

• B.A / (A+C)

• C.C / (A+C)

• D.B / (A+B)

7. F1计算

7.1. 基本概念

    F-meansure的通用公式：

$F_{\beta} = (1 + \beta^2) \times \frac{Precision \times Recall}{(\beta^2 \times Precision) + Recall}$

    $F_1$的指标：

$F_1 = 2 \times \frac{Precision \times Recall}{Precision + Recall}$

    多分类做法：

• Macro F1：宏观，将多个类的F1相加算平均（每个类同等重要）

• Weighted F1：在Macro基础上加权（按照每种类型的比例加权计算）

• Micro F1：计算合并后的混淆矩阵

7.2. 「例」

7.2.1. 文本评估

正确分词（实际）	伊拉克	已	连续	第四天	将	原油	倾入	波斯湾
分词结果（预测）	伊拉克	已	连续	第四天	将	原	油	倾入	波斯	湾
正确	o	o	o	o	o	x	x	o	x	x

    上述混淆矩阵

实际\预测	真	假
真	TP = 6	FN = 2
假	FP = 4	-

• 查准率（Precision）：总共预测10个词，正确了6个，0.6，正确个数占预测总数的真。

• 查全率（Recall）：实际8个词，正确了6个，0.75，正确个数占实际总数的真。

• $F_1 \approx 0.67$

7.2.2. 多分类

1. 计算A的混淆矩阵：

   实际\预测	真	假
   真	2	2
   假	0	-
   查准率：总共预测2个词，正确了2个，$P = 1.0$
   查全率：实际4个词，正确了2个，$R = 0.5$
   $F_1 \approx 0.67$

2. 计算B的混淆矩阵：

   实际\预测	真	假
   真	2	1
   假	2	-
   查准率：总共预测4个词，正确了2个，$P = 0.5$
   查全率：实际3个词，正确了2个，$R = 0.66$
   $F_1 \approx 0.57625$

3. 计算C的混淆矩阵：

   实际\预测	真	假
   真	1	1
   假	2	-
   查准率：总共预测3个词，正确1个，$P = 0.33$
   查全率：实际2个词，正确了1个，$R = 0.5$
   $F_1 \approx 0.39759$

    上述结果计算：

1. 微平均 Micro F1（合并混淆矩阵）

   实际\预测	真	假
   真	5	4
   假	4	-
   查准率：总共预测9个词，正确5个，$P = 0.56$
   查全率：实际9个词，正确5个，$P = 0.56$
   $F_1 \approx 0.56$

2. 宏平均 Macro F1：多个F相加取平均

   $F_1 = \frac{0.6667 + 0.57265 + 0.39759}{3} = 0.546$
3. Weight F1：带上权重直接求和（注此处不需再除以3）

   $F_1 = \frac{4}{9} \times 0.6667 + \frac{3}{9} \times 0.57265 + \frac{2}{9} \times 0.39759 = 0.58$

8.多项式特征

8.1. 基本概念

    degree此参数决定了多项式的最大维度：

1. 假设有两个变量$x_1, x_2$
2. 如果degree = 2：$x_1, x_2, x_1^2, x_2^2$
3. 如果degree = 3：$x_1, x_2, x_1^2, x_2^2, x_1^3, x_2^3$
4. 默认的PolynomialFeatures包含了交互特征：$x_1x_2$

图中有错，Polynomial Features为 $x_1^2, x_2^2$，中间的6才是交互（互信息）。