人工智能 第二版 课件 第五章 统计机器学习方法

第五章统计机器学习方法5.1统计学习方法统计学习方法在人工智能历史上的作用属于机器学习的一种方法引导人工智能走出低谷让人工智能真正走向实用机器学习如果一个系统能够通过执行某个过程改进它的性能，这就是学习——司马贺（赫伯特·西蒙）统计机器学习通过运用数据及统计方法提高系统性能的机器学习运用统计方法，从数据出发提取数据的特征，抽象出问题的模型，发现数据中所隐含的知识，最终用得到的模型对新的数据进行分析和预测统计学习方法分类有监督学习（分类）统计学习方法分类无监督学习（聚类）统计学习方法分类半监督学习统计学习方法分类弱监督学习不完全监督：很少的标注样本统计学习方法分类弱监督学习不确切监督：标注对象不明确统计学习方法分类弱监督学习强化学习：试错和收益延迟统计学习方法本篇讲授内容监督学习无监督学习5.2朴素贝叶斯方法朴素贝叶斯方法是一种基于概率的分类方法基本思想：对于一个以若干特征表示的待分类样本，依次计算样本属于每个类别的概率，其中所属概率最大的类别作为分类结果输出贝叶斯方法

贝叶斯方法

独立性假设假设特征是独立的

朴素贝叶斯方法引入独立性假设后的贝叶斯方法称作朴素贝叶斯方法消除了特征取值的组合爆炸问题

举例：ID年龄发长鞋跟服装性别1老年短发平底深色男性2老年短发平底浅色男性3老年中发平底花色女性4老年长发高跟浅色女性5老年短发平底深色男性6中年短发平底浅色男性7中年短发平底浅色男性8中年长发高跟花色女性9中年中发高跟深色女性10中年中发平底深色男性11青年长发高跟浅色女性12青年短发平底浅色女性13青年长发平底深色男性14青年短发平底花色男性15青年中发高跟深色女性举例：ID年龄发长鞋跟服装性别1老年短发平底深色男性2老年短发平底浅色男性3老年中发平底花色女性4老年长发高跟浅色女性5老年短发平底深色男性6中年短发平底浅色男性7中年短发平底浅色男性8中年长发高跟花色女性9中年中发高跟深色女性10中年中发平底深色男性11青年长发高跟浅色女性12青年短发平底浅色女性13青年长发平底深色男性14青年短发平底花色男性15青年中发高跟深色女性

举例：ID年龄发长鞋跟服装性别1老年短发平底深色男性2老年短发平底浅色男性3老年中发平底花色女性4老年长发高跟浅色女性5老年短发平底深色男性6中年短发平底浅色男性7中年短发平底浅色男性8中年长发高跟花色女性9中年中发高跟深色女性10中年中发平底深色男性11青年长发高跟浅色女性12青年短发平底浅色女性13青年长发平底深色男性14青年短发平底花色男性15青年中发高跟深色女性

举例

平滑因样本不足可能存在的概率为0问题拉普拉斯平滑假设每一种情况都至少出现一次

拉普拉斯平滑举例：ID年龄发长鞋跟服装性别1老年短发平底深色男性2老年短发平底浅色男性3老年中发平底花色女性4老年长发高跟浅色女性5老年短发平底深色男性6中年短发平底浅色男性7中年短发平底浅色男性8中年长发高跟花色女性9中年中发高跟深色女性10中年中发平底深色男性11青年长发高跟浅色女性12青年短发平底浅色女性13青年长发平底深色男性14青年短发平底花色男性15青年中发高跟深色女性

朴素贝叶斯方法应用举例文本分类问题设有体育、财经、政治和军事4个新闻类别，新来一个新闻稿件，应该属于哪个类别呢？两个过程训练过程：计算概率分类过程：依据朴素贝叶斯方法对新来的稿件分类语料库的建立收集足够多的新闻稿件，每个稿件为一个训练样本，标注好所属的类别依据语料库计算概率朴素贝叶斯方法应用举例概率计算采用拉普拉斯平滑方法例如：

朴素贝叶斯方法应用举例概率计算以单词为特征例如：

朴素贝叶斯方法应用举例分类过程对数形式：

5.3决策树决策树是一种分类方法例：根据饮食习惯判断是哪里人一些概念树结构节点根节点叶节点：类别非叶节点：特征父节点子节点如何构建决策树？训练集（数据集）根据训练集构建一个决策树ID年龄发长鞋跟服装性别1老年短发平底深色男性2老年短发平底浅色男性3老年中发平底花色女性4老年长发高跟浅色女性5老年短发平底深色男性6中年短发平底浅色男性7中年短发平底浅色男性8中年长发高跟花色女性9中年中发高跟深色女性10中年中发平底深色男性11青年长发高跟浅色女性12青年短发平底浅色女性13青年长发平底深色男性14青年短发平底花色男性15青年中发高跟深色女性如何构建决策树同一个数据集可以构建不同的决策树如何构建决策树如何评价？决策树尽可能与训练集一致更好的泛化能力组合爆炸问题不可能建立所有可能的决策树，再从中选择一个最好的如何构建决策树启发式方法优先使用分类效果好的特征特征的效果依赖于数据集特征的评价数据集的熵熵是对数据集混乱程度的评价例：一个数据集中70%男生，30%女生一个数据集中50%男生，50%女生

特征的评价

特征的评价信息增益对数据集D实施特征A后，熵的下降程度信息增益可以评价特征的分类能力信息增益越大的特征分类能力越强信息增益越小的特征分类能力越弱

信息增益计算举例ID年龄发长鞋跟服装性别1老年短发平底深色男性2老年短发平底浅色男性3老年中发平底花色女性4老年长发高跟浅色女性5老年短发平底深色男性6中年短发平底浅色男性7中年短发平底浅色男性8中年长发高跟花色女性9中年中发高跟深色女性10中年中发平底深色男性11青年长发高跟浅色女性12青年短发平底浅色女性13青年长发平底深色男性14青年短发平底花色男性15青年中发高跟深色女性

5.3.1决策树算法——ID3算法ID3是一个按照信息增益选择特征的决策树算法基本思想：每次选择一个信息增益最大的特征，逐节点建立决策树ID3算法举例初始数据集D={1,2,…,15}ID年龄发长鞋跟服装性别1老年短发平底深色男性2老年短发平底浅色男性3老年中发平底花色女性4老年长发高跟浅色女性5老年短发平底深色男性6中年短发平底浅色男性7中年短发平底浅色男性8中年长发高跟花色女性9中年中发高跟深色女性10中年中发平底深色男性11青年长发高跟浅色女性12青年短发平底浅色女性13青年长发平底深色男性14青年短发平底花色男性15青年中发高跟深色女性

ID3算法举例年龄特征的条件熵按照年龄取值将D划分为3个子集{1,2,3,4,5},{6,7,8,9,10},{11,12,13,14,15}分别计算三个子集的熵：年龄的条件熵：ID年龄发长鞋跟服装性别1老年短发平底深色男性2老年短发平底浅色男性3老年中发平底花色女性4老年长发高跟浅色女性5老年短发平底深色男性6中年短发平底浅色男性7中年短发平底浅色男性8中年长发高跟花色女性9中年中发高跟深色女性10中年中发平底深色男性11青年长发高跟浅色女性12青年短发平底浅色女性13青年长发平底深色男性14青年短发平底花色男性15青年中发高跟深色女性

ID3算法举例年龄特征的信息增益ID年龄发长鞋跟服装性别1老年短发平底深色男性2老年短发平底浅色男性3老年中发平底花色女性4老年长发高跟浅色女性5老年短发平底深色男性6中年短发平底浅色男性7中年短发平底浅色男性8中年长发高跟花色女性9中年中发高跟深色女性10中年中发平底深色男性11青年长发高跟浅色女性12青年短发平底浅色女性13青年长发平底深色男性14青年短发平底花色男性15青年中发高跟深色女性

ID3算法举例发长特征的条件熵按照发长取值将D划分为3个子集{1,2,5,6,7,12,14},{3,9,10,15},{4,8,11,13}分别计算三个子集的熵：发长的条件熵：ID年龄发长鞋跟服装性别1老年短发平底深色男性2老年短发平底浅色男性3老年中发平底花色女性4老年长发高跟浅色女性5老年短发平底深色男性6中年短发平底浅色男性7中年短发平底浅色男性8中年长发高跟花色女性9中年中发高跟深色女性10中年中发平底深色男性11青年长发高跟浅色女性12青年短发平底浅色女性13青年长发平底深色男性14青年短发平底花色男性15青年中发高跟深色女性

ID年龄发长鞋跟服装性别1老年短发平底深色男性2老年短发平底浅色男性3老年中发平底花色女性4老年长发高跟浅色女性5老年短发平底深色男性6中年短发平底浅色男性7中年短发平底浅色男性8中年长发高跟花色女性9中年中发高跟深色女性10中年中发平底深色男性11青年长发高跟浅色女性12青年短发平底浅色女性13青年长发平底深色男性14青年短发平底花色男性15青年中发高跟深色女性ID年龄发长鞋跟服装性别1老年短发平底深色男性2老年短发平底浅色男性3老年中发平底花色女性4老年长发高跟浅色女性5老年短发平底深色男性6中年短发平底浅色男性7中年短发平底浅色男性8中年长发高跟花色女性9中年中发高跟深色女性10中年中发平底深色男性11青年长发高跟浅色女性12青年短发平底浅色女性13青年长发平底深色男性14青年短发平底花色男性15青年中发高跟深色女性ID年龄发长鞋跟服装性别1老年短发平底深色男性2老年短发平底浅色男性3老年中发平底花色女性4老年长发高跟浅色女性5老年短发平底深色男性6中年短发平底浅色男性7中年短发平底浅色男性8中年长发高跟花色女性9中年中发高跟深色女性10中年中发平底深色男性11青年长发高跟浅色女性12青年短发平底浅色女性13青年长发平底深色男性14青年短发平底花色男性15青年中发高跟深色女性ID3算法举例发长特征的信息增益ID年龄发长鞋跟服装性别1老年短发平底深色男性2老年短发平底浅色男性3老年中发平底花色女性4老年长发高跟浅色女性5老年短发平底深色男性6中年短发平底浅色男性7中年短发平底浅色男性8中年长发高跟花色女性9中年中发高跟深色女性10中年中发平底深色男性11青年长发高跟浅色女性12青年短发平底浅色女性13青年长发平底深色男性14青年短发平底花色男性15青年中发高跟深色女性

ID3算法举例同理得到鞋跟、服装的信息增益对比4个特征的信息增益ID年龄发长鞋跟服装性别1老年短发平底深色男性2老年短发平底浅色男性3老年中发平底花色女性4老年长发高跟浅色女性5老年短发平底深色男性6中年短发平底浅色男性7中年短发平底浅色男性8中年长发高跟花色女性9中年中发高跟深色女性10中年中发平底深色男性11青年长发高跟浅色女性12青年短发平底浅色女性13青年长发平底深色男性14青年短发平底花色男性15青年中发高跟深色女性

ID3算法举例选择鞋跟特征，将数据集D划分为D1、D2

ID年龄发长鞋跟服装性别1老年短发平底深色男性2老年短发平底浅色男性3老年中发平底花色女性4老年长发高跟浅色女性5老年短发平底深色男性6中年短发平底浅色男性7中年短发平底浅色男性8中年长发高跟花色女性9中年中发高跟深色女性10中年中发平底深色男性11青年长发高跟浅色女性12青年短发平底浅色女性13青年长发平底深色男性14青年短发平底花色男性15青年中发高跟深色女性ID3算法举例

ID年龄发长鞋跟服装性别1老年短发平底深色男性2老年短发平底浅色男性3老年中发平底花色女性4老年长发高跟浅色女性5老年短发平底深色男性6中年短发平底浅色男性7中年短发平底浅色男性8中年长发高跟花色女性9中年中发高跟深色女性10中年中发平底深色男性11青年长发高跟浅色女性12青年短发平底浅色女性13青年长发平底深色男性14青年短发平底花色男性15青年中发高跟深色女性

ID3算法举例

ID年龄发长鞋跟服装性别1老年短发平底深色男性2老年短发平底浅色男性3老年中发平底花色女性4老年长发高跟浅色女性5老年短发平底深色男性6中年短发平底浅色男性7中年短发平底浅色男性8中年长发高跟花色女性9中年中发高跟深色女性10中年中发平底深色男性11青年长发高跟浅色女性12青年短发平底浅色女性13青年长发平底深色男性14青年短发平底花色男性15青年中发高跟深色女性ID3算法举例

ID年龄发长鞋跟服装性别1老年短发平底深色男性2老年短发平底浅色男性3老年中发平底花色女性4老年长发高跟浅色女性5老年短发平底深色男性6中年短发平底浅色男性7中年短发平底浅色男性8中年长发高跟花色女性9中年中发高跟深色女性10中年中发平底深色男性11青年长发高跟浅色女性12青年短发平底浅色女性13青年长发平底深色男性14青年短发平底花色男性15青年中发高跟深色女性

ID3算法举例

ID年龄发长鞋跟服装性别1老年短发平底深色男性2老年短发平底浅色男性3老年中发平底花色女性4老年长发高跟浅色女性5老年短发平底深色男性6中年短发平底浅色男性7中年短发平底浅色男性8中年长发高跟花色女性9中年中发高跟深色女性10中年中发平底深色男性11青年长发高跟浅色女性12青年短发平底浅色女性13青年长发平底深色男性14青年短发平底花色男性15青年中发高跟深色女性ID3算法举例

ID年龄发长鞋跟服装性别1老年短发平底深色男性2老年短发平底浅色男性3老年中发平底花色女性4老年长发高跟浅色女性5老年短发平底深色男性6中年短发平底浅色男性7中年短发平底浅色男性8中年长发高跟花色女性9中年中发高跟深色女性10中年中发平底深色男性11青年长发高跟浅色女性12青年短发平底浅色女性13青年长发平底深色男性14青年短发平底花色男性15青年中发高跟深色女性

ID3算法举例ID年龄发长鞋跟服装性别1老年短发平底深色男性2老年短发平底浅色男性3老年中发平底花色女性4老年长发高跟浅色女性5老年短发平底深色男性6中年短发平底浅色男性7中年短发平底浅色男性8中年长发高跟花色女性9中年中发高跟深色女性10中年中发平底深色男性11青年长发高跟浅色女性12青年短发平底浅色女性13青年长发平底深色男性14青年短发平底花色男性15青年中发高跟深色女性

ID3算法举例

ID年龄发长鞋跟服装性别1老年短发平底深色男性2老年短发平底浅色男性3老年中发平底花色女性4老年长发高跟浅色女性5老年短发平底深色男性6中年短发平底浅色男性7中年短发平底浅色男性8中年长发高跟花色女性9中年中发高跟深色女性10中年中发平底深色男性11青年长发高跟浅色女性12青年短发平底浅色女性13青年长发平底深色男性14青年短发平底花色男性15青年中发高跟深色女性ID3算法举例ID年龄发长鞋跟服装性别1老年短发平底深色男性2老年短发平底浅色男性3老年中发平底花色女性4老年长发高跟浅色女性5老年短发平底深色男性6中年短发平底浅色男性7中年短发平底浅色男性8中年长发高跟花色女性9中年中发高跟深色女性10中年中发平底深色男性11青年长发高跟浅色女性12青年短发平底浅色女性13青年长发平底深色男性14青年短发平底花色男性15青年中发高跟深色女性

5.3.2决策树算法——C4.5算法C4.5是对ID3决策树算法改进ID3算法存在的问题倾向于选择取值多的特征当特征取值多时，D被划分为多个子数据集，每个子数据集中的样本数可能比较少，里面只包含单一类别样本的可能性就比较大，这样就会导致条件熵比较小，从而使得信息增益比较大极限情况下，特征A的取值特别多，以至于每个样本都有一个不同的取值，这样每个子数据集就只含有一个样本，每个子数据集的类别都是确定的。比如：以毫米为单位的发长特征本质上还是数据量不足

C4.5算法改进思想“相对”信息增益——信息增益率用信息增益率代替信息增益选择特征分离信息也是一种熵按照特征取值计算概率

C4.5算法信息增益率计算举例

ID年龄发长鞋跟服装性别1老年短发平底深色男性2老年短发平底浅色男性3老年中发平底花色女性4老年长发高跟浅色女性5老年短发平底深色男性6中年短发平底浅色男性7中年短发平底浅色男性8中年长发高跟花色女性9中年中发高跟深色女性10中年中发平底深色男性11青年长发高跟浅色女性12青年短发平底浅色女性13青年长发平底深色男性14青年短发平底花色男性15青年中发高跟深色女性

C4.5算法

C4.5算法计算举例ID发长（厘米）类别12男性24男性310女性420女性

C4.5算法

ID发长（厘米）类别12男性24男性310女性420女性

C4.5算法

ID发长（厘米）类别12男性24男性310女性420女性

C4.5算法注意：特征取连续值时，并不是只能使用一次。发长>7?D1是不是D2C4.5的不足倾向于取值不平衡的特征改进方法从n个信息增益大的特征中选择信息增益率最大的特征n的确定：信息增益大于平均值的特征5.3.3决策树：过拟合与剪枝过拟合问题决策树节点数错误率训练集错误率验证集错误率恰拟合过拟合欠拟合N剪枝方法DD2D1D22D21D23D12D11D13DD2D1D22D21D23如何评价剪枝是否有效？

剪枝方法举例

剪枝方法举例

简直方法举例

剪枝方法举例5.3.4随机森林算法决策森林“三个臭皮匠顶个诸葛亮”随机森林利用有限数据建立尽可能不同的决策树重复采样特征采样…数据采样决策树决策树决策树特征采样特征采样特征采样随机森林投票机制随机森林森林大小太小投票机制作用有限太大决策树之间缺乏独立性合适的大小错误率最小集外数据的利用集外数据约占37%利用集外数据测试错误率确定最小错误率时的森林大小重复采样约37%不被采集5.4k近邻方法k近邻一种分类方法基本思想物以类聚相近的样本属于同一个类别的概率大发长鞋跟高度男性女性xyba男性女性k近邻方法存在噪声时变得不可靠解决办法：看周围k个样本发长鞋跟高度男性女性xak近邻方法k值的影响发长鞋跟高度男性女性xk=1,女性k=3，男性k=5，女性k=11，男性距离计算

k近邻方法举例ID特征1特征2特征3类别10.71.20.9a21.51.30.8a31.10.81.2a40.91.10.7a51.21.41.3a60.23.50.3b70.34.10.7b80.33.21.2b90.12.80.5b100.73.31.1b112.80.21.1c123.10.51.5c134.51.21.3c144.10.90.9c152.90.71.2cx=(3.5,3.3,0.8)？距离3.502.833.493.413.023.343.303.233.452.823.192.912.382.482.70排序155141271110913486123k近邻方法的特点是一种不需要训练的方法直接存储训练样本简单有效当训练样本足够多时具有比较好的性能效率问题需要计算与每个样本的距离5.5支持向量机（SVM）什么是支持向量机？一种分类方法适用于二分类可以通过多个支持向量机的组合实现多分类支持向量机yxABCD最大间隔yABx间隔间隔最大间隔最优分界面支持向量与支持向量机yxAabcdea、b、c、d、e称作支持向量，唯一决定了最优分界面。这样得到的二分类器称作支持向量机。几个基本概念

几个基本概念决策函数

yAabcde

x正类负类yAabcde

x正类负类几个基本概念

几个基本概念函数间隔的特点超平面方程与函数间隔同一个超平面可以对应不同的函数间隔

几个基本概念几何间隔归一化的函数间隔实质就是点到平面的欧氏距离

几个基本概念几何间隔与函数间隔的关系训练集T到超平面(w.b)的函数间隔训练集T到超平面(w.b)的几何间隔

5.5.2线性可分支持向量机支持向量机分类线性可分支持向量机线性支持向量机非线性支持向量机线性可分支持向量机yAx

线性可分支持向量机给定训练集T：求解：用函数间隔表示：

线性可分支持向量机

线性可分支持向量机线性可分支持向量机求解

线性可分支持向量机求解

满足约束条件时≤0

>0

线性可分支持向量机求解原始问题：对偶问题：一般来说二者并不等价例：A、B最高，C、D最小，并假定B年龄小于A，C身高大于D身高最高的同学中年龄最小的同学：B年龄最小的同学中身高最高的同学：C年龄角度、身高角度均有：C≤B

线性可分支持向量机求解

对偶问题原始问题线性可分支持向量机求解

KKT条件在满足KKT条件下，原始问题与对偶问题等价线性可分支持向量机求解

KKT条件在满足KKT条件下，原始问题与对偶问题等价线性可分支持向量机求解

线性可分支持向量机求解

线性可分支持向量机求解

线性可分支持向量机求解

线性可分支持向量机求解如何得到超平面方程？

求解举例例：

设有正样本x1=(3,3)、x2=(4,3)，y1=y2=1，负样本x3=(6,4)，y3=-1

求该问题的最优分界面，并据此给出样本(1,1)所属的类别。

最小值在边界上

样本x=(1,1)为正类☆回顾：线性可分支持向量机5.5.3线性支持向量机yx函数间隔0.9函数间隔0.1abc

线性支持向量机

线性支持向量机

线性支持向量机yx函数间隔=1

总结

5.5.4非线性支持向量机

非线性支持向量机

非线性支持向量机原空间的椭圆方程变换后的空间成为平面方程

非线性支持向量机线性支持向量机新空间超平面方程

非线性支持向量机

举例设x1=(0,0)、x2=(1,1)属于正类，x3=(1,0)，x4=(0,1)属于负类选择变换

11

非线性支持向量机

5.5.5核函数与核方法回顾：非线性支持向量机

核函数

核方法求解非线性支持向量机通过核函数在原空间计算变换后空间的点积不需要知道变换函数非线性支持向量机

变换后空间的超平面原始空间的超曲面决策函数

常用核函数多项式核函数最优分界超曲面方程分类决策函数

常用核函数高斯核函数最优分界超曲面方程分类决策函数

常用核函数sigmoid核函数最优分界超曲面方程分类决策函数

支持向量机的过拟合问题

举例

待分类样本x=(0,1)所属的类别：

待分类样本x=(0,1)为负类

x1x2x311-1-1

支持向量机总结非线性支持向量机线性支持向量机线性可分支持向量机

5.5.6支持向量机用于多分类问题支持向量机是二分类器如何求解多分类问题呢？支持向量机用于多分类问题

一对一法示意图类2、类3分类器类2得1票、类3的2票类2得2票、类3的1票类3类1

类2类3类2类1

一对一法的特点

支持向量机用于多分类问题一对多法K个类别，每个类别做正类，其余K-1个类别合并在一起做负类，共构建K个支持向量机类2类3类1

xzy红色：正蓝色：负类2类3类1

一对多法的特点比较少的分类器K（>3）个类别，K个分类器样本不平衡问题正类少，负类多解决方法对正负两类样本设置不同的参数C

支持向量机用于多分类问题层次法从根节点开始，每次划分为两个类别类1～类4类1～类2类3～类4类1类2类3类4层次法的特点

附录B支持向量机求解算法SMO

B.1SMO算法的基本思想梯度下降法

梯度下降法示意图SMO算法的基本思想

SMO算法的基本思想坐标下降法一次只修改一个变量SMO算法的基本思想

坐标下降法示意图

SMO算法的基本思想

SMO算法的基本思想

SMO算法的基本思想

裁剪方法

裁剪方法

裁剪方法

裁剪方法

裁剪方法

裁剪方法

裁剪方法

SMO算法KKT条件y

SMO算法基本思想小结

B.2SMO算法的详细计算过程

根据上一讲的结果：

更新偏置b

更新偏置b

更新偏置b

更新偏置b

根据定义：有：

SMO算法5.6K均值聚类算法聚类问题按形状按大小按颜色c聚类结果与选择的特征有关K均值聚类算法几个类别？朴素的想法类内样本越是紧密地簇

拥在一起聚类效果越好如何衡量？类别内样本之间的距离K均值聚类算法

K均值聚类算法

K均值聚类算法N个样本数、K个类别，所有可能的聚类方案数（含一个类别中样本为0的情况）

……N个样本K个类别每个样本K个可能有K!种排列

K均值聚类算法如何做到J最小？当知道类中心时，每个样本归到最近的类中心如何得到类中心？

K均值聚类算法

K均值聚类举例

假定选择x1、x2、x3分别为类1、类2、类3的中心聚类结果第一类：x1第二类：x2、x5第三类：x3、x4、x6

x1x2x3x4x5x6类10126362934类21025372025类3262502252020202000

聚类结果第一类：x1第二类：x2、x5第三类：x3、x4、x6

类中心第一类：(2,2)第二类：(3,5)第三类：(6.7,4)

24682468(2,3)(2,2)(8,2)(7,3)(4,7)(5,7)

(3,5)(6.7,4)类1类3类2

x1x2x3x4x5x6类10126362934类2105203458类325.822.81.15.816.111.8类中心第一类：(2,2)，第二类：(3,5)，第三类：(6.7,4)

聚类结果第一类：x1、x2第二类：x5

、x6第三类：x3、x4011.15.858

24682468(2,3)(2,2)(8,2)(7,3)(4,7)(5,7)

(3,5)(6.7,4)类1类3类2聚类结果第一类：x1、x2第二类：x5

、x6第三类：x3、x4

24682468(2,3)(2,2)(8,2)(7,3)(4,7)(5,7)

(4.5,7)(7.5,2.5)类1类3类2(2,2.5)二分K均值聚类算法K均值算法存在的问题聚类结果与初始选择的类别中心有关采用多次聚类选择J值最小的聚类结果效率问题二分K均值聚类算法先聚类两个类别从已有聚类结果中选择一个类别将其聚类成两个类别直到得到K个类别为止可一定程度上缓解初始类别中心选择问题二分K均值聚类算法如何选择一个类别再聚类？选择使J值最大降低的类别如何确定K？最小化J？一个样本一个类别时J=0

No！如何确定K？拐点法逐渐增加K值，寻找J下降的拐点K选择为45.7层次聚类算法数据的层次性层次聚类算法自底向上聚类初始化：每个样本为一个类别合并两个最相似的类别重复第2步，直到聚成了K个类别或者聚成一个类别为止。层次聚类示意图层次聚类算法层次聚类算法举例abcdefgh距离度量中心距离法以两个类别中心的距离作为两个类别之间距离的度量平均距离法以两个类别中任意两个样本间距离的平均值作为两个类别之间距离的度量（两个样本分别来自不同的类别）。最小距离法以两个类别中任意两个样本间距离的最小值作为两个类别之间距离的度量（两个样本分别来自不同的类别）。最大距离法以两个类别中任意两个样本间距离的最大值作为两个类别之间距离的度量（两个样本分别来自不同的类别）。最小距离法与最大距离法效果对比最小距离法最大距离法5.8DBSCAN聚类算法数据有梳有密、形态不一可能含有噪声DBSCAN：一种基于密度的聚类方法DBSCAN聚类算法如何评价一个样本所处位置的密度？DBSCAN聚类算法核心样本以某个样本p为圆心、r为半径做圆，圆内至少包含有minPts个样本，则称p为核心样本。圆内的任一样本q称作被p包含，或者说q相对p来说直接可达。DBSCAN聚类算法边界样本被核心样本包含的非核心样本称作边界样本DBSCAN聚类算法异常样本如果一个样本既不是核心样本，也不被任何核心样本所包含，则称该样本为异常样本。异常样本说明该样本处于一个比较稀疏的区域，大概率是一个噪声样本。DBSCAN聚类算法选取一个核心样本p，将p所包含的所有样本加入到类c中，标记样本p被处理过从类c中依次选取没有处理过的核心样本q，并将q所包含的样本加入到类c中，标记样本q被处理过在这个过程中，类c中的样本逐渐增加，新增加的样本有核心样本也有非核心样本重复以上过程，直到类c中所有核心样本被标记处理过，则完成了第一个类别的聚类，类c中的所有样本为一个类别再选取一个没有被处理过的核心样本，按照上述方法完成聚类依次进行下去，直到所有的核心样本被处理完，则结束聚类，剩下的异常样本被认作是噪声DBSCAN聚类算法——举例假定minPts=3

给定了半径rabcdefghijkmnabcdefghijkmn核心样本：c类1：c,d,e类1：c,d,e类1：c,d,e,f类1：c,d,e,f,g类1：c,d,e,f,gabcdefghijkmn核心样本：j类2：j,i,k类2：j,i,k,m类1：c,d,e,f,g类2：j,i,k类2：j,i,k,mabcdefghijkmn类1：c,d,e,f