# 数据挖掘作业5

**Repository Path**: cai-lingyi/data-mining-job-5

## Basic Information

- **Project Name**: 数据挖掘作业5
- **Description**: 本次作业实现了3个经典算法：KNN算法、K-Means算法、朴素贝叶斯算法。
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 2
- **Forks**: 0
- **Created**: 2020-11-23
- **Last Updated**: 2021-09-16

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 数据挖掘作业5

#### 简介
本次作业实现了3个经典算法：KNN算法、朴素贝叶斯算法、K-Means算法。

#### 详细介绍
 **一、分类算法** 
  
        本次实现的分类算法有KNN算法和朴素贝叶斯算法，他们都有类标签，属于有监督算法。
        简而言之，KNN算法是选取待分类数据周围最近的K个点，以少数服从多数的原则为基础，判断未知点的类别。朴素贝叶斯算法利用贝叶斯定理与学到的联合概率模型进行分类预测。
        对于有监督算法，一般适用于如下问题。因为监督学习可以认为是学习一个模型，使它能对给定的输入预测相应的输出。监督学习包括分类、标注、回归。本篇主要考虑前两者的学习方法。分类问题是从实例的特征向量到类标记的预测问题；标注问题是从观测序列到标记序列(或状态序列)的预测问题。可以认为分类问题是标注问题的特殊情况。 分类问题中可能的预测结果是二类或多类；而标注问题中可能的预测结果是所有的标记序列，其数目是指数级的。K近邻法、朴素贝叶斯法、决策树是简单的分类方法，具有模型直观、方法简单、实现容易等特点；
        对于有监督算法的模型而言，分类问题与标注问题的预测模型都可以认为是表示从输入空间到输出空间的映射.它们可以写成条件概率分布P(Y|X)或决策函数Y=f(X)的形式。前者表示给定输入条件下输出的概率模型，后者表示输入到输出的非概率模型。朴素贝叶斯算法是概率模型，K近邻算法是非概率模型，而决策树可以看做概率模型也可以看做非概率模型。直接学习条件概率分布P(Y|X)或决策函数Y=f(X)的方法为判别方法，对应的模型是判别模型：K近邻算法、决策树、logistic回归等。首先学习联合概率分布P(X,Y)，从而求得条件概率分布P(Y|X)的方法是生成方法，对应的模型是生成模型：朴素贝叶斯法等。决策树是定义在一般的特征空间上的，可以含有连续变量或离散变量。k近邻法的特征空间是欧氏空间(更一般地，是希尔伯特空间)。提升方法的模型是弱分类器的线性组合，弱分类器的特征空间就是提升方法模型的特征空间。k近邻法、决策树使用的是非线性模型。

 **二、聚类算法** 

        本次实现的聚类算法是K-Means算法，无类标签，属于无监督算法。
        简而言之，𝑘均值聚类算法，首先选择k个类的中心，将样本分到与中心最近的类中，得到一个聚类结果；然后计算每个类的样本的均值，作为类的新的中心；重复以上步骤，直到收敛为止。
        𝑘均值聚类算法有以下特点：基于划分的聚类方法；类别数k事先指定；以欧氏距离平方表示样本之间的距离或相似度，以中心或样本的均值表示类别；以样本和其所属类的中心之间的距离的总和为优化的目标函数；得到的类别是平坦的、非层次化的；算法是迭代算法，不能保证得到全局最优。
        对于无监督学习，其基本想法是对给定数据（矩阵数据）进行某种“压缩”，从而找到数据的潜在结构，假定损失最小的压缩得到的结果就是最本质的结构。可以考虑发掘数据的纵向结构，对应聚类。也可以考虑发掘数据的横向结构，对应降维。还可以同时考虑发掘数据的纵向与横向结构，对应概率模型估计。
        聚类是将样本集合中相似的样本（实例）分配到相同的类，不相似的样本分配到不同的类。在聚类过程中中，可能会使用到降维。降维是将样本集合中的样本（实例）从高维空间转换到低维空间。假设样本原本存在于低维空间，或近似地存在于低维空间，通过降维则可以更好地表示样本数据的结构，即更好地表示样本之间的关系。降维有线性降维和非线性降维，降维方法有主成分分析。
        除了K-Means算法外，还有许多无监督学习方法，最后对无监督学习方法特点做如下总结：
|      | 方法       | 模型         | 策略         | 算法         |
|------|----------|------------|------------|------------|
| 聚类   | 层次聚类     | 聚类树        | 类内样本距离最小   | 启发式算法      |
|      | k均值聚类    | k中心聚类      | 样本与类中心距离最小 | 迭代算法       |
|      | 高斯混合模型   | 高斯混合模型     | 似然函数最大     | EM算法       |
| 降维   | PCA      | 低维正交空间     | 方差最大       | SVD        |
| 话题分析 | LSA      | 矩阵分解模型     | 平方损失最小     | SVD        |
|      | NMF      | 矩阵分解模型     | 平方损失最小     | 非负矩阵分解     |
|      | PLSA     | PLSA模型     | 似然函数最大     | EM算法       |
|      | LDA      | LDA模型      | 后验概率估计     | 吉布斯抽样，变分推理 |
| 图分析  | PageRank | 有向图上的马尔可夫链 | 平稳分布求解     | 幂法         |



#### 实验环境

1.  PC一台
2.  Win10 操作系统
3.  Jupyter Notebook(Anaconda3)


#### 数据集
        本次3个算法使用的数据集是iris数据集。这个数据集里一共包括150行记录，其中前四列为花萼长度(Sepal.Length)，花萼宽度(Sepal.Width)，花瓣长度(Petal.Length)，花瓣宽度(Petal.Width)等4个用于识别鸢尾花的属性，特征值都为正浮点数，单位为厘米,第5列为鸢尾花的类别（包括Setosa[山鸢尾]，Versicolour[杂色鸢尾]，Virginica[维吉尼亚鸢尾]三类）。作为Python中经典的机器学习模块，sklearn围绕着机器学习提供了很多可直接调用的机器学习算法以及很多经典的数据集，有待我们进一步尝试、挖掘。


#### 总结以及心得体会

1.  通过本次实验(数据挖掘作业5)，在掌握理论的基础上，通过代码实现了KNN算法、朴素贝叶斯算法、K-Means算法，对其理解更加透彻。
2.  对经典的机器学习算法有了深刻的了解，进而能理解其它的算法，并能对某些算法做一些适当的改进。
3.  对于可视化的学习有了进一步了解，能直观帮助我们理解各类算法的实验结果。

#### reference
李航.统计学习方法[M].北京:清华大学出版社,2019.

周志华.机器学习[M].北京:清华大学出版社,2016.

Sammut C,Webb G I.Machine Learning[J].2010,10.1007/978-0-387-30164-8(Chapter 89):139-139.

Mitchell T M.Machine Learning[M].McGraw-Hill,2003.

Zaki M J, r W M.Data Mining and Analysis:Fundamental Concepts and Algorithms[M].2014.