一种实现混合属性数据流聚类的算法

摘 要：在当今的网络中存在三种形式的数据流，连续型数据流，标称型数据流和混合属性数据流。由于目前在数据挖掘中大部分算法只能处理一种属性的数据流，而处理混合属性数据流的算法却很少，但在数据挖掘的实际应用中常常需要将不同属性的数据流进行相互区分。事实上研究人员在区分不同属性数据流时，首先是将不同属性的流进行聚类，其次是对不同属性的流进行识别。在查阅有了有关资料和参考文献后，本文提出了一种对混合属性数据流的聚类算法，该算法的聚类思想是：①提取混合属性数据流的分类属性，②使用k-近邻算法计算数据流分类属性的相似性，③根据k-近邻算法对数据流相似度的计算结果，使用k-均值聚类算法对混合属性数据流进行聚类，④给出聚类的算法。

关键词：混合属性数据；相似性；k-近邻算法；k-均值聚类；分类属性

中图分类号：TP372 文献标识码：A

1 引 言

当今的计算机技术和网络技术发展的速度是快速的，在这些技术快速发展的同时，产生了大量的各种属性的数据，这些数据是连续的、无界的、不定速度的流式数据，IT人员将这些数据称为数据流[2]。在网络中每天都有惊人的流量吞吐量，在这些海量的数据中可将这些数据流的属性分为三种型式，连续属性数据流、标称属性数据流和混合属性数据流。从数据流的属性角度上来看，连续属性数据流和标称属性数据流是传统意义上的数据流，而混合属性数据流是IT技术发展之际产生的新属性的数据流。网络管理人员为了从这大量的数据流中获取重要的信息，必须对这三种属性的数据流进行有效准确的识别。为了对未知属性数据流进行识别，第一步是将这些数据流进行聚类。尽管目前有多种数据流的聚类算法，但这些大部分算法都是用于传统意义上的数据流，而对混合属性数据流的聚类算法相对较少。为了检测网络流量中的混合属性数据流，在聚类算法这方面研究主要有以下几种算法：有Guha等人提出的STREAM聚类算法、Aggarwal提出的clustrem的改算法和Ong等人根据clustrem提出的利用标称属性作为聚类条件的SCLOPE等算法[2]。本文的作者在查阅了一些有关文献和一些聚类算法之后提出了一种实现混合属性数据流的聚类算法，在本文中仍然以混合属性数据流的分类属性作为聚类的前提条件。以下是本文聚类算法中使用的算法的简介。

决策树，k近邻算法和贝叶斯等算法是当前研究的较多和主流的数据分类应用算法。k近邻算法对实例进行分类时必须根据已知实例，该算法在识别数据的属性时，必须提取待分类实例的各种属性，再将该实例的各种属性分别与已知实例的各种进行逐一比较[6]。在最终的比较结果中如果有k个实例与待分类的实例属性相同，那么就将这个待分类的实例与k个实例分为一类[6]。

目前，常用的聚类算法有基于划分的聚类算法，基于层次的聚类算法和基于密度的算法。基于基于划分的聚类的算法就是将聚类的对象划分k个分组，每个分组代表一个聚类，在每个聚类分组中通过距离公式计算聚类对象的相似性来完成聚类。k-均值聚类算法是一常见的基于划分的聚类算法，通过有限次数的迭代来完成对象之间的聚类，该算法的特点是实现起来较为简单，同时适合大规模数据的聚类，该算法的实用性较强，因此k-均值在各个科学领域都有广泛的应用，大多数的聚类过程中都采用该算法为聚类的算法[4-5]。

2 混合属性数据流概念的简介和及其应用

2.1 混合属性数据流的基本概念

1.当今网络中的数据流可以分为三种属性数据流：①连续型数据流，②标称型数据流，③混合型数据流。连续型数据流是指数据的取值是连续性的，标出型数据流是指数据的取值为有限的状态，混合属性数据流是指数据同时具有连续属性和标称属性的数据流[1-3]。

2.混合属性数据流集合表示为 ，集合x分类属性， ，其中：数值属性的 ，分类属性为 [1-3]。

1）混合属性数据流的数值属性的含义是：该属性的数据取值是连续型[1-3]。

2）混合属性数据流的分类属性的含义是：该属性的数据取值是有限的状态[1-3]。

计算技术与自动化2016年6月

第35卷第2期朱俚治等：一种实现混合属性数据流聚类的算法

由于目前一些面向混合属性数据流的聚类算法将分类属性作为混合属性数据流聚类的条件，因此在本文中仍然以混合属性数据流的分类属性作为聚类的前提条件。

2.2 混合属性数据流概念的应用

3 k近邻算法

基于实例的学习方法中的最基本的是k-邻近算法。这个算法假定所有的实例对应于n维空间中的点。一个实例的最近邻是根据标准欧氏距离定义的。更精确地讲把任意的实例x表示为下面的特征向量[6-8]。

4 k近邻算法的应用

4.1 数据流Ai与数据流Bi的属性

某个已知的数据流Ai具有的数值属性的{ai1，ai2，…，aid}，分类属性为{ai（d+1），ai（d+2），…，aim}。

某个未知的数据流Bi具有的数值属性的{bi1，bi2，…bid}，分类属性为{bi（d+1），bi（d+2），…，bim}。

以下使用k-近邻算法计算混合属性数据流Ai与Bi中的分类属性的相似度。

4.2 k近邻算法距离公式的应用

1.实例A与实例B的属性距离

1）aim表示实例A进行分类时的能够起到分类作用的属性，B表示储存器中一个的实例。实例B具有的分类作用的属性bim。

2）d1表示ai（d+1）与bi（d+1）之间的距离，d2表示ai（d+2）与bi（d+2）之间的距离，……dn表示aim与bim之间的距离。

3）如果当ai（d+1）-bi（d+1）≈0，ai（d+2）-bi（d+2）≈0…aim-bim≈0时，则有ai（d+1）bi（d+1）≈1，ai（d+2）bi（d+2）≈1…aimbim≈1

2.实例A与实例B属性距离计算公式

1）实例A与实例B属性的偏离估量函数

函数：f（x）=1-实例A的分类属性值实例B的分类属性值

2）实例A与实例B属性相似程度的估计函数

函数： g（x）=1-f（x）

3.在实例A的属性与实例B的属性相似性的计算

1）在实例A的属性与实例B的属性比较过程中，如果对象aim的属性十分接近于已知对象bim的属性时，那么aimbim的比值将十分逼近1值。当aimbim的比值十分逼近1时，这时f（x）=1-aimbim，并且k-近邻算法中的距离dn就十分接近于0的值。当实例aim的属性偏离已知实例的bim属性大小将趋向于0之时，则有dn的值越小，并且该值趋向于0时，这是则A的属性偏离的B属性概率就越小。

2）当y=f（x）的值越小，则对象A的属性偏离B的概率就越小。当y=f（x）的值越小时，那么g（x）=1-f（x）的值就越大，这是表示对象A的属性偏离B的概率就越小。如果对象A的属性偏离B的概率越小，则对象A与B之间的相似度就越强。

4.在实例A的属性与实例B的属性偏离性的计算

1）在实例A的属性与实例B的属性比较过程中，如果A对象的属性大于已知对象B的属性时，那么aimbim的比值将大于1时。当aimbim的比值越大时，函数f（x）=1-aimbim的值大于0的程度将越明显，并且k-近邻算法中的距离dn偏离0的程度就越大，则A的属性与B的属性偏离程度就越大。

当y=f（x）的值越大时，那么g（x）=1-f（x）的值就小，这是表示对象A的属性偏离B的概率就越大，则对象A与B之间的相似度就越差。

2）在实例A的属性与实例B的属性比较过程中，如果需对象的A属性小于已知对象B的属性时，那么aimbim的比值将小于1时。当aimbim的比值越小时，函数f（x）=1-aimbim的值小于1的程度将越明显，并且k-近邻算法中的距离dn偏离0的程度就越大，则A的属性与B的属性偏离程度就越大。

当y=f（x）的值越小时，那么g（x）=1-f（x）的值就大，这是表示对象A的属性偏离B的概率就越大，则对象A与B之间的相似度就越差。

5.实例A与实例B属性的比较结论

1）实例A属性为{ai（d+1），ai（d+2），…，aim}，实例B分类属性为{bi（d+1），bi（d+2），…，bim}。

2）d1表示ai（d+1）与bi（d+1）之间的距离，d2表示ai（d+2）与bi（d+2）之间的距离，……dn表示aim与bim之间的距离。

3）如果d1≈0，d2≈0，…dn≈0，则实例A与实例B的属性是较为相似。

4）如果实例A与实例B的属性是较为相似，则使用k均值聚类算法对实例A与实例B进行聚类了。

5 k均值聚类算法的应用

5.1 k均值算法基本概念简介

1.k均值算法的聚类思想

k均值聚类算法在寻找对象之间相似性的度量通常是欧几里德距离的倒数，也就是说两者的距离越小表示两者的相似就越大，反之则相似性就越小[4-5]。的思想是：该算法的思想是：把所有需要聚类的数据分成若干个类，如果在每个类中数据属性相似程度较高，那么将每个类中所有属性值求平均值，每个类的平均值成为这个类的聚类中心。之后根据每个类的平均值的相似程度开始聚类。该算法的聚类过程是：根据相似程度不同的若干个类，将其中相似程度最高的两个类聚为一个类，当每次聚类完成后再次计算该类的平均值，即新的类的中心值，然后再根据新的中心值，再次进行聚类。如此重复，直到类的平均值不再变化为止。

6 聚类算法

1.需要聚类的混合属性数据的流。

2.k近邻算法计算混合属性数据流的相似程度。

3.根据混合属性数据流的相似程度使用k均值算法对相似的流进行聚类。

7 结束语

混合属性数据流技术是由网络技术的发展而产生的新属性数据，该属性的数据流与连续属性的数据流和标称属性的数据流形成当今网络中主要的三种数据流。对于网络管理人员来说要保证网络的安全性和维护网络的正常运行，对流量的监测是必须的。如果要对网络流量进行监控，必须对数据流进行识别。对网络中的流进行的识别之时，必须进行相同属性流的聚类，因此流的聚类对识别流来说是相当重要的。基于上述原因本文提出了一种对混合属性数据流进行聚类的算法，该算法具有一定的合理性和和科学性，因此该算方法具有一定的应用价值和一定的应用领域。

参考文献

[1] 黄德才，沈仙桥，陆亿红.混合属性数据流的二重k近邻聚类算法[J].计算机科学，2013， 40（10）：226-230.

[2] 杨春宇，周杰.一种混合属性数据流聚类算法[J].计算机学报，200730（8）：13564-1371.

[3] 廖志芳，罗浩，樊晓平，等.一种面向混合属性数据聚类的新算法[J].控制与决策，2009， 24（5）：697-700.

[4] 谢娟英，蒋帅，王春霞，等.一种改进的全局k均值聚类算法[J].陕西师范大学学报：自然科学版.2010， 38（2）：18-22.

[5] 胡伟.改进的层次k均值聚类算法[J].计算机工程与应用，2013， 49（2）：157-159.

[6] TomM.Mitchell著.机器学习[M].北京：机械工业出版社，2013.

[7] 林关成.基于改进K近邻算法支持向量分类研究[J].渭南师范学院学报，2012，（2）：83-86.

[8] 陆微微，刘晶.一种提高K-近邻算法效率的新算法[J].计算机工程与应用，2008，（4）：163-178.

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