求数据挖掘考试题

1. 什么是关联分析
关联分析是数据挖掘领域常用的一类算法，主要用于发现隐藏在大型数据集中有意义的联系。
举一个大家最耳盯姿老熟能详的例子，就是尿布和啤酒，表示成关联规则的形式就是｛尿壶｝ ——> ｛啤酒｝。这就是使用关联分析方法所得到的结果，而关联分析所得到的结果，我们可以用关联规则 或者 频繁项集的形式表示。
在进行关联分析时，我们常常会遇到这样两个问题：
A. 从大型数据集中发现模式一般来说需要在计算上付出巨大的代价，甚至往往是impossble的，我们往往采用置信度和支持度的剪枝来解决这个问题。
B. 所发现的某些模式可能是虚假的，这个我们需要采用一些关联规则的评估来解决这个问题。
2. 基本概念
A. 项集：在关联分析中，包含0个或者多个的项的集合称为 项集。 如果一个项集包含k个项，那么就称为k-项集。比如｛牛奶，咖啡｝则称为2项集。
B. 支持度： 支持度用来确定给定数据集的频繁程度，即给定数据集在所有的数据集中出现的频率，例如s(X -> Y) = P(X,Y) / N
C. 置信度： 置信度则是用来确定Y在包含X的事务中出现的频繁程度，即 c(X -> Y) = P(X,Y) / P(X)
3. 关联分析算法的基本原理
支持度和置信度的意义在于，支持度是一个重要的度量，如果支持度很低，代表这个规则其实只是偶然出现，基本没有意义。因此，支持度通常用来删除那些无意义的规则。而置信度则是通过规则进行推理具有可靠性。用c(X->Y)来说，只有置信度越高，Y出现在包含X的事务中的概率才越大，否则这个规则也没有意义。
通常我们在做关联规则发现的时候都会设定支持度和置信度阈值 minsup 和minconf ， 而关联规则发现则是发现那些支持度大于等于minsup 并且置信度大于 minconf的所有规则。所以，提高关联分析算法效率最简单的办法则是提高支持度和置信度的阈值。
所以，通过上面的概念，我们可以很自然地想到，关联分析的基本算法：
A. 找到满足最小支持度阈值的所有项集，我们称之为频繁项集。（例如频繁二项集，频繁三项集）
B. 从频繁项集中找到满足最小置信度的所有规则。
4. 关联分析算法的评估
A. 兴趣度的客观度量
首先，我们来考虑一下支持度-置信度框架的局限性。
首先册梁是支持度，举例来说，在图书市场中，文学类书籍的数量远大于物理类书籍，那么物理类书籍的规则支持度就会很低，这样就导致很多物理类书籍的关联规则都被过滤掉了。
接下来是置信度，举例来说，我们对1000人做度量，发现有200人喜欢喝茶，其中有150人喜欢喝咖啡，50人不喜欢，那么我们通过置信度计算发现c(喝茶 -> 喝咖啡)这个的置信度非常高，我们于是可以推算出喜欢喝凯升茶的人都喜欢喝咖啡。但是其实我们看接下来的调查，另外不喜欢喝茶的800人中，有650人喜欢喝咖啡。 综上所述，我们可以发现，其实喝茶和喝咖啡其实是两个独立事件。所以我们可以概括一下，置信度的缺点，就是置信度度量忽略了规则后件中项集的支持度。
(A) 为了解决这个问题，我们引入一个度量，称为提升度(lift)，来计算置信度和规则后件项集支持度的比率：
lift(A->B) = c(A->B) / s(B)
那么对于二元项集来说，我们可以做这样一个变换：
lift(X->Y) = c(X->Y) / s(Y) = ( p(X,Y) / p(X) ) / p(Y) = p(X,Y) / p(X)p(Y)
那么这里，我们则可以把lift(X->Y)称为兴趣因子，表示为I(A,B)
通过概率学知识我们可以知道，如果X事件和Y事件相互独立（或者我们称之为满足事件独立性假设），那么p(X,Y) = p(X) * p(Y)，那么我们则可以这样来表示兴趣因子的度量：
当I(A,B) = 1时，我们称A和B是相互独立的，当I(A,B) < 1时，我们称A和B是负相关的，否则我们称A和B是正相关的。
但是从这个简陋的计算模型，我们就可以很轻易地感觉出单纯用兴趣因子来做关联度度量的不靠谱。例子特别容易找了。
(B) 对应兴趣因子，还有另外一种相关分析，IS度量等各种兴趣度客观度量方式。