AGNES 算法

本贴最后更新于 1624 天前,其中的信息可能已经渤澥桑田

层次凝聚算法——AGNES

AGNES算法是一种基于层次凝聚的聚类算法,它的思想十分朴素。假设现在有一个待聚类的数据集,那么根据分而治之的思想我们可以首先将每一个样本点看成是一个类,然后根据一定的规则将这些比较“小”的类进行合并,进而达到最终想要的结果。

那么这个合并的规则是什么?通常我们将样本点之间的距离看成相似度。在两个小类中,第一个类和第二个类中的点它们之间的距离有很多,如果第一个类有n个样本点,第二个类有m个样本点,那么不同的类点和点之间的距离就会有m*n个,到底如何定义这个规则呢? 一般而言我们有三种方式可采用,不同方式聚类出来的效果可能也不尽相同,即,最小距离,最大距离和平均距离,定义方式皆为字面意思。最小距离就是分处在两个小类中的距离最近的两个点,两点分别处于第一个小类和第二个小类。最大距离也是如此,平均距离就是将两个类之间的点所有距离加权求和,即所有距离除以距离的个数得出的距离就是平均距离。


AGNES算法的伪代码:

1.jpg

代码实现:

import numpy as np import matplotlib.pyplot as plt from sklearn import datasets def findmin(mat): #找出距离最小的两个类 temp=mat[0][1] x=0 y=0 for i in range(mat.shape[0]): for j in range(mat.shape[1]): if mat[i][j]<temp and i!=j: x=i y=j temp=mat[i][j] return [x,y,temp] def dis(X,a,b): #采用最大距离 temp=0 for i in a: for j in b: T=np.linalg.norm(X[i]-X[j],ord=2) if temp<T: temp=T return temp def AGNES(X,k): C=[] m=len(X) for j in range(m): C.append([j]) M=np.zeros((m,m)) for i in range(m): for j in range(i): M[i][j]=np.linalg.norm(X[i]-X[j],ord=2) M[j][i]=M[i][j] q=m while q>k: [x,y,m]=findmin(M) C[x].extend(C[y]) C.pop(y) M=np.delete(M,y,axis=0) #删除第J行和第J列 M=np.delete(M,y,axis=1) for j in range(q-1): M[x][j]=dis(X,C[x],C[j]) #更新距离(这一步可以优化,因为在代码开始阶段就已将所有点之间的距离计算完成。) M[j][x]=M[x][j] q=q-1 return C def plot(X,c): for i in c: x=[] y=[] for j in i: x.append(X[j][0]) y.append(X[j][1]) plt.scatter(x,y) plt.show() if __name__=="__main__": X=datasets.make_blobs(n_samples=300,centers=3,cluster_std=1.0,shuffle=True,random_state=None)[0] c=AGNES(X,3) plot(X,c)

测试结果:
Figure1.png

相关帖子

回帖

欢迎来到这里!

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

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

推荐标签 标签

  • AWS
    11 引用 • 28 回帖 • 8 关注
  • 钉钉

    钉钉,专为中国企业打造的免费沟通协同多端平台, 阿里巴巴出品。

    15 引用 • 67 回帖 • 270 关注
  • 思源笔记

    思源笔记是一款隐私优先的个人知识管理系统,支持完全离线使用,同时也支持端到端加密同步。

    融合块、大纲和双向链接,重构你的思维。

    26157 引用 • 108660 回帖 • 1 关注
  • 程序员

    程序员是从事程序开发、程序维护的专业人员。

    589 引用 • 3528 回帖 • 2 关注
  • Caddy

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

    10 引用 • 54 回帖 • 180 关注
  • Redis

    Redis 是一个开源的使用 ANSI C 语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value 数据库,并提供多种语言的 API。从 2010 年 3 月 15 日起,Redis 的开发工作由 VMware 主持。从 2013 年 5 月开始,Redis 的开发由 Pivotal 赞助。

    284 引用 • 248 回帖
  • HTML

    HTML5 是 HTML 下一个的主要修订版本,现在仍处于发展阶段。广义论及 HTML5 时,实际指的是包括 HTML、CSS 和 JavaScript 在内的一套技术组合。

    108 引用 • 295 回帖 • 1 关注
  • Vim

    Vim 是类 UNIX 系统文本编辑器 Vi 的加强版本,加入了更多特性来帮助编辑源代码。Vim 的部分增强功能包括文件比较(vimdiff)、语法高亮、全面的帮助系统、本地脚本(Vimscript)和便于选择的可视化模式。

    29 引用 • 66 回帖
  • Elasticsearch

    Elasticsearch 是一个基于 Lucene 的搜索服务器。它提供了一个分布式多用户能力的全文搜索引擎,基于 RESTful 接口。Elasticsearch 是用 Java 开发的,并作为 Apache 许可条款下的开放源码发布,是当前流行的企业级搜索引擎。设计用于云计算中,能够达到实时搜索,稳定,可靠,快速,安装使用方便。

    117 引用 • 99 回帖 • 197 关注
  • IDEA

    IDEA 全称 IntelliJ IDEA,是一款 Java 语言开发的集成环境,在业界被公认为最好的 Java 开发工具之一。IDEA 是 JetBrains 公司的产品,这家公司总部位于捷克共和国的首都布拉格,开发人员以严谨著称的东欧程序员为主。

    181 引用 • 400 回帖
  • RemNote
    2 引用 • 16 回帖 • 24 关注
  • OkHttp

    OkHttp 是一款 HTTP & HTTP/2 客户端库,专为 Android 和 Java 应用打造。

    16 引用 • 6 回帖 • 92 关注
  • Postman

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

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

    JWT(JSON Web Token)是一种用于双方之间传递信息的简洁的、安全的表述性声明规范。JWT 作为一个开放的标准(RFC 7519),定义了一种简洁的,自包含的方法用于通信双方之间以 JSON 的形式安全的传递信息。

    20 引用 • 15 回帖 • 26 关注
  • OpenResty

    OpenResty 是一个基于 NGINX 与 Lua 的高性能 Web 平台,其内部集成了大量精良的 Lua 库、第三方模块以及大多数的依赖项。用于方便地搭建能够处理超高并发、扩展性极高的动态 Web 应用、Web 服务和动态网关。

    17 引用 • 50 关注
  • gRpc
    11 引用 • 9 回帖 • 100 关注
  • MyBatis

    MyBatis 本是 Apache 软件基金会 的一个开源项目 iBatis,2010 年这个项目由 Apache 软件基金会迁移到了 google code,并且改名为 MyBatis ,2013 年 11 月再次迁移到了 GitHub。

    173 引用 • 414 回帖 • 364 关注
  • WebSocket

    WebSocket 是 HTML5 中定义的一种新协议,它实现了浏览器与服务器之间的全双工通信(full-duplex)。

    48 引用 • 206 回帖 • 281 关注
  • 游戏

    沉迷游戏伤身,强撸灰飞烟灭。

    187 引用 • 831 回帖
  • 宕机

    宕机,多指一些网站、游戏、网络应用等服务器一种区别于正常运行的状态,也叫“Down 机”、“当机”或“死机”。宕机状态不仅仅是指服务器“挂掉了”、“死机了”状态,也包括服务器假死、停用、关闭等一些原因而导致出现的不能够正常运行的状态。

    13 引用 • 82 回帖 • 77 关注
  • Q&A

    提问之前请先看《提问的智慧》,好的问题比好的答案更有价值。

    10054 引用 • 45681 回帖 • 69 关注
  • Sublime

    Sublime Text 是一款可以用来写代码、写文章的文本编辑器。支持代码高亮、自动完成,还支持通过插件进行扩展。

    10 引用 • 5 回帖 • 2 关注
  • IPFS

    IPFS(InterPlanetary File System,星际文件系统)是永久的、去中心化保存和共享文件的方法,这是一种内容可寻址、版本化、点对点超媒体的分布式协议。请浏览 IPFS 入门笔记了解更多细节。

    20 引用 • 245 回帖 • 232 关注
  • CloudFoundry

    Cloud Foundry 是 VMware 推出的业界第一个开源 PaaS 云平台,它支持多种框架、语言、运行时环境、云平台及应用服务,使开发人员能够在几秒钟内进行应用程序的部署和扩展,无需担心任何基础架构的问题。

    5 引用 • 18 回帖 • 192 关注
  • Office

    Office 现已更名为 Microsoft 365. Microsoft 365 将高级 Office 应用(如 Word、Excel 和 PowerPoint)与 1 TB 的 OneDrive 云存储空间、高级安全性等结合在一起,可帮助你在任何设备上完成操作。

    5 引用 • 34 回帖 • 1 关注
  • Kotlin

    Kotlin 是一种在 Java 虚拟机上运行的静态类型编程语言,由 JetBrains 设计开发并开源。Kotlin 可以编译成 Java 字节码,也可以编译成 JavaScript,方便在没有 JVM 的设备上运行。在 Google I/O 2017 中,Google 宣布 Kotlin 成为 Android 官方开发语言。

    19 引用 • 33 回帖 • 82 关注
  • API

    应用程序编程接口(Application Programming Interface)是一些预先定义的函数,目的是提供应用程序与开发人员基于某软件或硬件得以访问一组例程的能力,而又无需访问源码,或理解内部工作机制的细节。

    79 引用 • 431 回帖