文档章节

【谱聚类算法总结】

o
 osc_1ee7cxmx
发布于 2018/08/06 20:16
字数 768
阅读 0
收藏 0

精选30+云产品,助力企业轻松上云!>>>

前言:以前只是调用过谱聚类算法,我也不懂为什么各家公司都问我一做文字检测的这个算法具体咋整的,没整明白还给我挂了哇擦嘞?讯飞还以这个理由刷本宝,今天一怒把它给整吧清楚了,下次谁再问来!说不晕你算我输!

一、解释:

   谱聚类是一种基于图论的算法,主要思想是把所有的数据看做空间中的点,这些点之间用带权边连接,距离越近权重越大,通过对这些点组成的图进行切割,让切图后的子图间的权重和尽可能小,子图内的权重尽可能大,从而达到聚类的目的。

   切图的过程是:定义一个子图与其他子图间的权重和,同时要求每个子图的个数不能太少,这样图切问题就转换为了最小化这个权重和/子图个数的过程。优化这个过程我们定义一个指示矩阵h,要分为的类别是(A1,A2...Ak),i属于Aj类则hij≠0,否则等于0,这样优化式子得到h之后我们就能知道各个节点的类别。根据分析得知,这个h的解与拉普拉斯矩阵L和权重矩阵D有关,具体来说是D-1/2LD-1/2的k个最小的特征值对应的特征向量,这样我们就得到了h,也将维度从n降到了k。一般来说需要对h进行按行进行标准化,然后再对这个n*k的矩阵按行进行kmeans聚类,就得到了最终的聚类结果。

二、推导:

  

    

三、步骤:    

    输入:样本集D=(x1,x2,...,xn),相似矩阵的生成方式, 降维后的维度k1, 聚类方法,聚类后的维度k2

  输出: 簇划分C(c1,c2,...ck2). 

    1) 根据输入的相似矩阵的生成方式构建样本的相似矩阵S。

    2)根据相似矩阵S构建邻接矩阵W,构建度矩阵D。

    3)计算出拉普拉斯矩阵L。

    4)构建标准化后的拉普拉斯矩阵D−1/2LD−1/2

    5)计算D1/2LD1/2最小的k1个特征值所各自对应的特征向量f。

    6) 将各自对应的特征向量f组成的矩阵按行标准化,最终组成n×k1维的特征矩阵F。

    7)对F中的每一行作为一个k1维的样本,共n个样本,用输入的聚类方法进行聚类,聚类维数为k2

    8)得到簇划分C(c1,c2,...ck2)。

四、优缺点:

   优点:只需要相似度矩阵,方便处理稀疏数据的聚类;使用了降维,处理高维数据效果比传统聚类方法好。

   缺点:如果降维的幅度不够,效果和效率均不够好;依赖于相似度矩阵。

五、链接:

   https://www.cnblogs.com/pinard/p/6221564.html

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

Java线程池

前言 Java中对线程池的抽象是ThreadPoolExecutor类,Executors是一个工具类,内置了多种创建线程池的方法: newFixedThreadPool:固定长度线程池 newCachedThreadPool :可缓存线程池 newSin...

nullpointerxyz
25分钟前
35
0
Python笔记:用Python制作二维码

这些年,二维码在我国的日常使用频率特别大。因为其具有简单及安全性吧!除了用网络工具制作二维码,其实用JavaScript或Python也可以制作二维码,而且更有个性。 示例一(制作普通黑白二维码...

tengyulong
37分钟前
0
0
Redis-初体验/数据结构

定义: Redis 是 C 语言开发的一个开源的(遵从 BSD 协议)高性能键值对(key-value)的内存数据库,可以用作数据库、缓存、消息中间件等。它是一种 NoSQL(not-only sql,泛指非关系型数据库...

心田已荒
40分钟前
15
0
如何在保留订单的同时从列表中删除重复项? - How do you remove duplicates from a list whilst preserving order?

问题: Is there a built-in that removes duplicates from list in Python, whilst preserving order? 是否有内置的程序在保留顺序的同时从Python列表中删除重复项? I know that I can us...

fyin1314
今天
29
0
以太坊智能合约开发常见的10个安全问题

本文介绍CheckMarx安全研究小组通过扫描公开的以太坊智能合约所发现的Solidity智能合约开发中常见的十大安全问题,其中__未检查的外部调用__ 和 高成本循环 分列排行榜前两名。该安全问题排行...

区块链教程
今天
19
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部