Introduction to Data Mining

Chapter 2: Data

Stratified Sampling

equal numbers of objects are drawn from each group even though the groups are of different size.

Note

Difference between Dimension Reduction, Feature Selection and Feature Creation.

• Feature Selection: select a subset of original features
• Dimension Reduction: create new features to replace original features(PCA && SVD)
• Feature Creation: create new features

Proximity

There are two ways to describe proximity: similarity and distance(or disimilarity), which can be changed accordingly, for example, using Gaussian Kernel.

计算距离有几种方法：欧式距离，Hamming距离等。

Messures that satisfy Positivity, Symmetry, and Triangle Inequality are known as metrics.

计算相似度也有几种方法:SMC(Simple Matching Coefficient)，Jaccard Coefficient, Cosine Similarity等。

如何选择合适的度量方法呢？

1. 对于dense, continuous data来说，欧式距离是一个不错的选择。
2. 如果是sparse data来说，JC或者Cosine可能更好，但是这种情况下可以通过PCA转化features, 然后再用欧式距离来算。

Chapter 4 && Chapter 5: Classification

关于不同分类算法的比较，从下面的方面来考虑。

1. 建立模型是不是比较耗时间
2. 有了模型之后分类一个数据是不是耗时间
3. 是不是容易被noise干扰
4. 模型是不是容易进行解释，也就是把这个模型用自然语言表达出来

Desision Tree

定义一些度量节点t纯度的方法，比如Entropy, Gini等， 这些值越大，说明纯度越低。然后定义一个分割的纯度增量，

\[\Delta = I(parent) - \sum_{j=1}^{k} \frac{N(v_j)}{N}I(v_j)\]

挑选出一个Attribute能够造成最大的增量。

为了防止overfitting，可以对决策树进行剪枝，有两种方法：

1. 在构建决策树时剪枝，如果造成的增量小于某一个值就剪枝
2. 在构建好了决策树之后进行剪枝，将一棵子树用一个节点或一个分支来替代。

决策树的特点，对应于上面的四点：

1. 建立模型时间复杂度不是很高，因为采用的是贪婪算法，没有找到最优解
2. 在有了决策树之后分类很快，相当于树的下降，线性于树的深度
3. 不容易被noise干扰，特别是有了剪枝之后
4. 容易被解释

Overfitting

Overfitting是指train error很低，但是test error很高， 也可以说是bias低，但variance高， 原因是因为模型太复杂，不够general. 导致Overfitting的原因还是有效的训练集不够， 或者是没有具有代表性的元素，或者是因为噪声的干扰。

可以通过交叉验证来评判两个模型的好坏。

Rule-Based Classifier

基于规则的分类与决策树不同的地方在于 它可以是没有覆盖所有的情况或者是一个数据可以对应多个规则， 而在后面的讨论中都是后者，为了解决冲突的问题， 对规则进行排序，这样排在前面的规则先发挥作用。

排序的方式采用的是按类排序，数目少的类排在规则的前面。 对一个类里面的进行规则提取， 每次提取一条规则，将匹配到这个规则的记录移除，直到终止条件(添加了negtive case)。 提取规则时，有两个方向，从generic到specific或从specific到generic, 可以使用贪婪的方法添加一个conjuction或者移除一个conjunction。 同时，为了弥补贪婪算法的不足，可以使用beam search， 每轮迭代维护k个最可能的结果。

利用validation set来修剪rule，通过移除一个conjuction达到修剪的目的。 比如通过计算(p-n)/(p+n)来看是不是修要修剪。

Note

Rule-Based Classifier非常适合不平衡的分类。

对于它的特点，与决策树一样。

kNN Classifier

基本原理，通过节点的k个最近的邻居来进行归类， 不需要建立一个模型，可以直接进行分类。

特点：

1. 不许要时间建立模型
2. 分类的时间较长
3. 对noise敏感
4. 不容易被解释

Beyesian Classifier

找到一个这样的y作为lable:

\[\operatorname*{arg\,max}_y P(y|x) = \operatorname*{arg\,max}_y \frac{P(x|y)P(y)}{P(x)} = \operatorname*{arg\,max}_y P(x|y)P(y)\]

通过这样的转换是因为 \(P(y|x)\) 比较难求， 而可以利用这个公式:

\[P(x|y) = \prod_{i=1}^{d} P(x_i|y)\]

求得 \(P(x|y)\) 。

同时可以利用Laplace-Smoothing防止为0的项。

注意Beyesian分类器的条件是属性之间相互独立， 如果不相互独立，要需要通过Beyesian网络来求得概率。

神经网络和SVM

等以后系统学习之后再来做笔记吧。

Ensemble Method

基本思想：通过组合多个分类器作为一个分类器，能够达到更好的效果。

可以对数据集和属性进行sample来分别训练多个分类器。 Random Forest是指在构建决策树时随机选取Feature进行Split。

对于不平衡的分类问题，准确率还需要通过其他的表示方法来计算。

利用二分类器组合成多分类器时的方法有：

1. 分成k个1-r分类问题
2. 分成k(k-1)/2个1-1分类问题
3. 利用Error-Correcting Output Coding的方法，对类别进行编码， 一次对于某一位进行二分类，根据分类的结果进行投票， 投票最多的是最后的类别。

Chapter 6: Association Analysis

关联分析的目的是提取出类似于{Diapers} -> {Beers}这样的关联规则， 有两个步骤：

1. 找出频繁项集
2. 根据频繁项集生成规则

Chapter 8: Cluster Analysis