数据挖掘算法初窥门庭--聚类

本贴最后更新于 3171 天前,其中的信息可能已经斗转星移

#聚类(Cluster)
##概念
什么是聚类:
按照个体或样品的特征将它们分类,使同一类别的个体具有尽可能高的同质性,而类别之间则应该具有尽可能高的异质性。
聚类的特点:
不是一种统计方法,而是数据处理技术;需要自定聚类变量以及类别个数,属于非监督的分析方法;一般不涉及有关统计量的分布;不需要进行显著性检验;聚类算法比距离算法对结果影响更大;样本的顺序会影响聚类的结果。
一些重要概念:

  • 聚类变量:一组表示个体特征的变量。完全由研究者规定,会对结果产生较大的影响。需要需要对变量进行标准化处理。
  • 类别个数:聚类结果类别的个数。完全由研究者规定,不管实际数据中是否存在不同的类别吗,都能得到若干类别的解。
  • 个体同质程度:有两种方式进行测量
    • 采用描述个体之间的接近程度指标(数量),如“距离”:欧式距离、 曼哈顿距离等
    • 采用描述铬铁之间的相似程度指标(模式),如“相关系数”:皮尔逊相关系数

##快速聚类和两阶段聚类
根据聚类算法的处理过程可以分为:快速聚类和两阶段聚类。

  • 快速聚类:
    • 思想:
      选取 k 个观测量作为初始聚类中心,以距离最小原则将样本分配到 k 个类中,在每个类中以一定的方法重新选举聚类中心。不断迭代,直到收敛或满足要求。
    • 特点:
      一般只能处理数值型的变量;噪声对结果影响比较大;强线性关系变量会导致重复贡献影响结果。
  • 两阶段聚类:
    • 思想:
      将聚类分为预聚类(类数目增加)和聚类(类数目减少)两个阶段,类似于,构造一棵树,从根向上不断生长出更多的分支,然后对树进行修剪,把小的分支处理掉,合并留下的大分支。
    • 特点:
      可以处理数值型和分类型的变量;自动确定最优聚类数目;诊断离群点和噪声数据;可缩放性强。

##常见算法
根据算法思想可以把聚类算法分为下列类型。下面我们简单学习各种算法的思想,特点,优缺点等。具体算法在实践中再进行具体的学习。

###划分算法
思想:划分算法属于快速聚类的方法。

1.选取 k 个观测量作为初始聚类中心
2.以距离最小原则将每个实例分配到 k 个类中
3.在每个类中以一定的方法重新选举聚类中心
4.不断迭代,直到收敛或满足要求

  • k-means 算法

    • 特点:初始类中心选取是任意的,类中心的再选举采用类中所有对象的均值。
    • 优点:算法简单,也是最常用的聚类算法;对大数据是可伸缩的且效率高,时间复杂度接近于线性。
    • 缺点:初始值的选取会对结果产生较大的影响;对脏数据很敏感;只能处理数值类型数据
  • k-medoids 算法

    • 特点:是对 K-MEANS 算法的改进,类中心(medoids)的再选举采用的是选取到类中其他点距离之和最小的点。
    • 优点:对脏数据不敏感
    • 缺点:选取类中心计算量大,一般只能用于小数据集
  • clara 算法

    • 特点:是 k-medoids 效率不好的解决方案,在选举类中心时,使用抽样数据代替整个数据集
    • 优点:提高选举类中心的效率
    • 缺点:效率取决于采样的大小,采样大小决定了聚类的结果,一般不太可能得到最佳结果
  • clarans

    • 特点:是对 clara 的改进:clara 在选举类中心时是用的采用是不变的,clarans 算法在没一次迭代使用的采样都是不一样的。
    • 优点:解决 clara 算法无法得到最佳结果的问题
    • 缺点:必须人为限定迭代次数。
k-means 是一种典型的划分聚类算法,它用一个聚类的中心来代表一个簇,即在迭代过程中选择的聚点不一定是聚类中的一个点,该算法只能处理数值型数据
k-modes K-Means算法的扩展,能够处理分类数据,采用简单匹配方法来度量分类型数据的相似度
k-prototypes 结合了K-Means和K-Modes两种算法,能够处理混合型数据
k-medoids 在迭代过程中选择簇中到其他点距离之和最小的点为中心,PAM是典型的k-medoids算法
CLARA CLARA算法在PAM的基础上采用了抽样技术,能够处理大规模数据
CLARANS CLARANS算法融合了PAM和CLARA两者的优点,是第一个用于空间数据库的聚类算法, 该算法适用于处理数值型数据

###层次算法
层次聚类方法是对给定数据集进行层次分解明知道某种条件满足为止。具体可以分为凝聚和分裂两种方案。

  • 凝聚:自底向上,首先每个对象作为一簇,然后合并这些原子簇,知道某个条件被满足。
  • 分裂:自顶向下,首先将所有的对象置于同一个簇,然后逐渐分裂为更小的簇,直到某个条件被满足。
CURE 采用抽样技术先对数据集随机抽取样本,再采用分区技术对样本进行分区,然后对每个分区局部聚类,最后对局部聚类进行全局聚类。适合处理数值型数据类型
ROCK 也采用了随机抽样技术,该算法在计算两个对象的相似度时,同时考虑了周围对象的影响,适合处理混合型数据类型
CHEMALOEN(变色龙算法) 首先由数据集构造成一个K-最近邻图Gk ,再通过一个图的划分算法将图Gk 划分成大量的子图,每个子图代表一个初始子簇,最后用一个凝聚的层次聚类算法反复合并子簇,找到真正的结果簇
SBAC SBAC算法则在计算对象间相似度时,考虑了属性特征对于体现对象本质的重要程度,对于更能体现对象本质的属性赋予较高的权值
BIRCH BIRCH算法利用树结构对数据集进行处理,叶结点存储一个聚类,用中心和半径表示,顺序处理每一个对象,并把它划分到距离最近的结点,该算法也可以作为其他聚类算法的预处理过程。适合处理数值型数据类型
BUBBLE BUBBLE算法则把BIRCH算法的中心和半径概念推广到普通的距离空间
BUBBLE-FM BUBBLE-FM算法通过减少距离的计算次数,提高了BUBBLE算法的效率

###密度算法
基于距离的算法只能发现“类圆形”的聚类,基于密度的算法克服了这个缺点。
密度算法的知道思想是,当一个区域中的点的密度大于某个阈值,就把它加入到与之相近的聚类中去。

DBSCAN 采用空间索引技术来搜索对象的邻域,引入了“核心对象”和“密度可达”等概念,从核心对象出发,把所有密度可达的对象组成一个簇,适合处理数值型数据类型
GDBSCAN 算法通过泛化DBSCAN算法中邻域的概念,以适应空间对象的特点
OPTICS OPTICS算法结合了聚类的自动性和交互性,先生成聚类的次序,可以对不同的聚类设置不同的参数,来得到用户满意的结果
FDC FDC算法通过构造k-d tree把整个数据空间划分成若干个矩形空间,当空间维数较少时可以大大提高DBSCAN的效率

###网格算法
基于网格的算法先将数据空间划分为有限个单元的网格结构,所有的处理都是以单个的单元为对象。网格算法的特点是处理速度很快,通常于单元个数有关而与记录个数无关。

STING 利用网格单元保存数据统计信息,从而实现多分辨率的聚类
WaveCluster 在聚类分析中引入了小波变换的原理,主要应用于信号处理领域。只能处理数值型数据类型
CLIQUE 是一种结合了网格和密度的聚类算法,适合处理数值型数据类型

###模型算法
基于模型的方法给每一个聚类假定一个模型,然后去寻找能够很好满足这个模型的数据集。这种算法的潜在假定是:目标数据集是由一系列的概率分布决定的。

AutoClass 是以概率混合模型为基础,利用属性的概率分布来描述聚类,该方法能够处理混合型的数据,但要求各属性相互独立
自组织神经网络SOM 由外界输入不同的样本到人工的自组织映射网络中,一开始时,输入样本引起输出兴奋细胞的位置各不相同,但自组织后会形成一些细胞群,它们分别代表了输入样本,反映了输入样本的特征

###weka 中的聚类算法

  • EM,用户可指定需要产生多少聚类,否则所用的算法可通过交叉验证来决定,用户可指定循环次数的最大值,并且为正常的密度计算设定可允许的最小标准差。

  • SimpleKMeans 使用 k 均值来聚类数据;聚类的数量通过一个参数设定。

  • Cobweb 实现了用于名词属性的 Cobweb 算法和用于数值性属性的 Classit 算法。

  • FarthestFirst 实现 Hochbaum 和 Shmoys 远端优先遍历算法。

  • MakeDensityBaseCluster 是一个元聚类器,它包装一个聚类算法,使其返回一个概率分布和密度。它为每个聚类拟合一个离散分布,或一个对称的正态分布。

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...
  • ss

    @88250 这个给老大看看不错,老大的那个分类方法最终实现离不开这些东东呢。既然是学 java 的,不知到有没有把 scala 和 spark 一块学了?

  • 88250

    @ss 木。

推荐标签 标签

  • Swagger

    Swagger 是一款非常流行的 API 开发工具,它遵循 OpenAPI Specification(这是一种通用的、和编程语言无关的 API 描述规范)。Swagger 贯穿整个 API 生命周期,如 API 的设计、编写文档、测试和部署。

    26 引用 • 35 回帖 • 1 关注
  • 工具

    子曰:“工欲善其事,必先利其器。”

    286 引用 • 729 回帖
  • 安全

    安全永远都不是一个小问题。

    199 引用 • 816 回帖 • 1 关注
  • Oracle

    Oracle(甲骨文)公司,全称甲骨文股份有限公司(甲骨文软件系统有限公司),是全球最大的企业级软件公司,总部位于美国加利福尼亚州的红木滩。1989 年正式进入中国市场。2013 年,甲骨文已超越 IBM,成为继 Microsoft 后全球第二大软件公司。

    105 引用 • 127 回帖 • 382 关注
  • H2

    H2 是一个开源的嵌入式数据库引擎,采用 Java 语言编写,不受平台的限制,同时 H2 提供了一个十分方便的 web 控制台用于操作和管理数据库内容。H2 还提供兼容模式,可以兼容一些主流的数据库,因此采用 H2 作为开发期的数据库非常方便。

    11 引用 • 54 回帖 • 654 关注
  • 周末

    星期六到星期天晚,实行五天工作制后,指每周的最后两天。再过几年可能就是三天了。

    14 引用 • 297 回帖 • 1 关注
  • CSDN

    CSDN (Chinese Software Developer Network) 创立于 1999 年,是中国的 IT 社区和服务平台,为中国的软件开发者和 IT 从业者提供知识传播、职业发展、软件开发等全生命周期服务,满足他们在职业发展中学习及共享知识和信息、建立职业发展社交圈、通过软件开发实现技术商业化等刚性需求。

    14 引用 • 155 回帖
  • Postman

    Postman 是一款简单好用的 HTTP API 调试工具。

    4 引用 • 3 回帖 • 3 关注
  • iOS

    iOS 是由苹果公司开发的移动操作系统,最早于 2007 年 1 月 9 日的 Macworld 大会上公布这个系统,最初是设计给 iPhone 使用的,后来陆续套用到 iPod touch、iPad 以及 Apple TV 等产品上。iOS 与苹果的 Mac OS X 操作系统一样,属于类 Unix 的商业操作系统。

    85 引用 • 139 回帖 • 1 关注
  • SSL

    SSL(Secure Sockets Layer 安全套接层),及其继任者传输层安全(Transport Layer Security,TLS)是为网络通信提供安全及数据完整性的一种安全协议。TLS 与 SSL 在传输层对网络连接进行加密。

    70 引用 • 193 回帖 • 431 关注
  • Sym

    Sym 是一款用 Java 实现的现代化社区(论坛/BBS/社交网络/博客)系统平台。

    下一代的社区系统,为未来而构建

    524 引用 • 4601 回帖 • 700 关注
  • Unity

    Unity 是由 Unity Technologies 开发的一个让开发者可以轻松创建诸如 2D、3D 多平台的综合型游戏开发工具,是一个全面整合的专业游戏引擎。

    25 引用 • 7 回帖 • 173 关注
  • Hibernate

    Hibernate 是一个开放源代码的对象关系映射框架,它对 JDBC 进行了非常轻量级的对象封装,使得 Java 程序员可以随心所欲的使用对象编程思维来操纵数据库。

    39 引用 • 103 回帖 • 709 关注
  • FFmpeg

    FFmpeg 是一套可以用来记录、转换数字音频、视频,并能将其转化为流的开源计算机程序。

    23 引用 • 32 回帖
  • LaTeX

    LaTeX(音译“拉泰赫”)是一种基于 ΤΕΧ 的排版系统,由美国计算机学家莱斯利·兰伯特(Leslie Lamport)在 20 世纪 80 年代初期开发,利用这种格式,即使使用者没有排版和程序设计的知识也可以充分发挥由 TeX 所提供的强大功能,能在几天,甚至几小时内生成很多具有书籍质量的印刷品。对于生成复杂表格和数学公式,这一点表现得尤为突出。因此它非常适用于生成高印刷质量的科技和数学类文档。

    12 引用 • 54 回帖 • 65 关注
  • 大疆创新

    深圳市大疆创新科技有限公司(DJI-Innovations,简称 DJI),成立于 2006 年,是全球领先的无人飞行器控制系统及无人机解决方案的研发和生产商,客户遍布全球 100 多个国家。通过持续的创新,大疆致力于为无人机工业、行业用户以及专业航拍应用提供性能最强、体验最佳的革命性智能飞控产品和解决方案。

    2 引用 • 14 回帖
  • Python

    Python 是一种面向对象、直译式电脑编程语言,具有近二十年的发展历史,成熟且稳定。它包含了一组完善而且容易理解的标准库,能够轻松完成很多常见的任务。它的语法简捷和清晰,尽量使用无异义的英语单词,与其它大多数程序设计语言使用大括号不一样,它使用缩进来定义语句块。

    543 引用 • 672 回帖 • 1 关注
  • OAuth

    OAuth 协议为用户资源的授权提供了一个安全的、开放而又简易的标准。与以往的授权方式不同之处是 oAuth 的授权不会使第三方触及到用户的帐号信息(如用户名与密码),即第三方无需使用用户的用户名与密码就可以申请获得该用户资源的授权,因此 oAuth 是安全的。oAuth 是 Open Authorization 的简写。

    36 引用 • 103 回帖 • 9 关注
  • CentOS

    CentOS(Community Enterprise Operating System)是 Linux 发行版之一,它是来自于 Red Hat Enterprise Linux 依照开放源代码规定释出的源代码所编译而成。由于出自同样的源代码,因此有些要求高度稳定的服务器以 CentOS 替代商业版的 Red Hat Enterprise Linux 使用。两者的不同在于 CentOS 并不包含封闭源代码软件。

    238 引用 • 224 回帖
  • Vue.js

    Vue.js(读音 /vju ː/,类似于 view)是一个构建数据驱动的 Web 界面库。Vue.js 的目标是通过尽可能简单的 API 实现响应的数据绑定和组合的视图组件。

    266 引用 • 665 回帖
  • SOHO

    为成为自由职业者在家办公而努力吧!

    7 引用 • 55 回帖 • 19 关注
  • Hadoop

    Hadoop 是由 Apache 基金会所开发的一个分布式系统基础架构。用户可以在不了解分布式底层细节的情况下,开发分布式程序。充分利用集群的威力进行高速运算和存储。

    86 引用 • 122 回帖 • 625 关注
  • TGIF

    Thank God It's Friday! 感谢老天,总算到星期五啦!

    287 引用 • 4484 回帖 • 669 关注
  • NGINX

    NGINX 是一个高性能的 HTTP 和反向代理服务器,也是一个 IMAP/POP3/SMTP 代理服务器。 NGINX 是由 Igor Sysoev 为俄罗斯访问量第二的 Rambler.ru 站点开发的,第一个公开版本 0.1.0 发布于 2004 年 10 月 4 日。

    311 引用 • 546 回帖
  • JRebel

    JRebel 是一款 Java 虚拟机插件,它使得 Java 程序员能在不进行重部署的情况下,即时看到代码的改变对一个应用程序带来的影响。

    26 引用 • 78 回帖 • 664 关注
  • Caddy

    Caddy 是一款默认自动启用 HTTPS 的 HTTP/2 Web 服务器。

    12 引用 • 54 回帖 • 165 关注
  • Dubbo

    Dubbo 是一个分布式服务框架,致力于提供高性能和透明化的 RPC 远程服务调用方案,是 [阿里巴巴] SOA 服务化治理方案的核心框架,每天为 2,000+ 个服务提供 3,000,000,000+ 次访问量支持,并被广泛应用于阿里巴巴集团的各成员站点。

    60 引用 • 82 回帖 • 595 关注