By

总阅读次

文章目录
  1. 1. TF-IDF Feature Extraction (TF-IDF特征提取）
    1. 1.1. 数据
    2. 1.2. 步骤
    3. 1.3. 结果
    4. 1.4. 思考
  2. 2. Dimensionality Reduction （降维方法）
    1. 2.1. 任务
    2. 2.2. PCA
    3. 2.3. SVD
    4. 2.4. ISOMAP
    5. 2.5. 数据
    6. 2.6. 几点细节
    7. 2.7. 结果
    8. 2.8. 代码解释
    9. 2.9. 思考
  3. 3. Clustering （聚类）
    1. 3.1. 任务
    2. 3.2. K-medoids 算法
    3. 3.3. 谱聚类算法
    4. 3.4. 数据与环境
    5. 3.5. 结果
    6. 3.6. 思考
  4. 4. Training Classifers via Stochastic Gradient Descent （随机梯度下降）
  5. 5. Ensemble Learning （集成学习）
  6. 6. Association rule mining （关联规则挖掘）
  7. 7. 总结

本文描述了几个月以来所做的一些数据挖掘实践，综合总结一下，形成此文，也对本学期数据挖掘课程做一个总结。
代码Github地址： https://github.com/whatbeg/DataMiningTasks

TF-IDF Feature Extraction (TF-IDF特征提取）

数据

  1. 数据为数据集 ICML
  2. 采用 Python 2.7.10 和 Windows10 系统 作为编程环境
  3. 输出的结果名为 “类名_RESULT.txt”，位于与类目录同级的目录下。
  4. 结果数据包含 N 条， N 为此类中文章数目，在每条输出结果中，第一行为文章名字，然后紧跟着的是词的 TF-IDF 值向量，由于值向量稀疏，所以做了压缩，即以“序号： TF-IDF 值”的表示方法。

步骤

  1. 首先集合所有文章，得到他们的路径
  2. 然后将所有文章分词，将无关或者非法字符用空格替换，然后采用 NLTK 的 word_tokenize 方法进行
    分词， 然后用 NLTK 的 SnowballStemmer 进行词干提取，然后将单词进行小写化， 通过字典去重（存
    成字典 key），然后去除一些无关词，数字以及停用词，停用词选用了网上一个版本的停用词，约 900
    个停用词。
  3. 然后将所有词排序，编号，后续输出时以编号代替词，而不需写出词。
  4. 然后循环处理每个类（每种论文的目录），对这个目录下的所有文章，对每篇文章的词算出他们的TF 和 IDF 值，得到 TF-IDF 值，存储到这个类这篇文章的结果数据中。
  5. TF 词频采用的计算方法为： TF = 词在文章中出现次数 / 文章总词数
  6. IDF 计算方法为： IDF = log(总文章数 / 此词出现的文章数目)
  7. 处理完每个类，结束。

结果

思考

TF，IDF 的计算方法多种多样，本文采用的方法中，最终结果的TF-IDF数值上偏小，在保证含义的情况下可以采用其他方法，使 TF-IDF大致为一个正常值，以便更好地比较。用NLTK包的stemmer提取词干的时候难免会有一些提取的错误，这是由于词干提取并非完美的缘故，由于这个缘故，可以不进行词干提取，这样可以保持所有的信息，但是缺点就是会有多种变形词，单词数会增加 1/4到1/3，导致矩阵增大。

Dimensionality Reduction （降维方法）

任务

本部分描述实现降维的三种方法，分别是 PCA， SVD 以及流形学习中的 ISOMAP 算法，其中 ISOMAP 算法还需调用 MDS（ Multiple Dimensional Scaling 多维缩放），并且对这三种算法在两个不同规模的数据集上进行了测试。

PCA

PCA 算法的原理这里不做详细描述，只写明实现过程，首先将训练数据集中心化，然后计算训练数据集的协方差矩阵，对此协方差矩阵 C 做特征值分解，可以得出 C 的所有特征值和对应的特征向量，选取最大的k（降维后的维度数）个特征值和其对应的特征向量，即可得到高维到低维的映射矩阵 W。
PCA 算法伪代码如下：

SVD

SVD 算法与 PCA 算法很相似，并且可以使用SVD来计算PCA，它们的唯一区别就是SVD并不对训练样本集进行中心化，使各个维度的均值为 0，而是直接对训练集样本矩阵做 SVD分解，得出排序后的特征值和特征向量矩阵，取前k个特征值对应的特征向量即可组成高维到低维的映射矩阵。
SVD 算法伪代码如下：

ISOMAP

ISOMAP 是一个非线性降维算法，全称 Isometric Mapping，等度量映射，重点在于高维空间的测地线距离在低维空间的保持。算法流程如下：
（a） 计算样本集（测试集和训练集）的欧式距离
（b） 对于每个样本，取 4 个最近的样本，建立连边
（c） 用最短路算法算出两两点间的最短距离，这里会出现一个整个图可能形成多个
连通分量而导致不连通的问题，这样的话令不连通点间的距离为 0。
（d） 将整个图的距离矩阵作为 MDS 的输入，直接得出低维空间的样本表示，包括
测试集和训练集。
ISOMAP 算法伪代码如下：

最后的测试是讲高维样本映射到低维空间，然后运行 1-NN 算法对测试数据进行分类。

数据

  1. 数据 sonar 和 splice 数据集， sonar 是小数据集， splice 是较大的数据集。
  2. 采用 Python 2.7.10 和 Windows10 系统 作为编程环境
  3. 输出的结果将会被组成一个表格在下文给出。
  4. 结果数据包括在不同数据集下和不同的降维后维度数 k 的条件下，得到的最后 1NN 分类结果的准确率。

几点细节

（a） 在实现 ISOMAP 的时候， 4NN 地建立邻接图很有可能会形成多个联通分量，这时候有两种解决方法，一种是增大 Nearest Neighbor 的数量，直到联通，但是这种方法有所不妥， NN 越大，越有可能形成“短路”的现象，即明明两个点距离很远（他们的连边跨越了不可达区域），还是会将它们连起来，距离为其欧氏距离，这样破坏了流形的性质，可能造成结果的偏差；另一种方法使不连通的两两联通分量，各自取一个点使这两点距离最近，将这两点连边，这样就可以使这两个连通分量联通，这种方式大大降低了“短路”的概率，小小的不足就是会有一笔计算开销，不过经过测试，这种开销的增加可以近乎忽略。

详细过程如下：

1
2
3
1. 得到 4NN 图，通过 dfs 对图中点进行着色，两点之间如果可以连通则着同一色，最后得到的颜色数就是联通分量数。
2. 找两个距离最近的联通分量合并，将颜色赋为相同颜色
3. 重复 2 直到全部为一个联通分量

使用了贪心的思想，在算法的正确性上，可以在保证“短路”概率最小的前提下将非连通图变成连通图。

（b） ISOMAP 计算任意两点之间的最短距离时，在大数据集 splice（ 3000+条）下，python计算效率明显低下， 测试下发现需要 8 个小时左右！ 于是在代码中嵌入了 C 程序的执行，将时间缩短到百秒级别，传参采用文件形式。

结果

测试结果如下，不同数据集，不同维度 k 下不同算法进行 1NN 分类的准确率见下图。

代码解释

其中 DimensionalityReduction.py 实现三种降维算法，floyd.c, floyd.exe, floyd.o 为 C 语言实现的 Floyd 算法，供 python 调用，graph.txt 为 python 往 C 传的参数。graph_floyded.txt 为 C 对图运行完 floyd 算法后传回的图参数。然后接下来是 4 个数据集和测试集。最后是 Test.py 测试程序。

思考

  1. python 调用 C 有一套接口，如 ctypes, cython 等，可以将 floyd 算法或者 dijkstra 算法直接嵌入到 python 程序中，可以免去文件传参的开销，加快运行速度。

  2. MDS 中，对内积矩阵 B 进行特征分解的时候，明明 B 是实对称矩阵， 采用numpy.linalg.eig()函数计算还是会出现复数特征值的情况，尽管他们的虚部或正或负都很小，即使 B = 0.5(B+B’)这样的处理之后还是会出现，后来采用了eigh()函数，即计算埃尔米特矩阵或者对称矩阵特征值和特征向量的专用函数，则分解出来的都是实数。所以可能是函数的问题，因为我们已经知道B是实对称的，所以直接可以用 eigh 函数。

  3. 在处理 ISOMAP 邻接图不连通的情况时，不知道有没有更好的方法，在网上基本鲜有这方面的资料，不知道看到这里的读者有没有建议呢？

  4. 最后由于能够保证联通，所以测试了建立近邻连接图的邻接个数（这里是 4）对测试结果的影响， 选了 3NN， 4NN， 5NN， 6NN 四种， 最后在发现 3NN 最差，在大数据集 splice 上， 5NN 取得了很好的效果， 6NN 次之， 4NN 再次之，但是在小数据集上，4NN 是最好的， 5NN 和 6NN 的表现就大大的变差了。

所以来说，最后选择了用 4NN（近邻连接图）来测试小数据集， 5NN 来测试大数据集。

取得效果如下：

总的来说， NN 太小容易使本来很近的点却要在图中绕很远才能到，给距离带来了误
差， NN 越大则“短路”可能性又提高。

Clustering （聚类）

任务

本部分描述实现两种聚类算法，其一为K-medoids（K-中心点）算法，其二为基于谱图理论的谱聚类算法。数据集有两个，一个是小数据集 german.txt，其中有1000个样本，每个样本有24个特征，每个样本占一行，最后为该样本的标签，标签分两类，1和-1，标签用作Gini系数和Purity的计算。另一个是大数据集mnist.txt，其中包括10000个样本，每个样本有784个特征，每个样本占一行，最后为该样本的标签，标签分 10
类， 0-9。
下面简要说明两种聚类算法的流程。

K-medoids 算法

类似 K-means 算法的原理，只是聚类的中心不是所有该类所有样本的特征平均值，而是限制聚类的中心必须是该类的某一个样本，这样做的好处是可以有效避免离群点的影响，适用于异构数据等。初始找 k 个中心点，然后将每个点分到离它最近的中心点代表的类中，然后对每一类更新中心点，这样循环往复直到中心点不再变化。

算法伪代码如下：

谱聚类算法

基于谱图理论，适用于数据是非凸的或者类似于嵌入高维空间的低维流形时。基本思路是对每个样本点，与跟它最相似的多个样本点之间连边，边的权值可以赋为相似度或者 1（两种方式），然后计算拉普拉斯矩阵 L=D-W，其中 D 为每个样本点的度2作为对角元素组成的对角矩阵，W就是刚才的距离矩阵。然后对拉普拉斯矩阵 L 进行特征分解，取最小的 k 个特征值对应的特征向量作为新的样本表示，然后对这个样本表示进行K-medoids 聚类或者 K-means 聚类等即可得到聚类结果。

算法伪代码如下：

数据与环境

  1. 数据为 german 和 mnist 数据集， german 是小数据集， mnist 是较大的数据集，数据说明见上一节。
  2. 采用 Python 2.7.12 和 Ubuntu16.04 系统 作为编程环境
  3. 输出的结果将会被组成一个表格在下文给出。
  4. 结果数据包括在不同数据集下k-medoids算法聚类的效果，以Gini系数和Purity作为衡量依据，以及在不同数据集下和不同近邻数下 Spectral Clustering 聚类的效果，结果也以 Gini系数和 Purity 作为依据。

结果

测试结果如下，不同数据集下，不同算法下进行聚类的 Purity 见图 1。

不同数据集下，不同算法下进行聚类的 Gini 系数见图 2。

思考

纯枚举中心点替换的方法虽然说准确度高，但是速度太慢，在更大的数据集下必然很低效，可以考虑采用随机选取 r 个点对进行替换的方式，损失一点准确度，来对算法进行加速。或者也可以采用其他优化算法优化效率

Training Classifers via Stochastic Gradient Descent （随机梯度下降）

这部分详见文章： Training Classifers via Stochastic Gradient Descent

Ensemble Learning （集成学习）

这部分详见文章： 谈一谈朴素贝叶斯作为基分类器的Adaboost算法 （Naive Bayes Based Adaboost）

Association rule mining （关联规则挖掘）

这部分源码见AprioriTest，实现了一下Apriori算法，具体流程不细述。

总结

本文简要总结了一下数据挖掘的几个实践project，其中包括最基本的TF-IDF统计，以及降维，聚类，分类，集成学习，随机梯度下降等等，简要实现了几个数据挖掘上的基本算法，实现的比较简单，当做进一步理解算法之用，机器学习的方面远远不止这些，比如降维方法除了上述三种之外还有LLE，LE，LTSA，KPCA等等，聚类还包括层次聚类，AGNES等，以及kmeans，CLARANS等基于代表的算法，还有基于密度的方法，包括DENCLUE,DBSCAN等等，以及基于网格的方法(grid-based)包括CLIQUE等。分类方法那就更多了，SVM，LR，DT，，，一些数据挖掘比赛中用的比较多的是XGBoost，GBDT等，有时间要好好了解一下，最后集成学习中主要包括两大类算法，一种叫Bagging（Bootstrapped Aggregating）,主要通过多次采样平均，来降低variance，另一种Boosting，通过多个分类器的集成，降低bias。总之，数据挖掘课程的学习到这里就告一段落了，接下来的学习就要靠自己了，慢慢的运用，慢慢的学习吧，数据挖掘这条路，还是有很远要走的。

数据科学 | Data Science
机器学习