人工智能|机器学习——CURE聚类算法(层次聚类)

1.CURE聚类概述

绝大多数聚类算法或者擅长处理球形和相似大小的聚类.或者在存在孤立点时变得比较脆弱。CURE采用了一种新颖的层次聚类算法.该算法选择基于质心和基于代表对象方法之间的中间策略。它不同于单个质心或对象来代表一个类,而是选择数据空间中固定数目的具有代表性的点。一个类的代表点通过如下方式产生:首先选择类中分散的对象,然后根据一个特定的分数或收缩因子“收缩”或移动它们。在算法的每一步,有最近距离的代表点对(每个点来自于一个不同的类)的两个类被合并。

每个类有多于一个的代表点使得CURE可以适应非球形的几何形状。类的收缩或凝聚可以有助于控制孤立点的影响。因此,CURE对孤立点的处理更加健壮,而且能够识别非球形和大小变化比较大的类。针对大型数据库,CURE采用随机取样和划分两种方法组合:一个随机样本首先被划分,每个划分被部分聚类。

2 算法步骤

  • 从源数据对象中抽取一个随机样本S;
  • 将样本S分割成一组划分;
  • 对每个划分局部的聚类;
  • 通过随机样本剔除孤立点。如果一个类增长缓慢就去除它;
  • 对局部的类进行聚类,落在每个新形成的类中的代表点根据用户定义的一个收缩因子收缩或向类中心移动。这些点代表和捕捉到了类的形状。
  • 用相应的类标签来标记数据。

3.CURE 聚类特点

CURE,Clustering Using Representative 算法的特点如下:

  • (1)属于凝聚层次聚类

CURE 算法首先把每个数据点看成一个簇,然后将距离最近的簇 结合,一直到簇的个数达到要求的 K 个为止。

  • (2)适应非球形的几何形状

不同于一个质心或者单个点来代表一个类,CURE 算法中每个簇有多个代表点,这使得 CURE算法可以适应非球形的几何形状。

代表点的选取:
首先选择簇中距离质心最远的点做为第一个点,然后依次选择距离已选到的点最远的点,直到选到c 个点为止,这些点尽量得分散,捕获了簇的形状和大小。

  • (3)对孤立点的处理更加健壮

另外,CURE 算法还通过“收缩因子”减少离群点对聚类效果的影响。

代表点的收缩或凝聚:
将上面选取到的代表点根据固定的参数α(0≤α≤1 )向该簇的质心收缩,距离质心越远的点(例如离群点)的收缩程度越大,因此CURE对离群点是不太敏感的,这种方法可以有效的降低离群点带来的不利影响。

收缩系数α的取值不同,聚类结果也相应不同。

当 α 趋于 0 时,所有的“代表点”都汇聚到质心,算法退化为基于“质心”的聚类;
当 α 趋于 1 时,“代表点”完全没有收缩,算法退化为基于“全连接”的聚类,
因此 α 值需要根据数据特征灵活选取,才能得到更好的聚类结果

在得到收缩后的代表点后,两个簇之间的距离就可以定义为这两个簇中距离最近的两个代表点之间的距离

  • (4)识别异常值/离群点

CURE 算法分两个阶段消除异常值的影响。

第一个阶段、是在聚类算法执行到某一阶段(或称当前的簇总数减小到某个值)时,根据簇的增长速度和簇的大小对离群点进行一次识别。

第一阶段,将聚类过程中类成员增长非常缓慢的类作为异常值剔除;

CURE算法由于异常值同其他对象的距离更大,所以其所在类中对象数目的增大就会非常缓慢,甚至不增长。

需要注意的是:
如果这个阶段选择的较早(簇总数过大)的话,会将一部分本应被合并的簇识别为离群点;
如果这个阶段选择的较晚(簇总数过少)的话,离群点很可能在被识别之前就已经合并到某些簇中;
因此原文推荐当前簇的总数为数据集大小的1/3时,进行离群点的识别。

第一阶段有一个很明显的问题,就是当随机采样到的离群点分布的比较近时(即使可能性比较小),这些点会被合并为一个簇,而导致无法将他们识别出来,这时就需要第二阶段的来进行处理。

第二阶段,是指在聚类的最后阶段,将非常小的簇删除;

由于离群点占的比重很小,而在层次聚类的最后几步中,每个正常簇的粒度都是非常高的,因此很容易将他们识别出来,一般当簇的总数缩减到大约为 k 时,进行第二阶段的识别。

  • (5)适应大规模数据

为了适应大型数据,CURE算法采用了随机抽样和分割相结合的手段。

随机抽样将原始数据集中的部分点提取出来,然后试图在这些点上实施CURE层次聚类算法,采样形成的数据子集要适应内存的需要并且与原始数据集相比要足够小。因此,这种随机采样的方法会大大提升CURE的执行速度,并且由于采样过程会对离群点进行过滤因而可以提高聚类质量。

另外,CURE算法还引入了分割的手段,即样本分割成几个部门,然后针对各个部分中的对象进行局部聚类,形成子类,再针对子类进行聚类,新出新的类。

4.优缺点

优点

1)可以发现复杂空间的簇

2)受噪点影响小

缺点

1)参数较多,包括采样的大小、聚类的个数、收缩的比例等;

2) 抽样有误差;

3)难以发现形状非常复杂的空间簇(如中空形状),对空间数据密度差异敏感

4)虽然 CURE 聚类是针对大规模数据库设计的算法,但是当数据量剧增时,效率仍然不能满足需求

5.Python实现

# -*- coding: utf-8 -*-

###########################################################################################
# Implementation of CURE (Clustering Using Representatives) Clustering Algorithm
# Author for codes: Chu Kun(kun_chu@outlook.com)
# Paper: https://www.sciencedirect.com/science/article/pii/S0306437901000084
# Reference: https://github.com/Kchu/CURE-cluster-python
###########################################################################################

import numpy as np
import scipy.spatial.distance as distance
import sys

# Returns the distance between two vectors
def dist(vecA, vecB):
    return np.sqrt(np.power(vecA - vecB, 2).sum())

# This class describes the data structure and method of operation for CURE clustering.
class CureCluster:
    def __init__(self, id__, center__):
        self.points = center__
        self.repPoints = center__
        self.center = center__
        self.index = [id__]
        
    def __repr__(self):
        return "Cluster " + " Size: " + str(len(self.points))
    
    # Computes and stores the centroid of this cluster, based on its points
    def computeCentroid(self, clust):
        totalPoints_1 = len(self.index)
        totalPoints_2 = len(clust.index)
        self.center = (self.center*totalPoints_1 + clust.center*totalPoints_2) / (totalPoints_1 + totalPoints_2)
    
    # Computes and stores representative points for this cluster
    def generateRepPoints(self, numRepPoints, alpha):
        tempSet = None
        for i in range(1, numRepPoints+1):
            maxDist = 0
            maxPoint = None
            for p in range(0, len(self.index)):
                if i == 1:
                    minDist = dist(self.points[p,:], self.center)
                else:
                    X = np.vstack([tempSet, self.points[p, :]])
                    tmpDist = distance.pdist(X)
                    minDist = tmpDist.min()
                if minDist >= maxDist:
                    maxDist = minDist
                    maxPoint = self.points[p,:]
            if tempSet is None:
                tempSet = maxPoint
            else:
                tempSet = np.vstack((tempSet, maxPoint))
        for j in range(len(tempSet)):
            if self.repPoints is None:
                self.repPoints = tempSet[j,:] + alpha * (self.center - tempSet[j,:])
            else:
                self.repPoints = np.vstack((self.repPoints, tempSet[j,:] + alpha * (self.center - tempSet[j,:])))

    # Computes and stores distance between this cluster and the other one.
    def distRep(self, clust):
        distRep = float('inf')
        for repA in self.repPoints:
            if type(clust.repPoints[0]) != list:
                repB = clust.repPoints
                distTemp = dist(repA, repB)
                if distTemp < distRep:
                    distRep = distTemp
            else:
                for repB in clust.repPoints:
                    distTemp = dist(repA, repB)
                    if distTemp < distRep:
                        distRep = distTemp
        return distRep

    # Merges this cluster with the given cluster, recomputing the centroid and the representative points.
    def mergeWithCluster(self, clust, numRepPoints, alpha):
        self.computeCentroid(clust)
        self.points = np.vstack((self.points, clust.points))
        self.index = np.append(self.index, clust.index)
        self.repPoints = None
        self.generateRepPoints(numRepPoints, alpha)

# Describe the process of the CURE algorithm
def runCURE(data, numRepPoints, alpha, numDesCluster):

    # Initialization
    Clusters = []
    numCluster = len(data)
    numPts = len(data)
    distCluster = np.ones([len(data), len(data)])
    distCluster = distCluster * float('inf')
    for idPoint in range(len(data)):
        newClust = CureCluster(idPoint, data[idPoint,:])
        Clusters.append(newClust)
    for row in range(0, numPts):
    	for col in range(0, row):
    		distCluster[row][col] = dist(Clusters[row].center, Clusters[col].center)
    while numCluster > numDesCluster:
        if np.mod(numCluster, 50) == 0:
            print('Cluster count:', numCluster)

        # Find a pair of closet clusters
        minIndex = np.where(distCluster == np.min(distCluster))
        minIndex1 = minIndex[0][0]
        minIndex2 = minIndex[1][0]

        # Merge
        Clusters[minIndex1].mergeWithCluster(Clusters[minIndex2], numRepPoints, alpha)
        # Update the distCluster matrix
        for i in range(0, minIndex1):
            distCluster[minIndex1, i] = Clusters[minIndex1].distRep(Clusters[i])
        for i in range(minIndex1+1, numCluster):
            distCluster[i, minIndex1] = Clusters[minIndex1].distRep(Clusters[i])
        # Delete the merged cluster and its disCluster vector.
        distCluster = np.delete(distCluster, minIndex2, axis=0)
        distCluster = np.delete(distCluster, minIndex2, axis=1)
        del Clusters[minIndex2]
        numCluster = numCluster - 1

    print('Cluster count:', numCluster)
    # Generate sample labels
    Label = [0] * numPts
    for i in range(0, len(Clusters)):
        for j in range(0, len(Clusters[i].index)):
            Label[Clusters[i].index[j]] = i + 1

    return Label

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/457625.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

远程办公、企业内网服务器的Code-Server上如何配置使用CodeGeeX插件

很多小伙伴都会在工作中使用code-server&#xff0c;比如说远程办公&#xff0c;当你需要在家访问你的工作环境&#xff0c;亦或者是你们公司的Docker是放入服务器中。code-server 无疑是最好的选择&#xff0c;它可以让你通过互联网安全地连接到远程服务器上的开发环境并且使用…

UE5 android打包

下载安装JDK https://repo.huaweicloud.com/java/jdk/https://repo.huaweicloud.com/java/jdk/ 选择对应的jdk版本 配置环境变量 编辑Path 验证是否成功 java -version 安装Android Studio https://developer.android.google.cn/studio?hlzh-cnhttps://developer.androi…

C# 连接neo4j数据库,包括非默认的neo4j默认库

官方文档没找见&#xff0c;自己在源码里面找到的 private string _dbHost "bolt://localhost:7687"; private string _dbUser "neo4j"; private string _dbPassword "******"; private IDriver? _driver;public CQLOperation(string _data…

HTTPS基础

目录 HTTPS简介 HTTP与HTTPS的区别 CA证书 案例 服务器生成私钥与证书 查看证书和私钥存放路径 Cockpit(图像化服务管理工具) HTTPS简介 超文本传输协议HTTP协议被用于在Web浏览器和网站服务器之间传递信息。HTTP协议以明文方式发送内容&#xff0c;不提供任何方式的数据加密&…

以题为例浅谈SSRF

什么是ssrf SSRF(Server-Side Request Forgery:服务器端请求伪造) 是一种由攻击者构造形成由服务端发起请求的一个安全漏洞。 一般情况下&#xff0c;SSRF攻击的目标是从外网无法访问的内部系统。&#xff08;正是因为它是由服务端发起的&#xff0c;所以它能够请求到与它相连…

怎么避免电脑数据被拷贝?电脑如何禁用USB功能?

在无纸化办公的今天&#xff0c;很多重要数据都存放在电脑中。为了避免数据泄露&#xff0c;需要采用安全的方式保护电脑数据。那么&#xff0c;该如何避免电脑数据被拷贝呢&#xff1f;下面我们就来了解一下。 方法一&#xff1a;物理隔绝 物理隔绝是一种原始但有效的USB禁用…

数码管的动态显示(三)

1.原理 data_reg寄存&#xff0c;只寄存符号位和数据位不包含小数点位。 动态数码管每个显示1ms&#xff0c;所以计数到5*10^4-1 为了将sel和seg同步&#xff0c;把sel打了一拍。 6位都使用到了可以这么计算&#xff0c;6位都显示的是数据。或者最高位显示的是小数点&#xff…

ubuntu 下git常用指令【持续更新中】

1.下载 sudo apt install git 2. 查看版本 git --version3. 登录git账号 git config --global user.email "youexample.com" git config --global user.name "Your Name"4.生成密钥对 ssh-keygen -t rsa -C "your_emailyouremail.com"复制公…

鸿蒙Harmony应用开发—ArkTS声明式开发(容器组件:EffectComponent)

特效合并容器组件&#xff0c;用于子节点特效绘制的合并&#xff0c;实现特效的绘制性能优化。 说明&#xff1a; 该组件从API Version 10开始支持。后续版本如有新增内容&#xff0c;则采用上角标单独标记该内容的起始版本。 该组件为系统接口。 目前该组件仅支持子组件背景…

LORA_ LOW-RANK ADAPTATION OF LARGE LANGUAGE MODELS

paper: https://arxiv.org/pdf/2106.09685.pdf code: https://github.com/microsoft/LoRA 摘要 作者提出了低秩自适应&#xff0c;或称LoRA&#xff0c;它冻结了预先训练的模型权值&#xff0c;并将可训练的秩分解矩阵注入变压器架构的每一层&#xff0c;大大减少了下游任务的…

接上一篇:分布式调用链追踪系统设计

所以必须得记录父子关系&#xff1a; A---->B 是 B---->C 的父调用 A---->D 是 D---->E 的父调用 A---->D 还是 D---->F 的父调用 如何记录呢&#xff1f;需要给每个调用分配一个ID (称为 SpanID)&#xff0c;并且把这个 ID 传递给子调用&#xff0c; 子…

网络基础 - 预备知识(协议、网络协议、网络传输流程、地址管理)

文章目录 1. 认识 协议2. 了解 网络协议2.1 引入 协议分层2.2 OSI 七层模型 与 TCP/IP 四层模型 3. 网络传输 流程&#xff01;&#xff01;&#xff01;3.1 网络传输流程图3.2 关于报头3.3 实例解释 传输过程&#xff08;封装与解包&#xff09; 4. 网络中的地址管理4.1 认识 …

使用Python批量实现在Excel里新加一列

目录 一、引言 二、所需库介绍 三、代码实现 四、批量处理多个Excel文件 五、注意事项与扩展 六、案例演示 七、总结与展望 一、引言 Excel作为广泛使用的电子表格软件&#xff0c;在数据处理和分析中扮演着重要角色。然而&#xff0c;当面对大量Excel文件需要批量处理…

Apache Paimon 的 CDC Ingestion 概述

CDC Ingestion 1&#xff09;概述 Paimon支持schema evolution将数据插入到Paimon表中&#xff0c;添加的列将实时同步到Paimon表&#xff0c;并且无需重启同步作业。 目前支持的同步方式如下&#xff1a; MySQL Synchronizing Table: 将MySQL中的一个或多个表同步到一个Pa…

win11系统qtcreator构建运行程序首次启动卡顿(win11首次启动应用程序卡顿)

首先可以参考一下这个博客&#xff1a;为什么win11系统开机后第一次打开一个软件很慢&#xff0c;关闭进程重新打开速度就正常了&#xff0c;该怎样解决呢&#xff1f; - 知乎 经过上述博客&#xff0c;但是我没有完全解决&#xff0c;这里说一下自己的方法&#xff1a; 打开任…

ArrayList 和 LinkedList 有什么区别?

1、典型回答 ArrayList 和 LinkedList 是 Java 中常用的集合类&#xff0c;它们都实现了 List 接口&#xff0c;如下图所示&#xff1a; 但二者有以下几点不同&#xff1a; 1、底层数据结构实现不同&#xff1a; ArrayList 底层使用数组实现&#xff0c;它通过一个可调整大小…

泽众云真机-机型支持ADB调试功能即将上线

最近云真机平台在线客服&#xff0c;收到很多咨询关于ADB调试功能&#xff0c;什么时候能更新&#xff1f;据小编所知&#xff0c;正在升级之中&#xff0c;有一块专门为了解决ADB调试功能提前准备&#xff0c;升级网络硬件设备&#xff0c;目前平台的功能已开发完成&#xff0…

Python Web开发记录 Day8:Django part2 部门管理

名人说&#xff1a;莫道桑榆晚&#xff0c;为霞尚满天。——刘禹锡&#xff08;刘梦得&#xff0c;诗豪&#xff09; 创作者&#xff1a;Code_流苏(CSDN)&#xff08;一个喜欢古诗词和编程的Coder&#x1f60a;&#xff09; 目录 1、部门列表2、模板的继承3、添加部门4、编辑部…

【Leetcode每日一刷】顺/逆时针旋转矩阵 |48. 旋转图像、矩阵的螺旋遍历 |54. 螺旋矩阵

一、48. 旋转图像 1.1&#xff1a;题目 48. 旋转图像 1.2&#xff1a;解题思路 题型&#xff1a;顺/逆时针旋转矩阵&#xff1b; ❗❗核心思想/ 关键&#xff1a;不可暴力模拟&#xff0c;先镜像&#xff0c;后水平翻转 这题的意思很简单&#xff0c;就是让我们把矩阵顺时…

解决内网环境预览ArcGIS地图服务

目录 背景分析解决思路操作步骤1、登录ArcGIS Server后台修改 2、将预览服务请求资源部署到内网①下载ArcGIS API for JavaScript 库②修改ArcGIS API for JavaScript 库③映射ArcGIS API for JavaScript 库④验证ArcGIS API for JavaScript 映射3、验证ArcGIS Server的服务 背…