朱俚治

(南京航空航天大学信息中心　南京　210016)



一种加权欧氏距离聚类算法的改进*

朱俚治

(南京航空航天大学信息中心南京210016)

摘要聚类算法是一种无监督学习的算法,能够将相似度强的数据聚类到一个族内,并且能够将属性相异的数据划分到不同的族里。当今聚类算法可分为传统的聚类算法和非传统的聚类算法。传统的聚算法有:基于划分聚类算法、基于层次聚类算法等算法。人们在使用划分法和层次法进行聚类时,是通过计算聚类对象之间属性的距离来实现聚类,因此欧氏距离公式和加权欧氏距离公式在这两种聚类算法中常用的算法。加权欧氏距离计算公式在聚类时着重聚类对象属性权重的选择,所以此文从聚类对象的相似度和对象属性对应的权重,这两个方面来考虑聚类成功的概率。论文作者提出的算法思想是,如果某个聚类对象具有若干的属性,那么首先计算该聚类对象属性的相似度,再根据该属性对应的权重是否为关键权重,如果是此属性对应的权重是关键权重,那么该对象聚类的成功率较高。

关键词加权欧氏距离; 相似度; 权重; 属性; 聚类

Improvement of Weighted Euclidean Distance Clustering Algorithm

ZHU Lizhi

(Information Center, Nanjing University of Aeronautics & Astronautics, Nanjing210016)

AbstractClustering algorithm is an unsupervised learning algorithm, which can cluster the data with strong similarity to a family, and can divide the data into different groups. Clustering algorithms can be classified into the traditional clustering algorithm and the non traditional clustering algorithm. The traditional clustering algorithms are based on clustering algorithm and hierarchical clustering algorithm. When clustering is used to cluster by dividing method and hierarchy process, the distance between the attributes of clustering objects is calculated. So the Euclidean distance formula and the weighted Euclidean distance formula are used in the two clustering algorithms. Weighted Euclidean distance formula in the clustering object class attribute weights of reunion, so this paper from the object cluster similarity and the properties of an object corresponding to the weights, the two aspects to consider clustering success probability. The algorithm proposed by this paper is that if a clustering object has a number of attributes, then it first calculates the similarity of the clustering object attributes, and then according to the weight of the attributes corresponding to the weight is the key, then the success rate of the object clustering is higher.

Key Wordsweighted Euclidean distance, similarity, weight, attribute, clustering

Class NumberTP391.41

1引言

随着信息技术的发展,人们积累的音、视频数据,以及文本、图片等数据越来越多,为了从这些大量的数据中提取对人们有用的信息数据,必须将不同类的数据进行分类和聚类,因此就出现聚类技术[7~9]。分类技术和聚类技术是截然不同的两种技术,分类必须根据已有的知识进行分类,而聚类是一种无监督学习技术。聚类分析是数据挖掘领域中的一个重要分支,是人们认识和探索事物之间内在联系的有效手段,它既可以用作独立的数据挖掘工具,来发现数据库中数据分布的一些深入信息,也可作为其它数据挖掘算法中的预处理步骤[7~9]。

当今聚类算法有基于划分的聚类算法、基于层次的聚类算法、基于密度的算法等聚类算法。尽管当今出现多种新技术的聚类算法,但传统的聚类算法仍然有着广泛的应用领域。传统的聚类算法中的划分法,是通过最大距离和最小距离来完成聚类的。为了改进某些聚类算法,有人提出了马氏距离聚类算法、欧氏距离聚类算法、加权欧氏距离聚类算法。加权欧氏距离聚类算法是欧氏距离聚类算法一种改进算法,其算法的创新之处是引入权重的概念。权重的引入有利于聚类时成功的概率。本文在加权欧氏距离聚类算法中,引入了当对象进行聚类之时,首先计算对象属性相似度的概率。如果聚类对象某些属性的相似程度为强的概率较大,那么这将为聚类是否成功提供重要参考依据。

2聚类的算法简介

1) 聚类分析的定义

聚类是将数据划分成群组的过程,研究如何在没有训练的条件下把对象划分为若干类。通过确定数据之间在预先制定的属性上的相似性来完成聚类任务,这样最相似的数据就聚集成族[7~9]。

2) 聚类算法

聚类算法主要有以下几种:划分方法、层次方法、基于密度的方法、基于网格的方法和基于模型方法[7~9]。划分方法的经典算法有:K—MEANS算法,K—MEDOIDS算法。层次方法的经典算法有:BIRCH算法、CURE算法、CHAMELEON算法等。基于密度的经典算法有:DBSCAN算法、OPTICS算法和DENCLUE算法。基于网格的经典算法有:STING算法和CLIQUE算法等。

3) 聚类算法的规则

在聚类算法中划分方法,层次方法和基于网格的聚类算法都是通过计算对象属性之间的距离来判断属性的相似性[7~9]。应用于聚类算法中的对象属性的距离计算的公式有:欧氏距离聚类公式、加权欧氏距离聚类公式、马氏距离聚类公式。因此距离计算公式在聚类算法中有相当重要的作用。

3加权欧氏距离简介

在传统的聚类算法中常用的聚类方法是通过对象的距离来完成聚类[2~3]。在很多的聚类算法中都采用欧氏距离公式作为聚类时的依据。在欧氏距离聚类方法中有两种欧氏距离公式:非加权欧氏距离和加权欧氏距离,本文将采用加权欧氏距离作为研究的对象。

1) 非加权欧氏距离计算公式[2]:

------------------------------2) 加权欧氏距离计算法公式[2]:

------------------------------其中,i=(Xi1,Xi2,…,Xip)和j=(Xj1,Xj2,…,Xjp)是两个p维的数据对象,Wp表示每个变量的权重值。在进行聚类时合理地运用加权欧氏距离,可以反映出各变量在数据中的不同作用,对改进聚类结果能起到较好的效果。

4加权欧氏距离公式中聚类对象属性的比较

需要聚类的对象A′有若干属性Xi1,Xi2,…,Xip,聚类对象A有若干属性Xj1,Xj2,…,Xjp。

1) 需要聚类对象A′的若干属性与聚类对象A的若干属性之间的比较:

如果对象A′某些属性十分接近对象A某些属性,那么有:Xi1-Xj1≈0,Xi2-Xj2≈0,…,Xip-Xjp≈0。

3) 根据以上的讨论和分析有以下的结论:

如果对象A′某些属性十分接近于对象A的某些属性时:

(1)它们属性的差值十分接近于0。

(2)它们属性的比值十分接近于1。

5聚类对象属性相似度的计算

5.1聚类对象的属性偏离概率估量

根据上一节的研究有以下的分析和讨论:

本文用A′表示是需要聚类对象的属性值,用A表示聚类对象的属性值。

如果A′与A属于恶意软件,当对象A′的属性与对象A的属性偏离程度达到了100%时,这时它们的属性完全没有相同之处。但是当对象A′的属性与对象A的属性相似程度达到了100%时,这时它们的属性完全相同,相似程度非常强。

如果A′与A属于非恶意软件,当对象A′的属性与对象A的属性偏离程度达到了100%时,这时它们的属性完全没有相同之处。但是当对象A′的属性与对象A的属性相似程度达到了100%时,这时它们的属性完全相同,相似程度非常强。

进行对象聚类的时候,只有同为恶意软件的对象或同为非恶意软件的对象之间才有相似之处,才能够进行聚类。恶意软件的对象与非恶意软件是截然不同属性的两种软件,它们之间的聚类是不可能的,不能聚成一个族。

以下对象之间的分析和讨论都是基于同属于恶意软件或同属于非恶意软件相似度概率的计算。

1) 在聚类过程之中,如果需对象A′的属性十分接近于已知对象A的属性时,那么A′/A的比值将十分逼近1值。当A′/A的比值十分逼近1时,函数f(x)=|1-A′/A|就十分接近于0的值,这时对象A′的属性偏离已知对象A的属性的值将趋向于0,因此当f(x)=|1-A′/A|的值越小,值的大小趋向于0时,这时对象A′的属性值非常接近于已知对象A的属性值,则A′的属性偏离A的概率就越小。

2) 在聚类过程之中,如果需对象A′的属性大于已知对象A的属性时,那么A′/A的比值将大于1。当A′/A的比值越大时,函数f(x)=|1-A′/A|的值大于0的程度将越明显。这时对象A′的属性值大于或远大于已知对象A的属性值时,则A′的属性偏离A的概率就越大。

3) 在聚类过程中,如果需对象A′的属性小于已知对象A的属性时,那么A′/A的比值将小于1。当A′/A的比值越小时,这时对象A′的属性值小于或远小于已知对象A的属性值时,则A′的属性偏离A的概率就越大。

5.2聚类对象属性相似度的估计

函数:g(x)=1-f(x)

说明:函数y=g(x)的含义是聚类对象相似程度的判断函数。以下分析和讨论是对函数g(x)=1-f(x)进行讨论:

1) 当y=f(x)的值越小,则有对象A′的属性偏离A的概率就越小。如果y=f(x)的值越小,那么g(x)=1-f(x)的值就越大,就表示对象A′的属性偏离A的概率就越小。这时对象A′的属性与A的相似的概率就越大,则聚类对象之间的相似度就越强。

2) 当y=f(x)的值越大,则有对象A′的属性偏离A的概率就越大。如果y=f(x)的值越大,那么g(x)=1-f(x)的值就越小,就表示对象A′的属性偏离A的概率就越大。这时对象A′的属性与A的相似的概率就越小,则聚类对象之间的相似度就越弱。

6聚类对象的属于与权重

1) 聚类对象的属性

(1)A′具有的属性为Xi1,Xi2,…,Xip。A具有的属性为Xj1,Xj2,…,Xjp。

(2)A′的属性Xi1与A的属性Xj1相对应,A′的属性Xi2与A的属性Xj2相对应,…,A′的属性Xip与A的属性Xjp相对应。

2) 聚类对象的属性与其权重

(1)A′的属性Xip与A的属性Xjp相对应

权重Wi1与Xi1-Xj1对应,权重Wi2与Xi2-Xj2对应,…,权重Wip与Xip-Xjp对应。

(2)如果Xip-Xjp十分接近于0,那么Xip与Xjp的比值十分接近于1,并且它们的相似概率值十分接近于1。如果此时与该属性对应的权重为关键权重,那么有以下的结论:那么在进行对象聚类时该属性为重要属性,能够作为聚类是否成功的关键性参考条件。

7结语

在进行聚类对象的属性可能是n维的,因此在进行聚类时对象之间必须进行属性值的匹配和计算。在属性的计算过程中,属性之间的相似程度是不同的,有些属性相似程度强些,而有些属性相似程度弱些。加权欧氏距离的聚类公式能够计算多个属性的相似度,再根据该属性对应的权重是否为关键权重来为这次聚类是否成功提供重要依据。如果对象的某些属性相似的概率较大,并且与该属性对应的权重为重要的权重,那么这些因素同样是聚类时是否成功的重要参考条件。

参 考 文 献

[1] 孟海东,张玉英,宋飞燕.一种基于加权欧氏距离聚类方法的研究[J].计算机应用,2006,26(12):152-153.

MENG Haidong, ZHANG Yuying, SONG Feiyan. Research based on euclid distance with weights of clustering method[J]. Journal of Computer Application,2006,26(12):152-153.

[2] 董旭,魏振军.一种加权欧氏距离聚类方法[J],信息工程大学学报,2005,6(1):23-25.

DONG Xu, WEI Zhenjun. A Clustering Method of Euclid Distance with Weights[J]. Journal of Information Engineering,2005,6(1):23-25.

[3] 吴香华,牛生杰,吴诚,等.马氏距离聚类分析中协方差矩阵估算的改进[J].数理统计与管理,2011,30(2):240-245.

WU Xianghua, NIU Shengjie, WU Cheng, et al. An Improvement on Estimating Covariance Matrix during Cluster Analysis Using Mahalanobis Distance[J]. Application of Statistics and Managerment,2011,30(2):240-245.

[4] 邵峰晶,于忠清,王金龙,等.数据挖掘原理与算法[M].北京:科学出版社,2009.

SHAO Fengjing, YU Zhongqing, WANG Jinlong, et al. Principle and Algorithm of Data Mining[M]. Science Press,2009.

[5] 罗森林,马骏,潘丽敏.数据挖掘理论与技术[M].北京:电子工业出版社,2013.

LUO Senglin, MA Jun, PAN Limin. Theory And Technology of Data Mining[M]. Beijing: Electronics Industry Press,2013.

[6] 吴帆,李石君.一种高效的层次聚类分析算法[J].计算机工程,2004,30(9):70-71.

WU Fan, LI Shijun. An Efficient Hierarchical Clustering Algorithm[J]. Computer Engineering,2004,30(9):70-71.

[7] 向培素.聚类算法综述[J].西南名族大学学报·自然科学版,2011,37(专辑):112-114.

XIANG Peisu. Survey of Clustering Algorithm[J]. Journal of Southwest University for Nationalities·Natural Science,2011,37(special):112-114.

[8] 方媛,车启凤.数据挖掘之聚类算法综述[J].河西学院学报,2012,28(5):72-76.

FANG Yuan, CHE Qifeng. Summary of Data Mining Clustering Algorithm[J]. Journal of Hexi University,2012,28(5):72-76.

[9] 贺玲,吴玲达,蔡益朝.数据挖掘中的聚类算法综述[J].计算机应用,2007:10-13.

HE Ling, WU Lingda, CAI Yichao. Survey of Clustering Algorithms in Data Mining[J]. Application Research of Computers,2007:10-13.

[10] 刘瑞元.加权欧氏距离及其应用[J].数理统计与管理,2002,21(5):17-19.

LIU Ruiyuan. Euclid distance with weight and its applications[J]. Application of Statistics and Managerment,2002,21(5):17-19.

[11] 宋宇辰,张玉英,孟海东.一种基于加权欧氏距离聚类方法的研究[J].计算机工程与应用,2007,43(4):179-180.

SONG Yuchen, ZHANG Yuying, MENG Haidong. Research based on euclid distance with weights of clustering method[J]. Computer Engineering and Applications,2007,43(4):179-180.

[12] 陈治平.基于复杂对象分解的相似性计算方法[J].计算机工程与应用,2008,44(34):149-162.

CHEN Zhiping. Similarity measurement based on decomposition of complex object[J]. Computer Engineering and Applications,2008,44(34):149-162.

中图分类号TP391.41

DOI:10.3969/j.issn.1672-9722.2016.03.009

作者简介:朱俚治,男,工程师,研究方向:计算机技术、信息安全。

收稿日期:2015年9月3日,修回日期:2015年10月19日