聚类分析和判别分析 - YUANya

时间:2024-03-02 19:49:00

13聚类分析和判别分析

==================================

聚类分析

什么是聚类分析?

聚类:数据对象的集合

在同一集群内彼此相似

与其他集群中的对象不同

==================================

聚集分析

将一组数据对象分组为群集,即为分组

聚类是无监督的分类:没有预定义的类。

典型应用

作为了解数据分布的独立工具。

作为其它算法的预处理步骤

=================================

什么是好的聚类?

良好的聚类方法将产生高质量的簇,

类内相似性

类间相似性

聚类结果的质量取决于相似性度量,即相似性要求高聚类的质量就差。

聚类方法的质量也通过它发现一些或全部隐藏模式的能力来测量,即是否在组中发现隐藏模式如果有隐藏模式则聚类效果差。

====================================

测度聚类质量

不同/相似度量:相似性用距离函数表示,距离函数通常是度量:d(ij)

对于布尔变量、范畴变量、序数变量、区间缩放变量和比率变量,距离函数的定义通常有很大的不同。

权重应该根据应用程序和数据语义与不同的变量相关联。

很难定义足够相似足够好”--答案通常是高度主观的。

聚类方法

 

 

 

数据结构

数据矩阵

 

 

 

相异矩阵

 

 

 

==========================================

分区算法:基本概念

分区方法:N个对象的数据库D的分区构造成一组K个簇

给定一个k,找到一个k簇的分区,以优化所选的分区准则。

全局最优:彻底枚举所有分区

启发式方法:K-meank-medoid算法

k-means:每个群集由群集的中心表示

K-medoidPAM(围绕medoid的分区):每个集群由集群中的一个对象表示

==========================================

K-means聚类

基本思路:使用集群中心(表示)表示集群。

将数据元素分配给收敛集群(中心)

目标:尽量减少平方误差(类内差异)

 

给定kk-均值算法分四个步骤实现:

将对象划分为k个非空子集

计算种子点作为当前分区的群集的质心(质心为中心,即群集的平均点)

 

使用最近的种子点将每个对象分配给群集

回到步骤2,当不再有新的任务时停止

就是在已知要分为4类之后,将K=4,随便找到4个点,计算每个原始点的到这四个点中心的距离,选择距离最近的点归类,这就有4类点,再在这些点内部计算每一点的质心,这就有了新的4个点,再对所有点计算到这四个点的距离,然后比较,以此类推。

 

 

 

================================

流程:

初始化1

指定组k的数目:

例如,k=4

选择4个点(随机)

 

 

 

每个点根据4个距离分配到最近的集群。

 

 

 

迭代直到装置收敛

 

 

============================================

关于k-means方法的评述

优点:相对高效:O(TKN),其中n#对象,k#集群,t#迭代。通常,kt<n

注释:通常以局部最佳状态终止。

全局最优的方法包括:确定性退火和遗传算法。

缺点:

仅在均值被定义时才适用,而不适用于分类数据

需要预先指定k,集群的数目。

无法处理噪声数据和异常值。

不适合发现具有非凸形状的簇

=================================================

处理数值数据的方法:k-means

 

 

 

类似于K的聚类方法

一些不同于K-means算法的不同在于

对于原始K-means值的选择

不同计算

计算集群均值的策略

处理分类数据K-modes

 

用模式替换均值

使用新的不同的措施来处理分类对象。

使用基于频率的方法来更新群集模式

分类数据和数值数据的混合:K-prototype

 

===========================================

K-medoid聚类方法

在集群中找到有代表性的对象,称为medoid

PAM围绕MeDOID进行分区

使用真实对象代表群集,

任意选择k表示对象

对于每对非选定的对象h和选定的对象i,计算总交换成本TCIDH

对于每对ih,

如果TCIDH<0,则将I替换为H

然后将每个非选定对象分配给最相似的具有代表性的对象。

重复步骤2-3,直到没有变化

即若K=2,则选择原始数据中的某两个点作为原始medoids,计算每个点到该点的距离,形成两个簇,再选择一个非之前的点作为medoid,如果花费得到改善则将medoid值替换为改点,如果没有得到改善则不变。

从一组初始的medoid开始,如果它改善了所产生的聚类的总距离,则迭代地将其中一个medoid替换为非medoid之一

PAM有效地适用于小型数据集,但对于大型数据集,PAM不能很好地进行扩展

CLARA

CLARANS:随机抽样

===========================================

PAM的评论

在存在噪声和异常值的情况下,pamk均值更健壮,因为Medoid受异常值或其他极值的影响小于k-means

PAM有效地适用于小型数据集,但对于大型数据集,PAM不能很好地扩展。

因为迭代次数较多,每个迭代的O(k(n-k)2)

其中n是数据的个数k是簇的个数

===========================================

CLARA集群大型应用程序

它绘制数据集的多个样本,对每个样本应用PAM,并给出最佳的聚类作为输出。

优点:处理比PAM更大的数据集。

劣势:效率取决于样本量。

-如果样本被偏置,则基于样本的良好聚类不一定代表整个数据集的良好聚类

即将原来的所有样本划分为更小单元,即单个样本来进行PAM

=======================================

分层群聚

使用距离矩阵作为聚类准则。此方法不需要将群集k的数目作为输入,而是需要一个终止条件。

 

给定一组待聚类的项目和NxN距离(或相似度)矩阵,基本过程分层聚类是这样的:

  1. 首先,将每个项分配给它自己的集群,这样如果您有N个项,那么您现在就有N个集群,每个集群只包含一个项。
  2. 找到最接近(最相似)的集群,并将它们合并到一个集群中,这样现在就少了一个集群。
  3. 计算新集群和每个旧集群之间的距离(相似之处)。
  4. 重复步骤2和步骤3,直到所有项目聚集成一个大小为N的集群。

就像哈弗曼树得到的过程一样。

========================================

簇间距离

单点距离:点间最小距离

完全点距离:最大点间距离

平均点距离:点间平均距离

质心距离:质心距离

===============================

合并或连接规则-计算距离

================================

距离测量:明可夫斯基度规

假设两个对象xy都有p特性:

 

 

 

明可夫斯基度规

 

 

=====================================

常用的Minkowski度量

R=2时是欧几里得距离:

R=1时是曼哈顿距离

R=正无穷是(sup”距离),即数据集合中取最大值。

 

 

 

============================================

当所有特征都是二进制时,曼哈顿距离被称为Hamming距离。

17个条件下基因表达水平(1-高,0-低)

 

 

 

即二进制的01+10=11=5

=========================================

其他相似指数

权重距离:

Sop距离:

 

内积:

皮尔逊相关系数

斯皮尔曼等级相关系数

==========================================

系统树图

一种树数据结构,它说明了层次聚类技术。

每个级别显示该级别的群集

叶子-个体群集

-一个群集

i级的群集是i+1群集的联盟

 

 

 

==========================================

聚类级别

 

 

 

凝聚实例

首先计算各点之间的距离,然后将距离最小的相组合,以此类推,直到根节点。

 

 

 

单链路、完全链接和平均链接群集

 

 

 

 

==========================================================

聚簇分析中的问题

大量的聚类算法

许多距离/相似性度量

哪种聚类算法运行得更快,使用的内存更少

到底有多少

这些簇稳定吗?

这些集群(簇)有意义吗?

=======================================================

统计显着性检验不是一个典型的统计测试

聚类分析是不同算法的集合根据定义良好的相似性规则将对象放入聚类

聚类分析方法大多是在没有先验假设的情况下使用,但还处于探索阶段。

事实上,集群分析发现"最重要的解决方案是可能的。"

统计学显著性检验在此不合适,即使在报告p水平的情况下(如在K-均值聚类中)

========================================

判别分析,判别式分析DA

DA用于通过距离度量来标识对象组之间的边界。

例如:

一些昆虫属于什么种类,属于一些措施的基础。

某人是否有良好的信用风险?

学生应该被大学录取吗?

类似于回归,除了标准(或因变量)分类变量的而不是连续变量

可替代地,判别式分析与(MANOVA)相反。

MANOVA:自变量是分类变量的,因变量是连续变量。

Manova中,自变量是群(分类变量),因变量是连续测度。

DA中,自变量是连续测度和因变量是团体(分类变量)。

===========================

DA的原始数据:

 

 

 

目的是让再来一个数据,据数据结构进行目录分类。

============================================

线性判别分析

线性判别分析试图找到最佳分离人口的选定措施的线性组合。

 

 

 

红色和蓝色即已经找到了划分方法。

程序:

判别函数分析分为两个步骤:

  1. 判别函数集测试显著性意义,即先看看有没有限制性差异,再多重比较

第一步骤在计算上与ManoVA相同。存在总方差-协方差矩阵;同样,存在集合内方差-协方差矩阵。

通过多元F检验对这两个矩阵进行比较,以确定组间是否存在显著差异(对于所有变量)

首先进行多元检验,如果具有统计学意义,则继续查看哪一个变量在各组中具有显著不同的均值。

  1. 分类

一旦发现组平均值具有统计学显著性,就进行变量分类。

判别分析自动确定变量的最优组合,从而使第一个函数提供最全面的变量组合。

群体间的区别,第二种提供第二全面,以此类推。

此外,这些职能将是独立的或正交的,也就是说,它们对群体之间的歧视的贡献不会重叠。

此外,这些函数将是独立的或正交的,也就是说,它们对群体之间的歧视的贡献不会重叠

=========================================

假定前提

样本量:即薯竖条型变量。

可接受不同的样本尺寸。最小组的样本大小需要超过预测变量的数量。作为经验法则,最小的样本大小应该是 对于几个(45)的预测因子,至少会有20。自变量的最大数目是n-2,其中n是样本的大小.虽然这种低样本量可能有效,但不鼓励这样做,而且通常最好是有45倍的观察和独立变量

正态分布:

假设数据(对于变量)表示来自多元正态分布的样本。您可以检查变量是否通常分布有频率分布的直方图。 然而,请注意,违反正态假设并不是致命的,只要非正态是由偏斜而非异常引起的,则由此产生的显着性检验仍然是可靠的。

方差/协方差的同质性

判别分析对方差协方差矩阵的异质性非常敏感。在接受重要研究的最终结论之前,最好先回顾一下组内方差和相关矩阵。同步性通过散射图进行评估,并通过变量变换加以修正。

=================================================

极端值

判别分析对离群点的包含非常敏感

运行每个组的单变量和多变量异常值的测试,并对其进行转换或消除。

如果一项研究中的一组包含影响平均值的极端离群值,则它们也会增加变异性。总体显着性测试基于集合方差,即所有组之间的平均方差。因此,相对较大的均值(具有较大的方差)的显着性检验将基于相对较小的集合方差,从而导致错误的统计显着性。即方差和均值都比实际情况要大。

 

非线性:

如果其中一个自变量与另一个独立变量高度相关,或者一个是其他独立变量的函数(例如和),那么矩阵就没有唯一的判别解。

在独立凹坑相关的程度上,标准化的鉴别函数系数将不能可靠地评估预测变量的相对重要性。既没有偏相关系数这一类的函数来评估。

============================================================

判别分析与聚类

判别分析:

已知的类数量

基于训练集

用于对未来的观测进行分类

 

分类是监督学习的一种形式

Y =X1 + X2 + X3

聚类

未知类数

无先验知识

用于理解(探索)数据

聚类是一种无监督学习形式。

X1 + X2 + X3

posted on 2019-12-11 20:48  YUANya  阅读(1195)  评论(0编辑  收藏  举报