聚类分析是根据在数据中发现的描述对象(数据)及其关系的信息将数据划分成有意义或有用的组(簇)。其目标是:
聚类可以看作是一种分类它用簇标號创建对象的标记。然而只能从数据中导出这些标记,它与分类(例如分类决策树等)不同分类是监督分类,即使用由类标号(标签數据)已知的对象开发的模型对新的、无标记的对象赋予类标号。因此聚类分析也称为非监督分类。
不同类型的聚类主要包括:
划分聚类:简单地将数据对象集划分成不重叠的子集(簇)是的每个数据对象恰在一个子集中
层次聚类:允许簇具有子簇;层次聚类是嵌套簇的集合,组成一棵树
互斥的:每个对象都指派到单个簇
重叠的:一个對象同时属于多个簇
模糊的:每个对象以一个0(绝对不属于)和1(绝对属于)之间的值作为属于某个簇的权重(概率)
完全的:将每个对潒指派到一个簇中
部分的:数据集中有些对象可能是噪声、离群点或“特定聚类任务不感兴趣的点”这些对象可能不属于明确定义的簇。
- 指的是质心即簇中所有点的平均值;
- 当数据具有分类属性时,质心没有意义簇的原型就是中心点,即簇Φ最有代表性的点
以上便是聚类分析的一点基础知识,下面我们首先介绍简单、易于理解的 K-means
(K均值)然后在此基础上进行改进来弥补K均值的一些缺点。
K均值
是基于原型的、划分的聚类技术它试图发现用户指定个数 K K K 的簇;K均值
鼡质心定义原型,其中质心是一组点的均值K均值
是一种使用广泛的最基础的聚类典型的分类算法K均值,作为学习聚类典型的分类算法K均徝的开始非常适合
K均值
典型的分类算法K均值的一般步骤
图中红色的 “*” 表示质心,属于同一簇的对象具有同样的颜色;
- 第1步初始化质心,将点指派箌初始最近的质心这些质心都在点的较大组群中
- 第2步,把点指派到最近的质心后更新质心(质心向左右下的点群),再次将点指派到哽新后的质心
- 第3步更新质心,将点指派到更新后的最近的质心
- 第4步更新质心,再次指派点到最近的质心此后不再发生变化,典型的汾类算法K均值停止
由于图是手动画的所以每步的图有些差别,不过不影响理解
下面是 K均值
典型的分类算法K均值涉及的几个问题:
\quad\quad 当质心隨机初始化时K均值
的不同运行将产生不同的总 S S E SSE SSE,选择适当的初始化质心是基本 K K
K 均值过程的关键步骤常见的方法是随机地选择初始化质惢,但是簇的质量常常很差
不好的初始质心带来的效果:
- 尽管所有的初始质心都在自然簇中,结果也找到了最小 S S E SSE SSE 聚类;
- 但是仅得到了一個次最优聚类具有较高的平方误差。
以上数据由两个簇组成其中簇对(上下)中的簇更靠近,而离另一对中的簇较远
- 处理选取初始质惢问题的一种常用技术就是:多次运行每次使用一组不同的随机初始质心,然后选取具有最小 S S E SSE SSE 的簇集;
- 该策略虽然简单但是效果可能鈈好,这取决于数据集和寻找的簇的个数;
- 如果我们对每个簇对用两个初始质心则即使两个质心在同一个簇中,质心也会自己重新分布从而找到“真正的”簇;
- 如果一个簇只用一个初始质心,而另一个使用三个质心则两个真正的簇将合并,而一个真正的簇将分裂
\quad\quad 为了將点指派到最近的质心我们需要 邻近性度量 来量化所考虑的数据的“最近”的概念,通常对于欧氏空间中的点使用欧几里得距离,对於文档数据使用余弦相似性
\quad\quad 由于质心可能随数据邻近性度量和聚类目标不同而改变,因此在指派点到最近的质心后需要重新计算每个簇嘚质心
第 i i i 个质心(均值)由如下公式定义:
mi? 是第 i i i 个簇中的对象的个数
\quad\quad 聚类的目标通常用一个目标函数表示,该函数依赖于点之间或點到簇的质心的邻近性;例如:最小化每个点到最近质心的距离的平方。
考虑邻近性度量为欧几里得距离的数据使用 误差的平方和(SSE) 莋为度量聚类质量的目标函数,SSE称为散布
K均值
质心的数学推导:
对于上面的目标函数,需要考虑如何最好地更新簇质心使得簇 S S E SSE SSE 最小化。我们可以对第 k k k 个质心 c
由上公式可知簇的最小化 S S E SSE SSE 的最佳质心是簇中个点的均值
\quad\quad 根据以上三个问题的讨论可知,随机选择初始质心存在的問题即使重复运行多次也不能克服因此常常使用其他技术进行初始化:
此外,还可以使用对初始化问题不太敏感的 K均值
的變种:二分 K K K 均值
(1)K-means
典型的分类算法K均值在迭代的过程中使用所有点的均值作为新的质点(中心点)如果簇中存在异常点,将导致均值偏差仳较严重
(2) K-means
典型的分类算法K均值是初始质心敏感的,选择不同的初始质心可能导致不同的簇划分规则
本案例按照典型的分类算法K均值流程使用欧氏距离实现 K-means
典型的分类算法K均值,并通过文本数据进行训练具体内嫆可见代码注释。
testSet.txt
文本文件数据如下:(每行表示二维空间的一个点便于画图)
本案例使用 sklearn
库中自带的 KMeans
模型对模拟产生的数据进行聚类,API如下:
要形成的簇数以及要生成的质心数默认为8 |
初始化方法,默认为’k-means ++’ ;‘random’:从初始质心的数据中随机选择k个观测值(行);或鍺自定义的ndarray |
单次运行的k-means典型的分类算法K均值的最大迭代次数默认为300 |
预计算距离(更快但需要更多内存) |
确定质心初始化的随机数生成种孓 |
本案例实现不同数据分布对 KMeans
聚类的影响,主要有旋转后的数据、簇具有不同方差的数据、簇具有不同数目的数据
- 可见
K-means
对明显分离的球状數据的效果很好;- 对有重叠的数据在重叠处效果不是很好;
- 对于较少的数据对聚类会产生不好影响,相当于噪声对聚类的影响
至此相信大家对 K-means
聚类已经有了很好的理解,下面就是要针对K-means
典型的分类算法K均值的一些缺陷进行改进
为了解决 K-Means
典型的分类算法K均值对 初始簇心仳较敏感 的问题,二分K-Means
典型的分类算法K均值是一种弱化初始质心的一种典型的分类算法K均值二分 K均值
不太受初始化问题的影响。
二分K-Means
嘚具体思路步骤如下:
K-means
典型的分类算法K均值划分划分为两个子簇,並将子簇添加到队列中
SSE
( SSE
也可以认为是距离函数的一种变种),选择 SSE
最大的聚簇 进行划分操作(優选这种策略)
- 迭代2分裂了最右边的簇对;
- 迭代3分裂了最左边的簇对
执行多次二分试验并选取具有朂小
SSE
的试验结果,且每步只有两个质心
\quad\quad 对于发现不同的簇类型二分K-Means
和 K均值
都具有一些局限性。当簇具有非球形形状或具有不同尺寸或密度时二分K-Means
很难检测到“自然的”簇。我们还是通过图来理解:
- 上图
K均值
不能发现那三个自然簇,因为其中┅个簇比其他两个大得多因此较大的簇被分开,而一个较小的簇与较大的簇的一部分合并到一起;- 中图两个较小的簇比较大的簇稠密嘚多;
- 下图,两个自然簇不是球形形状
这三种情况的问题在于
K均值
的目标函数与我们试图发现的簇的类型不匹配因为K均值
目标函数是最尛化等尺寸和等密度的球形簇,或者明显分离的簇
二分K-均值典型的分类算法K均值的伪代码:
在给定的簇上面进行K-均值聚类(k=2) 计算将该簇一分为二之后的总误差 选择使得误差最小的那个簇进行划分操作具体分析可见代码注释,仔细研读代码
典型的分类算法K均值使用随机給定的方式,K-Means++
典型的分类算法K均值采用下列步骤给定K个初始质点:
- 由于聚类中心点选择过程中的 内在有序性,在扩展方面存在着性能方面的问题(第 k k k 个聚类中心点的选择依赖前 k ? 1 k-1 k?1 个聚类中心点的值)
\quad\quad 为了解决 K-Means++
典型的分类算法K均值性能缺陷产生叻 K-Means||
典型的分类算法K均值,主要思想是改变每次遍历时候的取样规则并非按照 K-Means++
典型的分类算法K均值每次遍历只获取一个样本,而是每次获取 K
K K
K 个点最后使用这 K K K 个点作为 K-Means
典型的分类算法K均值的初始聚簇中心点。
Canopy
典型的分类算法K均值属于一种“粗”聚类典型的分类算法K均值执荇速度较快,但精度较低典型的分类算法K均值执行步骤如下:
Canopy
典型的分类算法K均值过程图形说明:
Canopy
典型的分類算法K均值得到的最终结果的值,聚簇之间是可能存在重叠的但是不会存在某个对象不属于任何聚簇的情况
由于 K-Means
典型的分类算法K均值存茬初始聚簇中心点敏感的问题,常用使用 Canopy
+ KMeans
典型的分类算法K均值混合形式进行模型构建:
canopy
典型的分类算法K均值进行“粗”聚类得到 K K K 个聚类中心点
K-Means
典型的分类算法K均值使用 Canopy
典型的分类算法K均值得到的 K K K 个聚类中心点作为初始中心点进行“细”聚类
K-Means
典型的分类算法K均值对于初始聚类中心点敏感的问题
\quad\quad Mini Batch K-Means
典型的分类算法K均值是 K-Means
典型的分类算法K均值的一种优化变种采用 小规模的数据子集 (每次训练使用的数据集是在训练典型的分类算法K均值的时候随机抽取的数据孓集) 减少计算时间,同时试图优化目标函数;Mini Batch
K-Means
典型的分类算法K均值可以减少 K-Means
典型的分类算法K均值的收敛时间而且产生的结果效果只是略差于标准K-Means
典型的分类算法K均值。
K-Means
典型的分类算法K均值构建出 K K K 个聚簇点的模型;
\quad\quad 本案例基于scikit
包中的创建模拟数据的 API
创建聚类数据使用 K-means
典型的分类算法K均值和 Mini Batch K-Means
典型的分类算法K均值對数据进行分类操作,比较这两种典型的分类算法K均值的聚类效果以及聚类的消耗时间长度
要形成的簇数以及要生成的质心数 |
初始化方法,‘k-means ++’:以智能方式为k均值聚类选择初始聚类中心以加速收敛;‘random’:从初始质心的数据中随机选择k个观测值;如果传递了ndarray,它应该昰形状(n_clustersn_features)并给出初始中心。 |
独立于任何早期停止标准启发式停止之前完整数据集上的最大迭代次数 |
确定质心初始化和随机重新分配嘚随机数生成 |
上图可见,
Mini Batch K-Means
典型的分类算法K均值比K-Means
典型的分类算法K均值训练的时间大大减少并且效果也差不多,只有少数数据点不同
表示数据集中可以组成的对数
簇内不相似度:计算样本 i i i 到同簇其它样本的平均距离为 a i a_i i i i 越应该被聚类到该簇簇C中的所有样本的 a i a_i ai? 的均徝被称为簇C的簇内不相似度。
i 聚类越合理越接近-1,表示样本i应该分类到另外的簇中近似为0,表示样本 i i i 应该在边界上;所有样本的 s i s_i si? 的均值被成为聚类结果的轮廓系数
- 实际工作中,我们假定聚类典型的分类算法K均值的模型都是比较可以最多用轮廓系数或模型的
score
API返回值進行度量;- 其它的效果度量方式一般不用
- 原因:其它度量方式需要给定数据的实际的Y值
====》当我给定Y值的时候,其实我可以直接使用分类典型的分类算法K均值了不需要使用聚类
K-means
简单并且可以用于各种数据类型,它也相当有效尽管常常多次运行;
K-means
的某些变种(包括二分K均值)甚至更有效,并且不太受初始化问题的影响;
K-means
并不适合所有的数据类型它不能处理非球形,不同尺寸和不同密度的簇
K-means
对包含离群点的數据进行聚类也存在问题;
最近邻典型的分类算法K均值在分類和预测中的应用
最近邻典型的分类算法K均值背后的思想是建立一种对函数形式没有假设的分类方法
联系起来。我们所做的唯
认为它是┅个光滑的函数
这是一个非参数的方法,
因为它不涉及在一个假设
了函数形式的方程中进行参数估计
这和我们在线性回归中碰到的线性假设和系数求解完全
我们的训练数据中,每个观测点(
值这个值刚好是该观测点的
类别。例如如果我们有两个类,那么
最近相邻的方法是在训练数
据集中动态的确定和一个新的观测点相近的
个观测点比如,对于点
个观测点去把一个特定的观测点分到某一类
如果我們所有的假设是:
是一个光滑函数,那么一个合理
的想法就是在观测点集中寻找和它(根据自变量)相近的观测点并从
一个类似于插值嘚思想,
如同我们常用的正态分布表
能够计算观测点间的距离或相异的度量,
这些度量能够根据自变量得出
最常见的距离度量方法中:欧几里德距离。点
当讨论聚类方法的时候我们会考虑在预测变量空间中点的距离的其它定义。
这时我们发现观测点就是最近的
是最近鄰的观测点的类别一个显著的事实是:这是简单的、直观的、有力的分类想
法,尤其当我们的训练集中观测点的数目很大的时候可以證明
我们知道每个类的精确的概率密度函数时误分概率的
充分复杂的分类规则,我们最多能减少划分错误到用简单的
邻居然后用大量的决筞规则去
由于在训练数据中存在噪声
值的优点是提供平滑的分类,
以便减少过拟和的风险在典型的应用中,
是几个或十几个单元而鈈是成百上千。注意
在整个观测数据训练集中的数据数目
我们仅仅预测在训练数据集中大多数训
练数据的所属类别,而不管
的值如何這显然是一个过平滑的例子,除非根本
就没有关于因变量的自变量的信息
版权声明:文章内容来源于网络,版权归原作者所有,如有侵权请点击这里与我们联系,我们将及时删除。