Canopy算法中T值选取的优化及聚类效果的改进

2021年第6期China

Computer

&

Communication信IB与电IECanopy算法中T值选取的优化及聚类效果的改进鲁茜蒙祖强”(广西大学计算机与电子信息学院，广西南宁530004

)摘

要：笔者拟通过选取距离数据样本集的中心点最近的点作为初始聚类中心，借用频率分布直方图类比出距离分

布直方图，得到各数据样本点之间的距离，从而找出适宜的Tl、T2取值点，实现对Canopy算法的改进.通过与K-means

算法相结合，发现该改进方法能够提升算法的整体速度，同时对边缘点的聚类效果较原方法比更为清晰.利用GAUSS数

据集和人工数据集对改进后的算法做聚类分析模拟实验，实验结果表明该方法在聚类效果和聚类速度上都有所提升.关键词：聚类算法；改进；优化；结合中图分类号：TP311.

13

文献标识码：A

文章编号：1003-9767

(2021)

06-061-05Optimization

of

T

Value

Selection

and

Improvement

of

Clustering

Effect

in

Canopy

AlgorithmLU

Xi,

MENG

Zuqiang*(School

of computer

and

Electronic

Information,

Guangxi

University,

Nanning

Guangxi

530004,

China)Abstract：

The

author

intends

to

select

the

point closest

to

the

center

point

of the

data

sample

set

as

the

initial

clustering

center,

borrow

the

frequency

distribution

histogram

analogy

to

draw

the

distance

distribution

histogram,

and

obtain

the

distance

between

the

data

sample

points,

so

as

to

find

the

appropriate

Tl,

T2

Take

the

value

point

to

realize

the

improvement

of

Canopy

algorithm.

By

combining

with

the

K-means

algorithm,

it

is

found

that

the

improved

method

can

increase

the

overall

speed

of

the

algorithm,

and

the

clustering

effect

of

edge

points

is

clearer

than

the

original

method.

Using

GAUSS

data

set

and

artificial

data

set

to

do

cluster

analysis

simulation

experiments

on

the

improved

algorithm. The experimental

results

show

that

the

method

has

improved

clustering

effect

and

clustering

ds:

clustering

algorithm;

improvement;

optimization;

combination0引言随着信息技术的飞速发展，海量数据资源呈井喷式增长，

中心，然后在Hadoop分布式集群上运行K-Means算法，实

现在保证精度的情况下提高计算效率囱。陈胜发提出基于密

度权重Canopy的改进K-medoids算法用于提高算法精度旳。

王海燕提出使用Canopy+算法用于实现对Tl、T2的改进［4］0

邵欣欣提出利用共享最近邻相似度算法对聚类结果中的交叉

人们在享受数据分析技术带来便利的同时，如何对数据进行

深入挖掘、整合、再利用，逐渐成为人们关注的焦点。聚类

分析技术作为数据挖掘的一个重要研究领域，经过众多学者

的苦心研究，取得不错的成绩。其中，K-means算法作为划

分聚类的典型代表，因具有算法简单、收敛速度快的优点，

部分数据进行归类，达到提高精准度的目的切。胡小建等提

出依据最大最小原则生成初始聚类中心，并使用K-means聚

被很多专家学者引用，但K-means算法又因其依赖初始条件

中初始聚类k值的确定和初始聚类中心的选取，易形成局部

类算法对其进行优化叫Canopy算法作为一种粗聚类算法,在聚类初值选取的过

程中，对Tl、T2值的选取较为敏感，会直接影响最终的聚

类效果。尽管各专家学者对初始Tl、T2的选取各有研究，

但仍未发现最优的解决策略。为此，本文提出一种类比概率

最优解。为此专家学者提出Canopy算法与K-means算法相

结合的改进策略。针对Canopy-Kmeans算法中初始中心点选取随机、算法

受噪声点影响等问题，李琪等人提出了一种利用密度峰值改

分布直方图的方法，实现对Canopy算法中Tl、T2取值的

进的M-Canopy-Kmeans算法［1IO王颖提出通过密度确定初始 改进。作者简介：鲁茜(1989-),女，河南驻马店人，在职研究生，工程师。研究方向：数据挖掘。通信作者：蒙祖强(1974-),男，广西罗城人，博士研究生，教授。研究方向：跨模态智能、粒计算、数据挖掘与知识发现等。E-mail:

。61

算眩语盲1

China

Computer

&

Communication信IB与电IE2021年第6期Canopy算法的基本原理Canopy算法是一种简单、快捷、准确的对象聚类方法切。

落入各小区间的频数力，并计算频率£。以每个小区间为底、n以%"为高在平面直角坐标系内作小矩形，这些小矩形组成该算法可以实现粗聚类，分别采用近似距离度量的方法以及

两个距离阈值比较的方式实现。Canopy算法的主要思想通过

以下两个过程实现哄5：第一，使用一种简单、快捷的距离

A的图形称为频率分布直方图。统计学中通过频率分布直方图

可以直观表示频率的分布情况，借鉴此方法可以定义距离分

布直方图。计算方法将数据集分为若干可重叠的子集Canopy,不需要指

定k值，但精度较低；第二，与K-means算法相结合，通过

使用距离计算方法计算同一个簇内所有向量的距离。Canopy算法流程如下。第一步，对原数据样本进行排列，可以随机。第二步，选取距离中心点最近的距离为距离阈值T2,距

设｛DQa…门”｝是总体样本，将最小值记为a,将最大

值记为6又设是小于a的最大整数，a”是大于b的最小

离中心点最远的距离为距离阈值T1,且Tl

>

T2O整数,将区间［%,a”］等分成巾个小区间［a(),ai］,(ai,a2］”“,(a”-i,a”］，

区间间隔可根据总体样本量的多少和是否适宜观察进行调

第三步，从初始聚类样本集S中随机选择一个点P,将

整。在直角坐标系中，用横轴表示各个元素之间的欧式距离

P作为第一个簇的聚类中心点心，并将点P从初始聚类样本

集S中移除。第四步，从余下的数据样本集合S中随机选取一个点Q,

计算Q到所有已知聚类中心点的距离，考察其中最小距离D：

Dv,用纵轴表示满足该距离范围的Qy的个数，绘制距离宜

方图，并观察各样本间欧式距离数值的分布情况。2.2方法描述针对Canopy算法的缺点，重点优化改进算法的初值

取值方法和获取的阈值Tl、T2,并结合K-means算法利用

如果T2VDVT1,则用一个弱标记记录Q,表示点Q属于

该簇，将Q加入其中；如果D

表示点Q属于该簇，将Q从数据样本集合S中删除；如果D

Python语言实现。选取距离数据均值点最近的点作为聚类中

心点，以防因选取到噪声点或孤立点对聚类效果造成不利的

>

T1,则Q形成一个新聚类,将Q从数据样本集合S中删除。第五步，重复第四步直到集合S中的元素个数为零。该算法优势可以减少相似样本的计算量。劣势体现在步

影响。阈值选取有多种方式，常见的是通过计算数据点到均

值点的最远距离和最近距离确定Tl、T2的值，本文通过借

骤一中对样本的排列是随机的，取值也可以是随机的，因此

存在噪声点和孤立点。同时Tl、T2的取值会影响Canopy的

重叠率及粒度，当T1过大时，会使样本属于多个簇，各个

用距离直方图选择Tl、T2的值，且Tl

>

T2O连接每个柱

状图的最高点绘制一条曲线，以第2个波峰的顶点为切点做

平行于X轴的切线，向左相交于曲线的第一个点的横坐标的

值为T2O取波谷到第2个波峰之间柱状图上升最快的柱状图

簇区别不明显；当T2过大时，会减少簇个数；当T2过小时,

会增加簇个数，同时增加计算时间。为此对样本点的选取和

的最左边点的横坐标的值为T1。由距离直方图可知，越接近

波峰越代表满足该欧式距离的点分布越多，越接近波谷代表

满足该欧式距离的点分布越少，选取两个波峰间稀疏分布点

Tl、T2的选取是优化的关键。2

Canopy算法优化2.1相关概念以二维数组为例，设初始数据集5=｛x1A2,-An｝。定义1:数据对象%,-和占的欧式距离为DIJO的边界距离，便于区分处于交叉地带的点，有利于下一步精

细聚类，形成边界清晰的聚类结果。2.3优化后的Canopy算法描述Canopy算法的步骤如下。第一，计算各个数据样本间的

几=“叫-亏丿+(%-乜尸

其中，i,j=l,2,—,no(1

)欧式距离，以数组的形式进行存储。第二，计算该数组的最

大值b、最小值a,并对最大值、最小值向上、向下取整。第三，

绘制距离分布宜方图。在宜角坐标系中，X轴表示欧式距离，

以0.1为最小区间单位，将区间［a0,am］等分成若干等分小区

定义2:数据集S中所有样本元素的均值点为AverXoAverX

=

(

---------,二-------------(2)n

n定义3：类比频率分布直方图定义距离分布直方图。X,

+...

+

X,.

X.

+...

+

X,

,、间，Y轴表示满足某欧式距离范围的点的个数。第四，根据

距离分布直方图读取Tl、T2的取值，且Tl

>

T2O第五，

计算数据样本的均值点，初始聚类中心点选择距离均值点最

近的点。第六，计算聚类中心距离其他数据样本点之间的距

离D。第七，将。<

T2的数据样本划分到初始聚类中心所

设｛&1丿2,…/”｝是总体的样本，其最小值记为a,最大值记

为6又设a。是小于a的最大整数,a”是大于％的最小整数,

将区间［a。,a”］等分成

m

个小区间［a0,a1］,(ai,a2］,.-,(am.i,«m］,

在的Canopy中，并将该数据样本从样本数据集合中删除；

各小区间的长度均为AX

=鱼匚丑，然后统计出样本观测值

m将T2

<

D

<

T1的数据样本划分到初始聚类中心所在的

Canopy中，但在样本数据集合中不删除，继续下一次聚类划

62

2021年第6期China

Computer

&

Communication信£1与电IG分比较；将D

>

T1的数据样本作为新的聚类中心，生成自

己的Canopyo第八，重复步骤6和步骤7,直到待选的样本

数据集合为空，算法结束。End

S中元素为空算法3:

K-means算法Input：数据中心点集合卩=0炉2,…如，聚类中心个数上Output：

K-means聚类中心点集合U对每个Canopy数据集进行K-means聚类,直到函数收敛

3优化后的Canopy-k-means算法3.1优化后的Canopy-k-means算法流程优化后的Canopy-k-means算法流程如图1所示。整个算法中的优化部分在于在整个算法的初期增加了

绘制距离分布直方图，利用几何学的方式可以直观、方便、

快捷地获得算法改进中提及的Tl、T2的取值，并将获取的

Tl、T2的取值作为参数传入Canopy算法中。对初始聚类中

心的选取距离中心点最近的点作为初始聚类中心点，这样有

利于统筹考虑所有的点，对于边缘点较友好。在选取Tl、T2

时，利用波峰、波谷分别代表两两对象样本间的距离分布情

况，将第2个波峰的顶点作为切点做平行于X轴的切线，向

左相交于曲线的第1个点的横坐标的值为T2。取波谷到第2

个波峰之间柱状图上升最快的柱状图的最左边点的横坐标的

值为T1。取这两点为Tl、T2,通过多次实验验证发现，该

方法的聚类效果对于簇与簇之间边界点的处理效果较好。4实验分析4.1实验目的及实验设计因Canopy算法对初始中心和Tl、T2取值具有较强的依

赖性，再加上目前没有完美的取值方案，本文提出一种新的

取值方式，在聚类速度和聚类精度上有所提高。实验测试硬

图1优化后的Canopy-k-means算法流程图件环境选取

Intel(R)Core(TM)i5-8265U

CPU

2.8G,

512M

内

3.2优化后的Canopy-k-means算法伪代码算法1：生成距离分布直方图存，160G硬盘；软件环境选取Windows

10操作系统。本文

选取常用数据库中的GAUSS数据集和UCI数据集作为算法

的实验数据。其中，GUASS数据集的数据量为1000条，数

Input：数据样本集

S={xi>%2,…,x”}Output：绘制距离分布直方图，生成Tl、T2计算数据样本集合S中两两对象的欧式距离00,并存放

在数组中；据类型为浮点型。UCI数据集选择降到二维的Iris数据集作

为实验样本数据，含150条数据，数据类型为浮点型。通过

实验验证算法结论，评测标准包括算法收敛速度和F-Measure

计算数组中的最大值和最小值，分别为卩^昨、计算满足该欧式距离范围内数组元素的个数；指标。F-»ieas“Fe的计算公式为：厂

2

x

precision

x

recall

.、F

-

measure

=------------------

(

3

)precision

+

recall绘制距离分布直方图，Tl、T2取值。算法2：

Canopy算法其中，"ecisio"

=生表示精准率，recall

=吐表示

%

Input：数据样本集

S={xi>%2,…,x”}nmOutput：生成Canopy中心点集合P={p“P2,…!P”},聚类

中心个数k找回率，％"表示第丘个类簇与真实结果第”个类簇拥有相

同的数据对的个数，％表示第丘个类簇中数据对象的个数，

%表示第m个类别中数据对象的个数，F-measure的值越大，

计算数据样本集的中心点，生成中心点P1;While计算聚类中心点距离其他数据样本点之间的距离

为D；说明聚类效果越好。结合上述实验目的、实验数据和实验评

价标准，进行如下实验对比分析。本文中的算法改进前后对

比是基于Canopy-K-means算法对比改进前后的聚类结果。IfD小于T2放入聚类中心P1中并从数据样本S中删除该点;Else

ifD大于T2小于T1放入聚类中心P1;4.2算法改进前后的实验对比结果笔者将GUASS数据集中的1000条数据作为待聚类样本

数据，通过本文算法描述的方法生成GUASS数据集的距离

分布直方图，如图2所示。Else

ifD

大于

T1生成新的聚类中心并从数据样本S中删除该点；63

China

Computer

&

Communication直方图信1R与电IS2021年第6期根据降维后的Iris数据集，通过本文算法描述的方法生

成自定义数据集的距离分布直方图，如图5所示。直方图图2

GUASS数据集的距离分布直方图根据算法改进中描述的对Tl、T2的取值规则可知，

设定本数据集在Canopy算法中的初始阈值Tl=3.53,

T2=2.72,经过8次中心点更新后，生成的聚类效果图如图3

所示，图4为未进过改进的聚类方法，经过17次中心点更

根据算法改进中描述的对Tl、T2的取值规则可知，设定本数据集在Canopy算法中的初始阈值Tl=2.90,

T2=1.36,经

新后生成最终的结果。42过8次中心点更新后，生成的聚类效果图如图6、图7所示。★

*-4-2

0

2图3

gauss改进后的聚类结果图6

Iris数据集改进后的聚类结果1.5

-]----------------------------------------------------------------------------------------io-

if

★图7

Iris数据集未改进的聚类结果-4

-2

0

2

4-3-2-101234图4

gauss未改进的聚类结果64

2021年第6期China

Computer

&

Communication出，改进后的算法在聚类速度、聚类精度方面有了一定的提果的速度越快，且改进后的算法生成的簇更少，避免了过度信IB与电IE4.3实验结果分析

分析如表1所示。

基于Gauss、Iris数据集，算法改进前后的聚类效果对比

升。随着样本数据量的增加，改进后的算法生成最终聚类结

根据改进前后算法对上述两个数据集的聚类结果可以看聚类。«1算法改进前后的聚类效果对比分析数据集名数据样本量聚类中心更新次数生成聚类中心个数F-measure

指标改进前她前88改进后该进前改进后Gauss1367%97%95%100%Iris95结语本文提出借用距离分布宜方图求取Tl、T2的值，并结

合K-means算法实现对Canopy算法的改进。实验结果表明，

算法速度和聚类精确度都得到了提升，但是该方法在聚类时

[4]

王海燕.Canopy在划分聚类算法中对K选取的优化[J],吉

林大学学报,2020,58(3):634-63&[5]

邵欣欣.基于Canopy和共享最近邻的服务推荐算法[J].

计算机科学,2020,47(2):479-481.仍存在部分过度聚类的问题以及通过距离直方图对数值点选

取时偶有取值点较模糊的情况。同时该理论是建立在欧式距

[6]

胡小建，韦超豪.基于Canopy和k-means算法的订单分

批优化[J].合肥工业大学学报,2017,403:414-419.离的基础上，对于多维数据样本需要降维操作，且对于使用

空间向量更有明显特征性的数据样本不太友好，下一步有待

从这些方面进行改进。[7]

孟佳伟，孙红.基于Hadoop平台的K-Means算法优化综

述[J].软件导刊,2017,16(6):208-211.[8]

樊哲.Mahout算法解析和案例实战[M],北京：北京机械工

业出版社,2014:1-27.参考文献[1]

李琪等.基于密度峰值优化的Canopy-Kmeans并行算法[J].

通信技术,2018,51(2):312-317.[9]

XIA

D,NING

F,HE

ch

on

Parallel

Adaptive

Canopy-K-Means

Clustering

Algorithm

for

Big

Data

Mining

Based

on

Cloud

Platform[J].Journal

of

Grid

Computing,2020,18(2):263-273.[2]

王颖.Canopy的改进K-medoids算法[J].电脑与电信,2019(7):

30-33.[10]

LI

J,ZHANG

K,YANG

X,et

ry

Preferred

Canopy-

K-means

based

Collaborative

Filtering

algorithm

[J]

.Future

[3]

陈胜发.基于密度权重Canopy的改进K-medoids算法[J],

计算机工程与科学,2019,41(10):tion

Computer

Systems,2018(93):

1046-1054.65