㈠ 聚类分析中常见的数据类型有哪些
聚类分析,又称群分析,即建立一种分类方法:将一批样品或者指标(变量),按照它们在性质上的亲疏、相似程度进行分类。
按其聚类的方法,数据类型有以下六种:
①系统聚类分析:开始每个对象自成一类,然后将最相似的两类合并,合并过后重新计算新类与其它类的距离或相近性程度。这一过程一直继续下去直到所有的对象归为一类为止
②调优法(动态聚类法):首先对n个对象进行初步分类,然后根据分类的损失函数尽可能小的原则对其进行调整,直到分类合理为止;
③最优分割法(有序样品聚类法):开始将所有样品看成一类,然后根据某种最优准则将他们分割为二类、三类,一直分割到所需要的K类为止;
④模糊聚类法:利用模糊集理论来处理分类的问题,他将经济领域中最有模糊特征的两态数据或多态数据具有明显的分类效果;
⑤图论据类法:利用图论中最小支撑树的概念来处理分类问题;
⑥聚类预报法:聚类预报弥补了回归分析和判别分析的不足。
按分类对象的不同:聚类分为R型和Q型
㈡ k均值聚类法适用于均为连续型的变量对吗
对。k均值聚类算法是一种迭代求解的聚类分析算法,其步骤是,预将数据分为K组,则随机选取K个对象作为初始的聚类中心,K均值聚类适用于连续型变量,算法快速、简单,对大数据集有较高的效率并且是可伸缩性的,并且通常要求已知的类别数。然后计算每个对象与各个种子聚类中心之间的距离,把每个对象分配给距离它最近的聚类中心。聚类中心以及分配给它们的对象就代表一个聚类。
㈢ 16种常用的数据分析方法-聚类分析
聚类(Clustering)就是一种寻找数据之间内在结构的技术。聚类把全体数据实例组织成一些相似组,而这些相似组被称作簇。处于相同簇中的数据实例彼此相同,处于不同簇中的实例彼此不同。
聚类分析定义
聚类分析是根据在数据中发现的描述对象及其关系的信息,将数据对象分组。目的是,组内的对象相互之间是相似的(相关的),而不同组中的对象是不同的(不相关的)。组内相似性越大,组间差距越大,说明聚类效果越好。
聚类效果的好坏依赖于两个因素:1.衡量距离的方法(distance measurement) 2.聚类算法(algorithm)
聚类分析常见算法
K-均值聚类也称为快速聚类法,在最小化误差函数的基础上将数据划分为预定的类数K。该算法原理简单并便于处理大量数据。
K-均值算法对孤立点的敏感性,K-中心点算法不采用簇中对象的平均值作为簇中心,而选用簇中离平均值最近的对象作为簇中心。
也称为层次聚类,分类的单位由高到低呈树形结构,且所处的位置越低,其所包含的对象就越少,但这些对象间的共同特征越多。该聚类方法只适合在小数据量的时候使用,数据量大的时候速度会非常慢。
案例
有20种12盎司啤酒成分和价格的数据,变量包括啤酒名称、热量、钠含量、酒精含量、价格。
问题一:选择那些变量进行聚类?——采用“R 型聚类”
现在我们有4个变量用来对啤酒分类,是否有必要将4个变量都纳入作为分类变量呢?热量、钠含量、酒精含量这3个指标是要通过化验员的辛苦努力来测定,而且还有花费不少成本。
所以,有必要对4个变量进行降维处理,这里采用spss R型聚类(变量聚类),对4个变量进行降维处理。输出“相似性矩阵”有助于我们理解降维的过程。
4个分类变量各自不同,这一次我们先用相似性来测度,度量标准选用pearson系数,聚类方法选最远元素,此时,涉及到相关,4个变量可不用标准化处理,将来的相似性矩阵里的数字为相关系数。若果有某两个变量的相关系数接近1或-1,说明两个变量可互相替代。
只输出“树状图”就可以了,从proximity matrix表中可以看出热量和酒精含量两个变量相关系数0.903,最大,二者选其一即可,没有必要都作为聚类变量,导致成本增加。
至于热量和酒精含量选择哪一个作为典型指标来代替原来的两个变量,可以根据专业知识或测定的难易程度决定。(与因子分析不同,是完全踢掉其中一个变量以达到降维的目的。)这里选用酒精含量,至此,确定出用于聚类的变量为:酒精含量,钠含量,价格。
问题二:20 中啤酒能分为几类?—— 采用“Q 型聚类”
现在开始对20中啤酒进行聚类。开始不确定应该分为几类,暂时用一个3-5类范围来试探。Q型聚类要求量纲相同,所以我们需要对数据标准化,这一回用欧式距离平方进行测度。
主要通过树状图和冰柱图来理解类别。最终是分为4类还是3类,这是个复杂的过程,需要专业知识和最初的目的来识别。
这里试着确定分为4类。选择“保存”,则在数据区域内会自动生成聚类结果。
问题三:用于聚类的变量对聚类过程、结果又贡献么,有用么?——采用“单因素方差分析”
聚类分析除了对类别的确定需讨论外,还有一个比较关键的问题就是分类变量到底对聚类有没有作用有没有贡献,如果有个别变量对分类没有作用的话,应该剔除。
这个过程一般用单因素方差分析来判断。注意此时,因子变量选择聚为4类的结果,而将三个聚类变量作为因变量处理。方差分析结果显示,三个聚类变量sig值均极显著,我们用于分类的3个变量对分类有作用,可以使用,作为聚类变量是比较合理的。
问题四:聚类结果的解释?——采用”均值比较描述统计“
聚类分析最后一步,也是最为困难的就是对分出的各类进行定义解释,描述各类的特征,即各类别特征描述。这需要专业知识作为基础并结合分析目的才能得出。
我们可以采用spss的means均值比较过程,或者excel的透视表功能对各类的各个指标进行描述。其中,report报表用于描述聚类结果。对各类指标的比较来初步定义类别,主要根据专业知识来判定。这里到此为止。
以上过程涉及到spss层次聚类中的Q型聚类和R型聚类,单因素方差分析,means过程等,是一个很不错的多种分析方法联合使用的案例。
聚类分析的应用
聚类分析是细分市场的有效工具,被用来发现不同的客户群,并且它通过对不同的客户群的特征的刻画,被用于研究消费者行为,寻找新的潜在市场。
聚类分析被用来对动植物和基因进行分类,以获取对种群固有结构的认识。
聚类分析可以通过平均消费来鉴定汽车保险单持有者的分组,同时可以根据住宅类型、价值、地理位置来鉴定城市的房产分组。
聚类分析被用来在网上进行文档归类。
聚类分析通过分组聚类出具有相似浏览行为的客户,并分析客户的共同特征,从而帮助电子商务企业了解自己的客户,向客户提供更合适的服务。
㈣ 常用的聚类方法有哪几种
聚类分析的算法可以分为划分法、层次法、基于密度的方法、基于网格的方法、基于模型的方法。
1、划分法,给定一个有N个元组或者纪录的数据集,分裂法将构造K个分组,每一个分组就代表一个聚类,K<N。
2、层次法,这种方法对给定的数据集进行层次似的分解,直到某种条件满足为止。
3、基于密度的方法,基于密度的方法与其它方法的一个根本区别是:它不是基于各种各样的距离的,而是基于密度的。这样就能克服基于距离的算法只能发现“类圆形”的聚类的缺点。
4、图论聚类方法解决的第一步是建立与问题相适应的图,图的节点对应于被分析数据的最小单元,图的边(或弧)对应于最小处理单元数据之间的相似性度量。
5、基于网格的方法,这种方法首先将数据空间划分成为有限个单元的网格结构,所有的处理都是以单个的单元为对象的。
6、基于模型的方法,基于模型的方法给每一个聚类假定一个模型,然后去寻找能够很好的满足这个模型的数据集。
(4)聚类算法适用于什么类型的数据扩展阅读:
在商业上,聚类可以帮助市场分析人员从消费者数据库中区分出不同的消费群体来,并且概括出每一类消费者的消费模式或者说习惯。
它作为数据挖掘中的一个模块,可以作为一个单独的工具以发现数据库中分布的一些深层的信息,并且概括出每一类的特点,或者把注意力放在某一个特定的类上以作进一步的分析;并且,聚类分析也可以作为数据挖掘算法中其他分析算法的一个预处理步骤。
许多聚类算法在小于 200 个数据对象的小数据集合上工作得很好;但是,一个大规模数据库可能包含几百万个对象,在这样的大数据集合样本上进行聚类可能会导致有偏的结果。
许多聚类算法在聚类分析中要求用户输入一定的参数,例如希望产生的簇的数目。聚类结果对于输入参数十分敏感。参数通常很难确定,特别是对于包含高维对象的数据集来说。这样不仅加重了用户的负担,也使得聚类的质量难以控制。
㈤ 聚类算法有哪些分类
聚类算法的分类有:
1、划分法
划分法(partitioning methods),给定一个有N个元组或者纪录的数据集,分裂法将构造K个分组,每一个分组就代表一个聚类,K小于N。而且这K个分组满足下列条件:
(1) 每一个分组至少包含一个数据纪录;
(2)每一个数据纪录属于且仅属于一个分组(注意:这个要求在某些模糊聚类算法中可以放宽);
2、层次法
层次法(hierarchical methods),这种方法对给定的数据集进行层次似的分解,直到某种条件满足为止。具体又可分为“自底向上”和“自顶向下”两种方案。
例如,在“自底向上”方案中,初始时每一个数据纪录都组成一个单独的组,在接下来的迭代中,它把那些相互邻近的组合并成一个组,直到所有的记录组成一个分组或者某个条件满足为止。
3、密度算法
基于密度的方法(density-based methods),基于密度的方法与其它方法的一个根本区别是:它不是基于各种各样的距离的,而是基于密度的。这样就能克服基于距离的算法只能发现“类圆形”的聚类的缺点。
4、图论聚类法
图论聚类方法解决的第一步是建立与问题相适应的图,图的节点对应于被分析数据的最小单元,图的边(或弧)对应于最小处理单元数据之间的相似性度量。因此,每一个最小处理单元数据之间都会有一个度量表达,这就确保了数据的局部特性比较易于处理。图论聚类法是以样本数据的局域连接特征作为聚类的主要信息源,因而其主要优点是易于处理局部数据的特性。
5、网格算法
基于网格的方法(grid-based methods),这种方法首先将数据空间划分成为有限个单元(cell)的网格结构,所有的处理都是以单个的单元为对象的。这么处理的一个突出的优点就是处理速度很快,通常这是与目标数据库中记录的个数无关的,它只与把数据空间分为多少个单元有关。
代表算法有:STING算法、CLIQUE算法、WAVE-CLUSTER算法;
6、模型算法
基于模型的方法(model-based methods),基于模型的方法给每一个聚类假定一个模型,然后去寻找能够很好的满足这个模型的数据集。这样一个模型可能是数据点在空间中的密度分布函数或者其它。它的一个潜在的假定就是:目标数据集是由一系列的概率分布所决定的。
通常有两种尝试方向:统计的方案和神经网络的方案。
(5)聚类算法适用于什么类型的数据扩展阅读:
聚类算法的要求:
1、可伸缩性
许多聚类算法在小于 200 个数据对象的小数据集合上工作得很好;但是,一个大规模数据库可能包含几百万个对象,在这样的大数据集合样本上进行聚类可能会导致有偏的结果。
我们需要具有高度可伸缩性的聚类算法。
2、不同属性
许多算法被设计用来聚类数值类型的数据。但是,应用可能要求聚类其他类型的数据,如二元类型(binary),分类/标称类型(categorical/nominal),序数型(ordinal)数据,或者这些数据类型的混合。
3、任意形状
许多聚类算法基于欧几里得或者曼哈顿距离度量来决定聚类。基于这样的距离度量的算法趋向于发现具有相近尺度和密度的球状簇。但是,一个簇可能是任意形状的。提出能发现任意形状簇的算法是很重要的。
4、领域最小化
许多聚类算法在聚类分析中要求用户输入一定的参数,例如希望产生的簇的数目。聚类结果对于输入参数十分敏感。参数通常很难确定,特别是对于包含高维对象的数据集来说。这样不仅加重了用户的负担,也使得聚类的质量难以控制。
5、处理“噪声”
绝大多数现实中的数据库都包含了孤立点,缺失,或者错误的数据。一些聚类算法对于这样的数据敏感,可能导致低质量的聚类结果。
6、记录顺序
一些聚类算法对于输入数据的顺序是敏感的。例如,同一个数据集合,当以不同的顺序交给同一个算法时,可能生成差别很大的聚类结果。开发对数据输入顺序不敏感的算法具有重要的意义。
㈥ 用于数据挖掘的聚类算法有哪些,各有何优势
K均值聚类:最适合处理大数据,适用于大样本的个案聚类,分类数明确,适用于连续性变量;
系统聚类:适用于个案或变量聚类,对分类数没有要求,连续性和分类型变量均适用;
两步聚类:1)分类变量和连续变量均可参与二阶聚类;2)可自动确定分类数;3)适用于大数据集;4)用户可自己定制用于运算的内存容量
㈦ 系统聚类适用于连续变量还是离散变量
连续变量和离散变量都适用系统聚类。
系统聚类法(分层聚类法):
1、基本思想:开始将每个样本自成一类;然后求两两之间的距离,将距离最近的两类合成一类;如此重复,直到所有样本都合为一类为止。
2、适用范围:既适用于样本聚类,也适用于变量聚类。并且距离分类准则和距离计算方法都有多种,可以依据具体情形选择。
快速聚类法(K-均值聚类法):
1、基本思想:按照指定分类数目,选择个初始聚类中心;计算每个观测量(样本)到各个聚类中心的距离,按照就近原则将其分别分到放入各类中;重新计算聚类中心,继续以上步骤;满足停止条件时(如最大迭代次数等)则停止。
2、使用范围:要求用户给定分类数目,只适用于样本聚类(Q型),不适用于变量聚类(R型)。
㈧ 用于数据挖掘的聚类算法有哪些,各有何优势
1、层次聚类算法
1.1聚合聚类
1.1.1相似度依据距离不同:Single-Link:最近距离、Complete-Link:最远距离、Average-Link:平均距离
1.1.2最具代表性算法
1)CURE算法
特点:固定数目有代表性的点共同代表类
优点:识别形状复杂,大小不一的聚类,过滤孤立点
2)ROCK算法
特点:对CURE算法的改进
优点:同上,并适用于类别属性的数据
3)CHAMELEON算法
特点:利用了动态建模技术
1.2分解聚类
1.3优缺点
优点:适用于任意形状和任意属性的数据集;灵活控制不同层次的聚类粒度,强聚类能力
缺点:大大延长了算法的执行时间,不能回溯处理
2、分割聚类算法
2.1基于密度的聚类
2.1.1特点
将密度足够大的相邻区域连接,能有效处理异常数据,主要用于对空间数据的聚类
2.1.2典型算法
1)DBSCAN:不断生长足够高密度的区域
2)DENCLUE:根据数据点在属性空间中的密度进行聚类,密度和网格与处理的结合
3)OPTICS、DBCLASD、CURD:均针对数据在空间中呈现的不同密度分不对DBSCAN作了改进
2.2基于网格的聚类
2.2.1特点
利用属性空间的多维网格数据结构,将空间划分为有限数目的单元以构成网格结构;
1)优点:处理时间与数据对象的数目无关,与数据的输入顺序无关,可以处理任意类型的数据
2)缺点:处理时间与每维空间所划分的单元数相关,一定程度上降低了聚类的质量和准确性
2.2.2典型算法
1)STING:基于网格多分辨率,将空间划分为方形单元,对应不同分辨率
2)STING+:改进STING,用于处理动态进化的空间数据
3)CLIQUE:结合网格和密度聚类的思想,能处理大规模高维度数据
4)WaveCluster:以信号处理思想为基础
2.3基于图论的聚类
2.3.1特点
转换为组合优化问题,并利用图论和相关启发式算法来解决,构造数据集的最小生成数,再逐步删除最长边
1)优点:不需要进行相似度的计算
2.3.2两个主要的应用形式
1)基于超图的划分
2)基于光谱的图划分
2.4基于平方误差的迭代重分配聚类
2.4.1思想
逐步对聚类结果进行优化、不断将目标数据集向各个聚类中心进行重新分配以获最优解
2.4.2具体算法
1)概率聚类算法
期望最大化、能够处理异构数据、能够处理具有复杂结构的记录、能够连续处理成批的数据、具有在线处理能力、产生的聚类结果易于解释
2)最近邻聚类算法——共享最近邻算法SNN
特点:结合基于密度方法和ROCK思想,保留K最近邻简化相似矩阵和个数
不足:时间复杂度提高到了O(N^2)
3)K-Medioids算法
特点:用类中的某个点来代表该聚类
优点:能处理任意类型的属性;对异常数据不敏感
4)K-Means算法
1》特点:聚类中心用各类别中所有数据的平均值表示
2》原始K-Means算法的缺陷:结果好坏依赖于对初始聚类中心的选择、容易陷入局部最优解、对K值的选择没有准则可依循、对异常数据较为敏感、只能处理数值属性的数据、聚类结构可能不平衡
3》K-Means的变体
Bradley和Fayyad等:降低对中心的依赖,能适用于大规模数据集
Dhillon等:调整迭代过程中重新计算中心方法,提高性能
Zhang等:权值软分配调整迭代优化过程
Sarafis:将遗传算法应用于目标函数构建中
Berkh in等:应用扩展到了分布式聚类
还有:采用图论的划分思想,平衡聚类结果,将原始算法中的目标函数对应于一个各向同性的高斯混合模型
5)优缺点
优点:应用最为广泛;收敛速度快;能扩展以用于大规模的数据集
缺点:倾向于识别凸形分布、大小相近、密度相近的聚类;中心选择和噪声聚类对结果影响大
3、基于约束的聚类算法
3.1约束
对个体对象的约束、对聚类参数的约束;均来自相关领域的经验知识
3.2重要应用
对存在障碍数据的二维空间按数据进行聚类,如COD(Clustering with Obstructed Distance):用两点之间的障碍距离取代了一般的欧式距离
3.3不足
通常只能处理特定应用领域中的特定需求
4、用于高维数据的聚类算法
4.1困难来源因素
1)无关属性的出现使数据失去了聚类的趋势
2)区分界限变得模糊
4.2解决方法
1)对原始数据降维
2)子空间聚类
CACTUS:对原始空间在二维平面上的投影
CLIQUE:结合基于密度和网格的聚类思想,借鉴Apriori算法
3)联合聚类技术
特点:对数据点和属性同时进行聚类
文本:基于双向划分图及其最小分割的代数学方法
4.3不足:不可避免地带来了原始数据信息的损失和聚类准确性的降低
㈨ 聚类分析聚类算法中包含哪些数据类型
聚类分析聚类算法中包含哪些数据类型
许多基于内存的聚类算法采用以下两种数据结构:
(1)数据矩阵(Data Matrix,或称对象一变盘结构):用p个变量来表示n个对象,例如使用年龄、身高、性别、体重等属性变量来表示对象人,也叫二模矩阵,行与列代表不同实体:
(2)相异度矩阵(Dissimilarity Matrix,又称为对象一对象结构):存储所有成对的n个对象两两之间的近似性(邻近度),也叫单模矩阵,行和列代表相同的实体。其中d(ij)是对象i和对象j之间的测量差或相异度。d(i,f)是一个非负的数值,d(ij)越大,两个对象越不同;d (i,j)越接近于0,则两者之间越相似(相近)。
许多聚类算法都是以相异度矩阵为基础的,如果数据是用数据矩阵形式表示,则往往要将其先转化为相异度矩阵。
相异度d(i,j)的具体计算会因所使用的数据类型不同而不同,常用的数据类型包括:区间标度变量,二元变量,标称型、序数型和比例标度型变量,混合类型的变量。
㈩ 聚类算法--DBSCAN
DBSCAN(Density-Based Spatial Clustering of Applications with Noise,具有噪声的基于密度的聚类方法)是一种很典型的密度聚类算法,和K-Means,BIRCH这些一般只适用于凸样本集的聚类相比,DBSCAN既可以适用于凸样本集,也可以适用于非凸样本集。 基于密度的带有噪声的空间聚类,可用于异常值监测,通俗来说就是基于密度的聚类算法 !
聚类就是对大量未知标注的数据集,按数据的内在相似性将数据集划分为多个类别,使类别内的数据相似度较大而类别间的数据相似度较小。聚类算法是无监督的算法。
DBSCAN算法的目的: 是基于密度寻找被低密度区域分离的高密度样本分为三类:
稠密区域内部的点(核心点): 在半径Eps内含有超过MinPts数目的点
稠密区域边缘上的点(边缘点): 在半径Eps内点的数量小于MinPts(即不是核心点),但是其邻域内至少包含一个核心点
稀疏区域中的点(噪声或者背景点): 任何不是核心点或者边界点的点
特点 : 发现任意形状的簇、对噪声数据不敏感、一次扫描、需要密度参数作为停止条件,计算量大和复杂度高 。
DBSCAN是一种基于密度的聚类算法,这类密度聚类算法一般假定类别可以通过样本分布的紧密程度决定。同一类别的样本,他们之间的紧密相连的,也就是说,在该类别任意样本周围不远处一定有同类别的样本存在。
通过将紧密相连的样本划为一类,这样就得到了一个聚类类别。通过将所有各组紧密相连的样本划为各个不同的类别,则我们就得到了最终的所有聚类类别结果。
前面我们定性描述了密度聚类的基本思想,在这里我们就看看DBSCAN是如何描述密度聚类的。DBSCAN是基于一组邻域来描述样本集的紧密程度的,参数(ϵϵ, MinPts)用来描述邻域的样本分布紧密程度。其中,ϵϵ描述了某一样本的邻域距离阈值,MinPts描述了某一样本的距离为ϵϵ的邻域中样本个数的阈值。
假设我们的样本集是D=(x1,x2,...,xm)(x1,x2,...,xm),则DBSCAN具体的密度描述定义如下:
1) ϵϵ-邻域:对于xj∈Dxj∈D,其ϵϵ-邻域包含样本集D中与xjxj的距离不大于ϵϵ的子样本集,即Nϵ(xj)={xi∈D|distance(xi,xj)≤ϵ}Nϵ(xj)={xi∈D|distance(xi,xj)≤ϵ}, 这个子样本集的个数记为|Nϵ(xj)||Nϵ(xj)|
2)核心对象:对于任一样本xj∈Dxj∈D,如果其ϵϵ-邻域对应的Nϵ(xj)Nϵ(xj)至少包含MinPts个样本,即如果|Nϵ(xj)|≥MinPts|Nϵ(xj)|≥MinPts,则xjxj是核心对象。
3)密度直达:如果xixi位于xjxj的ϵϵ-邻域中,且xjxj是核心对象,则称xixi由xjxj密度直达。注意反之不一定成立,即此时不能说xjxj由xixi密度直达, 除非且xixi也是核心对象。
4)密度可达:对于xixi和xjxj,如果存在样本样本序列p1,p2,...,pTp1,p2,...,pT,满p1=xi,pT=xjp1=xi,pT=xj, 且pt+1pt+1由ptpt密度直达,则称xjxj由xixi密度可达。也就是说,密度可达满足传递性。此时序列中的传递样本p1,p2,...,pT−1p1,p2,...,pT−1均为核心对象,因为只有核心对象才能使其他样本密度直达。注意密度可达也不满足对称性,这个可以由密度直达的不对称性得出。
5)密度相连:对于xixi和xjxj,如果存在核心对象样本xkxk,使xixi和xjxj均由xkxk密度可达,则称xixi和xjxj密度相连。注意密度相连关系是满足对称性的。
从下图可以很容易看出理解上述定义,图中MinPts=5,红色的点都是核心对象,因为其ϵϵ-邻域至少有5个样本。黑色的样本是非核心对象。所有核心对象密度直达的样本在以红色核心对象为中心的超球体内,如果不在超球体内,则不能密度直达。图中用绿色箭头连起来的核心对象组成了密度可达的样本序列。在这些密度可达的样本序列的ϵϵ-邻域内所有的样本相互都是密度相连的。
DBSCAN的聚类定义很简单: 由密度可达关系导出的最大密度相连的样本集合,即为我们最终聚类的一个类别,或者说一个簇 。
这个DBSCAN的簇里面可以有一个或者多个核心对象。如果只有一个核心对象,则簇里面其他的非核心对象样本都在这个核心对象的ϵϵ-邻域里;如果有多个核心对象,则簇里的任意一个核心对象的ϵϵ-邻域中一定有一个其他的核心对象,否则这个核心对象无法密度可达。这些核心对象的ϵϵ-邻域里所有的样本的集合组成的一个DBSCAN聚类簇。
那么怎么才能找到这样的簇样本集合呢?DBSCAN使用的方法很简单,它任意选择一个没有类别的核心对象作为种子,然后找到所有这个核心对象能够密度可达的样本集合,即为一个聚类簇。接着继续选择另一个没有类别的核心对象去寻找密度可达的样本集合,这样就得到另一个聚类簇。一直运行到所有核心对象都有类别为止。基本上这就是DBSCAN算法的主要内容了,但是我们还有三个问题没有考虑。
1)一些异常样本点或者说少量游离于簇外的样本点,这些点不在任何一个核心对象的周围,在DBSCAN中,我们一般将这些样本点标记为噪音点。
2)距离的度量问题,即如何计算某样本和核心对象样本的距离。在DBSCAN中,一般采用最近邻思想,采用某一种距离度量来衡量样本距离,比如欧式距离。这和KNN分类算法的最近邻思想完全相同。对应少量的样本,寻找最近邻可以直接去计算所有样本的距离,比如样本量较大,则一般采用KD树或者球树来快速的搜索最近邻。
3)某些样本可能到两个核心对象的距离都小于ϵϵ,但是这两个核心对象由于不是密度直达,又不属于同一个聚类簇,那么如何界定这个样本的类别呢?一般来说,此时DBSCAN采用先来后到,先进行聚类的类别簇会标记这个样本为它的类别。也就是说DBSCAN的算法不是完全稳定的算法。
DBSCAN通过检查数据集中的每个对象的ε-邻域来寻找聚类,如果一个点p的ε-邻域包含对于m个对象,则创建一个p作为核心对象的新簇。然后,DBSCAN反复地寻址这些核心对象直接密度可达的对象,这个过程可能涉及密度可达簇的合并。当没有新的点可以被添加到任何簇时,该过程结束。算法中的ε和m是根据先验只是来给出的。
DBSCAN聚类算法原理的基本要点:
1.DBSCAN算法需要选择一种距离度量,对于待聚类的数据集中,任意两个点之间的距离,反应了点之间的密度,说明了点与点是否能够聚到同一类中。由于DBSCAN算法对高维数据定义密度很困难,所以对于二维空间中的点,可以使用欧几里得距离来进行度量。
2.DBSCAN算法需要用户输入2个参数: 一个参数是半径(Eps),表示以给定点P为中心的圆形邻域的范围;另一个参数是以点P为中心的邻域内最少点的数量(MinPts)。如果满足:以点P为中心、半径为Eps的邻域内的点的个数不少于MinPts,则称点P为核心点 。
3.DBSCAN聚类聚类使用到一个 k-距离 的概念,k-距离是指:给定数据集P={p(i); i=0,1,……n},对于任意点P(i),计算点P(i)到集合D的子集S={p(1), p(2), …, p(i-1), p(i+1), …, p(n)}中 所有点之间的距离 , 距离按照从小到大的顺序排序 ,假设排序后的距离集合为D={d(1), d(2), …, d(k-1), d(k), d(k+1), …,d(n)}, 则d(k)就被称为k-距离 。也就是说, k-距离是点p(i)到所有点(除了p(i)点)之间距离第K近的距离 。对待聚类集合中 每个点p(i)都计算k-距离,最后得到所有点的k-距离集合E={e(1), e(2), …, e(n)} 。
4.根据经验计算半径Eps:根据得到的所有点的 k-距离集合E ,对集合E进行 升序排序 后得到k-距离集合 E' ,需要拟合一条排序后的E'集合中k-距离的变化曲线图,然后绘出曲线,通过观察, 将急剧发生变化的位置所对应的k-距离的值,确定为半径Eps的值 。
5.根据经验计算最少点的数量MinPts: 确定MinPts的大小,实际上也是确定k-距离中k的值 ,DBSCAN算法中取k=4,则MinPts=4。
6.另外,如果觉得经验值聚类的结果不满意,可以适当调整Eps和MinPts的值,经过多次迭代计算对比,选择最合适的参数值。可以看出,如果MinPts不变。Eps取得值过大,会导致大多数点都聚到同一个簇中,Eps过小,会导致一个簇的分裂;如果Eps不变,MinPts的值取得过大,会导致同一个簇中点被标记为离群点,MinPts过小,会导致发现大量的核心点。
我们需要知道的是,DBSCAN算法,需要输入2个参数,这两个参数的计算都来自经验知识。半径Eps的计算依赖于计算k-距离,DBSCAN取k=4,也就是设置MinPts=4,然后需要根据k-距离曲线,根据经验观察找到合适的半径Eps的值,下面的算法实现过程中,我们会详细说明。
对于算法的实现,我们概要地描述一下实现的过程:
1.解析样本数据文件。
2.计算每个点与其他所有点之间的欧几里得距离。
3.计算每个点的k-距离值,并对所有点的k-距离集合进行升序排序,输出的排序后的k-距离值。
4.将所有点的k-距离值,在Excel中用散点图显示k-距离变化趋势
5.根据散点图确定半径Eps的值
6.根据给定MinPts=4,以及半径Eps的值,计算所有核心点,并建立核心点与核心点距离小于半径Eps的点映射。
7.根据得到的核心点集合,以及半径Eps的值,计算能够连通的核心点,并得到离群点。
8.将能够连通的每一组核心点,以及到核心点距离小于半径Eps的点,都放到一起,形成一个簇。
9.选择不同的半径Eps,使用DBSCAN算法聚类得到的一组簇及其离群点,使用散点图对比聚类效果。
和传统的K-Means算法相比,DBSCAN最大的不同就是不需要输入类别数K,当然它最大的优势是可以发现任意形状的聚类簇,而不是像K-Means,一般仅仅使用于凸的样本集聚类。同时它在聚类的同时还可以找出异常点,这点和BIRCH算法类似。
那么我们什么时候需要用DBSCAN来聚类呢?一般来说,如果数据集是稠密的,并且数据集不是凸的,那么用DBSCAN会比K-Means聚类效果好很多。 如果数据集不是稠密的,则不推荐用DBSCAN来聚类 。
优点:
1)可以对任意形状的稠密数据集进行聚类,相对的,K-Means之类的聚类算法一般只适用于凸数据集。不用指明类别的数量,能灵活找到并分离各种形状和大小的类。能很好地处理噪声和离群点。
2)可以在聚类的同时发现异常点,对数据集中的异常点不敏感。
3)聚类结果没有偏倚,相对的,K-Means之类的聚类算法初始值对聚类结果有很大影响。
缺点:
1)在不同密度的类方面有一定难度。如果样本集的密度不均匀、聚类间距差相差很大时,聚类质量较差,这时用DBSCAN聚类一般不适合( HDBSCAN适合密度不均匀问题 )。
2)如果样本集较大时,聚类收敛时间较长,此时可以对搜索最近邻近时建立的KD树或者球树进行规模限制来改进。当数据量增大时,要求较大的内存支持I/O消耗也很大;算法聚类效果依赖与距离公式选取,实际应用中常用欧式距离,对于高维数据,存在“维数灾难”。
3)调参相对于传统的K-Means之类的聚类算法稍复杂,主要需要对距离阈值ϵϵ,邻域样本数阈值MinPts联合调参,不同的参数组合对最后的聚类效果有较大影响。
4)对于从两类均可达的边界点,由于各个点是被随机访问的,因此DBSCAN不能保证每次都返回相同的聚类。
DBSCAN类的重要参数分为两类,一类是DBSCAN算法本身的参数,一类是最近邻度量的参数,下面我们对这些参数做一个总结。
1) eps: DBSCAN算法参数,即我们的ϵ-邻域的距离阈值,和样本距离超过ϵ的样本点不在ϵ-邻域内。 默认值是0.5 ,一般需要通过在多组值里面选择一个合适的阈值。eps过大,则更多的点会落在核心对象的ϵ-邻域,此时我们的类别数可能会减少,本来不应该是一类的样本也会被划分为一类。反之则类别数可能会增大,本来是一类的样本却被划分开。
2) min_samples: DBSCAN算法参数,即样本点要成为核心对象所需要的ϵ-邻域的样本数阈值。默认值是5。一般需要通过在多组值里面选择一个合适的阈值。通常和eps一起调参。在eps一定的情况下,min_samples过大,则核心对象会过少,此时簇内部分本来是一类的样本可能会被标为噪音点,类别数也会变多。反之min_samples过小的话,则会产生大量的核心对象,可能会导致类别数过少。
3) metric: 最近邻距离度量参数。可以使用的距离度量比较多,一般来说DBSCAN使用默认的欧式距离(即p=2的闵可夫斯基距离)就可以满足我们的需求。可以使用的距离量度参数有:欧式距离、曼哈顿距离、切比雪夫距离、闵可夫斯基距离、带权重闵可夫斯基距离、标准化欧式距离、马氏距离。
还有一些其他不是实数的距离度量,一般在DBSCAN算法用不上,这里也就不列了。
4)algorithm:最近邻搜索算法参数,算法一共有三种,第一种是蛮力实现,第二种是KD树实现,第三种是球树实现。这三种方法与K近邻法(KNN)原理中算法一致。对于这个参数,一共有4种可选输入,"brute"对应第一种蛮力实现,"kd_tree"对应于第二种KD树实现,"ball_tree"对应于第三种的球树实现,"auto"则会在上面三种算法中做权衡,选择一个拟合最好的最优算法。 需要注意的是,如果输入样本特征是稀疏的时候,无论我们选择哪种算法,最后sklearn都会去用蛮力实现"brute" 。个人的经验,一般情况使用默认的"auto"就够了。如果数据量很大或者特征也很多,用“auto”建树时间可能会很长,效率不高,建议选择KD树实现“kd_tree”,此时如果发现"kd_tree"速度比较慢或者已经知道样本分布不是很均匀时,可以尝试用"ball_tree"。
5) leaf_size :最近邻搜索算法参数,为使用KD树或者球树时,停止建子树的叶子节点数量的阈值。这个值越小,则生成的KD树或者球树就越大,层数越深,建树时间越长,反之,则生成的KD树或者球树会小,层数较浅,建树时间较短。默认是30,因为这个值一般只影响算法是运行速度和使用内存大小,因此一般情况下可以不管它。
6) p :最近邻距离度量参数。只有用于闵可夫斯基距离和带权重闵客服斯基距离中p值的选择,p=1为曼哈顿距离,p=2为欧式距离。如果使用默认的欧式距离不需要管这个参数。
以上就是DBSCAN类的主要参数介绍,其实需要调参的就是两个参数eps和min_samples,这两个值的组合对最终的聚类效果有很大的影响。