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等，
这些值越大，说明纯度越低。然后定义一个分割的纯度增量，

.. math::

    \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:

.. math::

    \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)

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

.. math::

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

求得 :math:`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
-----------------------------------------------------