数据挖掘150道解析（二）40-50题

41. 频繁项集、频繁闭项集、最大频繁项集之间的关系是： (C)
A、频繁项集 频繁闭项集 =最大频繁项集
B、频繁项集 = 频繁闭项集 最大频繁项集
C、频繁项集 频繁闭项集 最大频繁项集
D、频繁项集 = 频繁闭项集 = 最大频繁项集
解析：
频繁项集，就是事例里频繁出现的项的集合，比如事例为每个人的购物清单，项就是买的东西，项集就是指频繁地同时出现的集合。比如人们总是喜欢同时买酒和花生，那么酒和花生这两个项就是一个频繁二项集。
频繁项集里存在着较多的冗余，因此人们又引入了频繁闭项集和最大频繁集的概念。

频繁闭项集：设I为项的集合，T为事例的集合，则定义如下映射：1）对于X属于I（项集），f(x)是T之中包含X的事例集；2）对于Y属于T（事例集），g(Y)是所有Y都包含的项集。可以看到，对于一般的X，g(f(X))可能会大于X，而频繁闭项集满足就是g(f(X))=X的项集X。
举例来说，比如人们总是一起买酒和花生和饼干三种东西（顺便举个例子），而不会只买其中的两种，那么如果找频繁项集，那么这三种的任意两个的组合以及三者组合都是频繁项集，比如酒和饼干；但是只有酒和花生和饼干三者的组合才是频繁闭项集。也就是说，不会存在其它的项总是和频繁闭项集一起出现，否则g(f(X))就会包含那些其它项了。

最大频繁集：如果X是一个频繁项集，而且X的任意一个超集都是非频繁的，则称X是最大频繁项集
这个应该说是比较明确的，就是这个集合已经不能再扩充了，否则就不是频繁集了

42. 考虑下面的频繁3-项集的集合：{1，2，3}，{1，2，4}，{1，2，5}，{1，3，4}，{1，3，5}，{2，3，4}，{2，3，5}，{3，4，5}假定数据集中只有5个项，采用 合并策略，由候选产生过程得到4-项集不包含（C）
A、1，2，3，4
B、1，2，3，5
C、1，2，4，5
D、1，3，4，5解析：
根据数据挖掘Apriori算法的性质之一：判定是否可作为K项频繁集是通过K项集分裂为K个K-1项集,考察K-1项集是否为Lk-1,要生成4-项集,｛1,2,4,5｝分裂后为｛1,2,4｝｛2,4,5｝｛1,2,5｝｛1,4,5｝其中,｛1,4,5｝不属于频繁3项集,所以｛1,2,4,5｝不能作为4项集,因为有性质为：任何非频繁的K-1项集都不可能是频繁项集K项集的子集.

44. 在图集合中发现一组公共子结构，这样的任务称为 ( B )
A、频繁子集挖掘
B、频繁子图挖掘
C、频繁数据项挖掘
D、频繁模式挖掘解析：
频繁模式是频繁地出现在数据集中的模式（如项集、子序列或者子结构）。例如，频繁地同时出现在交易数据集中的商品（如牛奶和面包）的集合是频繁项集。
两种经典频繁子图挖掘算法编辑
Apriori算法
"generation and test" 思想:
k-频繁子集用于生成 k+1-子集，根据downward closure property性质进行剪枝，生成 k+1候选集，通过对数
据库进行扫描判断候选子集中哪些是频繁的。如此下去，直到不能找到频繁项集。
"downward closure propert" 性质：
如果 k+1子集的任何一个k子集是非频繁的，则是k+1子集一定也是非频繁的。
a. AGM算法
每次添加一个顶点
b. FSG算法
每次添加一条边
FP-growth算法
主要思想：
将产生频繁集的数据压缩到一棵频繁模式树FP-tree中，用FP-tree存储项的关联信息，然后对模式树产生频繁集。
a. gSpan算法
b. FFSM算法

48. 以下哪些算法是分类算法，（B）
A，DBSCAN
B，C4.5
C,K-Mean
D,EM
解析：
DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一个比较有代表性的基于密度的聚类算法。与划分和层次聚类方法不同，它将簇定义为密度相连的点的最大集合，能够把具有足够高密度的区域划分为簇，并可在噪声的空间数据库中发现任意形状的聚类。

C4.5是机器学习算法中的另一个分类决策树算法，它是基于ID3算法进行改进后的一种重要算法，相比于ID3算法，改进有如下几个要点：
用信息增益率来选择属性。ID3选择属性用的是子树的信息增益，这里可以用很多方法来定义信息，ID3使用的是熵（entropy， 熵是一种不纯度度量准则），也就是熵的变化值，而C4.5用的是信息增益率
。
在决策树构造过程中进行剪枝，因为某些具有很少元素的结点可能会使构造的决策树过适应（Overfitting），如果不考虑这些结点可能会更好。
对非离散数据也能处理。
能够对不完整数据进行处理
假设我们提取到原始数据的集合为(x1, x2, …, xn)，并且每个xi为d维的向量，K-means聚类的目的就是，在给定分类组数k（k ≤ n）值的条件下，将原始数据分成k类
S = {S1, S2, …, Sk}，在数值模型上，即对以下表达式求最小值：
\underset{\mathbf{S}} {\operatorname{arg\,min}} \sum_{i=1}^{k} \sum_{\mathbf x_j \in S_i} \left\| \mathbf x_j - \boldsymbol\mu_i \right\|^2
这里μi 表示分类Si 的平均值。

在统计计算中，最大期望（EM）算法是在概率（probabilistic）模型中寻找参数最大似然估计或者最大后验估计的算法，其中概率模型依赖于无法观测的隐藏变量（LatentVariable）。最大期望经常用在机器学习和计算机视觉的数据聚类（DataClustering）领域。最大期望算法经过两个步骤交替进行计算，第一步是计算期望（E），利用对隐藏变量的现有估计值，计算其最大似然估计值；第二步是最大化（M），最大化在E步上求得的最大似然值来计算参数的值。M步上找到的参数估计值被用于下一个E步计算中，这个过程不断交替进行。

49. 以下哪些分类方法可以较好地避免样本的不平衡问题， （A）
A，KNN
B，SVM
C，Bayes
D，神经网络
解析：
邻近算法，或者说K最近邻(kNN，k-NearestNeighbor)分类算法是数据挖掘分类技术中最简单的方法之一。所谓K最近邻，就是k个最近的邻居的意思，说的是每个样本都可以用它最接近的k个邻居来代表。
kNN算法的核心思想是如果一个样本在特征空间中的k个最相邻的样本中的大多数属于某一个类别，则该样本也属于这个类别，并具有这个类别上样本的特性。该方法在确定分类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。 kNN方法在类别决策时，只与极少量的相邻样本有关。由于kNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，kNN方法较其他方法更为适合。

支持向量机(Support Vector Machine)是Cortes和Vapnik于1995年首先提出的，它在解决小样本、非线性及高维模式识别中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中。支持向量机方法是建立在统计学习理论的VC 维理论和结构风险最小原理基础上的，根据有限的样本信息在模型的复杂性（即对特定训练样本的学习精度，Accuracy）和学习能力（即无错误地识别任意样本的能力）之间寻求最佳折衷，以期获得最好的推广能力（或称泛化能力）。
详细请参考：http://blog.csdn.net/chl033/article/details/4400116

神经网络：逻辑性的思维是指根据逻辑规则进行推理的过程；它先将信息化成概念，并用符号表示，然后，根据符号运算按串行模式进行逻辑推理；这一过程可以写成串行的指令，让计算机执行。然而，直观性的思维是将分布式存储的信息综合起来，结果是忽然间产生想法或解决问题的办法。这种思维方式的根本之点在于以下两点：1.信息是通过神经元上的兴奋模式分布储在网络上；2.信息处理是通过神经元之间同时相互作用的动态过程来完成的。

50. 决策树中不包含一下哪种结点， (C)
A,根结点（root node)
B,内部结点（internal node）
C,外部结点（external node）
D,叶结点（leaf node）
解析：
决策树由树根（决策节点）、其他内点（方案节点、状态节点）、树叶（终点）、树枝（方案枝、概率枝）、概率值、损益值组成。