数据挖掘之聚类

作者: 七八音 | 来源:发表于2018-01-02 11:14 被阅读45次

    文章大纲:

    聚类概念

    聚类应用

    聚类目标

    相似性计算方法

    聚类方法分类

    划分方法

    1. 概念

    按照数据之间的相似性,对数据集进行分组或分类(簇, cluster)的过程;试图使类内差距最小化,类间差距最大化。

    利用聚类结果,可以提取数据集中隐藏的信息,对未来数据进行预测和分类

    特点:处理巨大的、复杂的数据集

    2. 应用

    (1)作为其它算法的预处理步骤:利用聚类进行数据预处理,可以获得数据的基本概况,在此基础上进行特征抽取或分类就可以提高精确度和挖掘效率。也可将聚类结果用于进一步关联分析,以获得进一步的有用信息。

    (2)作为一个独立的工具来获得数据的分布情况:聚类分析是获得数据分布情况的有效方法。通过观察聚类得到的每个簇的特点,可以集中对特定的某些簇作进一步分析。

    (3)聚类分析可以完成孤立点挖掘:许多数据挖掘算法试图使孤立点影响最小化,或者排除它们。

    3. 聚类分析的目标

    聚类分析的目标就是形成的数据簇,并且满足下面两个条件:

            --一个簇内的数据尽量相似(highintra-classsimilarity);

            --不同簇的数据尽量不相似(lowinter-classsimilarity)。

    衡量一个聚类分析算法质量,依靠:

            --相似度测量机制是否合适。

            --是否能发现数据背后潜在的、手工难以发现的类知识。

    4. 相似性度量

    (1)距离相似性度量

    (2)角度相似性度量

    Similarity is expressed in terms of a distance function, which is typically metric: d(i, j);

    不同类型的数据,距离函数的定义也有所不同。

    4.1 数据类型及其类内度量方式

    (1)区间标度

    区间标度是一个粗略线性标度的连续度量

    eg:重量和高度,经度和纬度坐标以及大气温度。

    明考斯基距离:

    名氏距离

    If  q=1,dis曼哈顿距离(Manhattan distance):

    曼哈顿距离

    If q=2,dis欧几里得距离Euclidean distance:

    欧式距离

    (2)二元变量

    两种状态:0、1.

    A。 对称型

    简单匹配系数:

    计算公式 数据表

    B。非对称型

    根据惯例,我们将比较重要的输出结果,通常也是出现几率较小的结果编码为1

    给定两个不对称的二元变量,两个都取值1的情况被认为比两个都取值0的情况更有意义。因此,这样的二元变量被认为好像只有一个状态。

    Jaccard系数:

    计算中,负匹配的数目d认为是不重要的,被忽略;

    计算公式

    (3)标称型、序数型和比例标度型

    (4)混合型

    4.2 类间度量

    设有两个类Ca和Cb,它们分别有m和h个元素,它们的中心分别为γa和γb。设元素x∈Ca,y∈Cb,这两个元素间的距离通常通过类间距离来刻画,记为D(Ca,Cb)。

    两个聚类p和q:

    (1)最短距离法

    (2)最长距离法

    (3)重心法

    (4)类平均法

    4.3 其他影响

    特征选取不当---聚类无效

    特征选取不足---误分类

    模式特征坐标单位的选取也会强烈地影响聚类结果

    尺度问题:标准化

    标准化1 标准化2 标准化3 标准化4

    4.4 角度相似性度量

    角度度量 特点

    5. 聚类方法分类

    (1)按照聚类的标准,聚类方法可分为如下两种:

    统计聚类方法:这种聚类方法主要基于对象之间的几何距离的。

    概念聚类方法:概念聚类方法基于对象具有的概念进行聚类。

    (2)按照聚类算法所处理的数据类型,聚类方法可分为三种:

    数值型数据聚类方法:所分析的数据的属性只限于数值数据。

    离散型数据聚类方法:所分析的数据的属性只限于离散型数据。

    混合型数据聚类方法:能同时处理数值和离散数据。

    (3)按照聚类的尺度,聚类方法可被分为以下三种:

    基于距离的聚类算法:用各式各样的距离来衡量数据对象之间的相似度,如k-means、k-medoids、BIRCH、CURE等算法。

    基于密度的聚类算法:相对于基于距离的聚类算法,基于密度的聚类方法主要是依据合适的密度函数等。

    基于互连性(Linkage-Based)的聚类算法:通常基于图或超图模型。高度连通的数据聚为一类。

    (4)按照聚类分析算法的主要思路,可被归纳为如下几种:

    划分法(Partitioning Methods):基于一定标准构建数据的划分。属于该类的聚类方法有:k-means、k-modes、k-prototypes、k-medoids、PAM、CLARA、CLARANS等。

    层次法(Hierarchical Methods):对给定数据对象集合进行层次的分解。

    密度法(density-based Methods):基于数据对象的相连密度评价。

    网格法(Grid-based Methods):将数据空间划分成为有限个单元(Cell)的网格结构,基于网格结构进行聚类。

    模型法(Model-Based Methods):给每一个簇假定一个模型,然后去寻找能够很好的满足这个模型的数据集。 

    6. 划分方法

    给定一个有n个对象的数据集,划分聚类技术将构造数据k个划分,每一个划分就代表一个簇,k<=n。也就是说,它将数据划分为k个簇,而且这k个划分满足下列条件:

            a。每一个簇至少包含一个对象。

            b。每一个对象属于且仅属于一个簇。

    对于给定的k,算法首先给出一个初始的划分方法,以后通过反复迭代的方法改变划分,使得每一次改进之后的划分方案都较前一次更好。

    启发式方法: k-平均算法和k-中心点算法

            k-均值算法:每个簇用该簇中对象的平均值来表示。

            k-中心点算法:每个簇用接近聚类中心的一个对象来表示

    k-means算法

    (1)步骤

    首先将所有对象随机分配到k个非空的簇中

    计算每个簇的平均值,并用该平均值代表相应的簇。

    根据每个对象与各个簇中心的距离,分配给最近的簇。

    然后转第二步,重新计算每个簇的平均值。这个过程不断重复直到满足某个准则函数才停止。

    (2)算法

    k-means算法

    (3)主要优点

    是解决聚类问题的一种经典算法,简单、快速。

    对处理大数据集,该算法是相对可伸缩和高效率的。

    当结果簇是密集的而簇间区别是明显的时,它的效果较好。

    (4)主要缺点:

    必须事先给出k(要生成的簇的数目),而且对初值敏感,对于不同的初始值,可能会导致不同结果。

    不适合于发现非凸面形状的簇或者大小差别很大的簇。

    对于“躁声”和孤立点数据是敏感的,因为簇的中心是通过计算数据的平均值得到的,这些数据的存在会使聚类的中心发生很大的偏移。

    相关文章

      网友评论

        本文标题:数据挖掘之聚类

        本文链接:https://www.haomeiwen.com/subject/rsjfnxtx.html