基于密度的数据流聚类方法研究.doc

分类号：密级：编号：工学博士学位论文基于密度的数据流聚类方法研究博士研究生：高兵指导教师：张健沛教授学科、专业：计算机应用技术哈尔滨工程大学2014年 06月 分类号：密级：编号：工学博士学位论文基于密度的数据流聚类方法研究博士研究生：高兵指导教师：张健沛教授学位级别：工学博士学科、专业：计算机应用技术所在单位：计算机科学与技术学院论文提交日期：2014年 3月论文答辩日期：2014年 6月学位授予单位：哈尔滨工程大学 Classified Index:U.D.C:A Dissertation for the Degree of D.EngResearch of Data Stream Clustering Methods Based on Density Candidate: Gao BingSupervisor: Prof. Zhang JianPeiAcademic Degree Applied for: Doctor of EngineeringSpecialty: Computer Applied TechnologyDate of Submission: March. 2014Date of Oral Examination: June. 2014University: HarbinEngineeringUniversity 哈尔滨工程大学学位论文原创性声明本人郑重声明：本论文的所有工作，是在导师的指导下，由作者本人独立完成的。有关观点、方法、数据和文献的引用已在文中指出，并与参考文献相对应。除文中已注明引用的内容外，本论文不包含任何其他个人或集体已经公开发表的作品成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。作者（签字）：日期：年月日哈尔滨工程大学学位论文授权使用声明本人完全了解学校保护知识产权的有关规定，即研究生在校攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨工程大学有权保留并向国家有关部门或机构送交论文的复印件。本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本学位论文，可以公布论文的全部内容。同时本人保证毕业后结合学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈尔滨工程大学。涉密学位论文待解密后适用本声明。本论文（在授予学位后即可在授予学位 12个月后解密后）由哈尔滨工程大学送交有关部门进行保存、汇编等。作者（签字）：日期：导师（签字）：年月日年月日 基于密度的数据流聚类方法研究摘要近年来，随着信息技术的飞速发展和广泛应用，数据流作为一种普遍存在的数据形式，吸引了越来越多数据挖掘研究者的关注。与存储于可多次随机访问介质中的静态数据不同，数据流具有连续性、实时性、次序性等特征，使传统的聚类分析技术不适用于数据流环境。学术界已经对数据流上的聚类分析问题进行了不少研究工作，开发出很多快速有效地针对数据流的聚类算法，给人们提供了有价值的信息帮助决策。由于数据流本身的复杂性和多样性，现有算法仍然有待于进一步提高以适应新的条件和要求，在诸如提高聚类结果的精度，发现不同密度的聚簇和离群点，在分布式数据流和不确定数据流中发现不同形状的聚簇等方面仍然有很多迫切需要解决的问题等待进一步研究。本文针对数据流分析中的聚类分析任务，利用基于密度的聚类技术，从以下四个方面进行了更加细致有效的研究：首先，针对不确定数据流聚类算法大多应用基于距离划分的聚类思想，难于发现不确定数据流中的非球状簇，而现有的基于密度的不确定数据流聚类算法不能解决属性级不确定性聚类问题。提出衡量网格不确定性的期望距离标准，通过分析属性级不确定性对聚类问题的影响定义网格概率密度，使网格密度能够兼顾网格中数据量与不确定性双重因素；同时，定义了新的密度阈值标准和网格衰减标准，并据此分类网格及设计聚类算法，保证了及时捕捉到簇的变化；在此基础上，结合衰减窗口技术，提出一种基于网格密度的不确定数据流聚类算法(DBUSC)，查找密度大于动态密度阈值的相邻网格单元得到最终聚类结果；最后，通过实验表明：与传统的基于距离划分方法相比， DBUSC算法具有能够发现非球形状聚簇和无需指定簇数的优点，在聚类不确定数据流时不仅所产生的时间代价更小，而且能够取得更好的聚类质量。其次，针对基于微聚类的数据流聚类方法中的微聚类结构不保留数据流自身信息，影响了聚类准确度，同时采用的两阶段聚类的思想降低了算法效率问题。提出用代表点结构作为数据流的概要结构，用以保存数据流的密度信息，在代表点的基础上定义环点，设计迭代算法通过查找环点得到密度相连的代表点形成簇；另外，定义了代表点时态权重，提出一种基于代表点性质的数据流聚类算法(RB-Stream)，采用测试-更新策略及时发现低于权重阈值的代表点，和权重不断增加的新的代表点，能够在最大程度上发现数据流中旧簇消亡和新簇出现的同时，进一步提高 RB-Stream算法的运行效率；最后，通过分析和实验表明：RB-Stream算法相对于二次聚类微簇得到聚类结果的算法，具有更好 哈尔滨工程大学博士学位论文的聚类准确性，节省了聚类所需的运行时间。再次，针对现有的数据流聚类多数只能适用于密度一致的流数据，不能发现数据流中密度不同的簇，并且数据流中数据不断流入，使发现密度不同且动态改变的簇和离群点尤为困难的问题。在共享最近邻图的基础上，定义了共享最近邻密度，结合数据对象被类似的最近邻对象包围的程度和被其周围对象需要的程度这两个环境因素，使聚类结果不受密度变化的影响；另外，定义了数据对象的平均距离和簇密度，以识别离群点和簇间的桥接；在此基础上，结合滑动窗口技术，维护共享最近邻图实现簇的不断更新，提出了一种基于共享最近邻密度的演化数据流聚类算法(SNDStream)，查找密度大于指定阈值的连通分支得到聚类结果；最后，通过分析和实验表明：SNDStream算法能够发现任意形状和不同密度的簇，正确识别离群点和聚簇之间的连接，具有良好的聚类质量，能够在不指定簇数的条件下有效适应聚簇不断变化的数据流场景。最后，在分布式数据流环境中发现任意形状的簇具有非常重要的意义，针对现有的分布式数据流聚类算法采用基于距离划分的或者基于模型的聚类思想，难于很好的处理数据流中的非球状簇问题。提出了一种分布式数据流聚类算法(RB-DDSC)，算法包含两个阶段，首先在代表点结构的基础上，在远程站点生成局部聚簇模型传送到协调站点，然后在协调站点通过合并局部模型算法产生全局聚簇；进而，设计了测试-更新局部模型和全局模型算法避免了在数据流相对稳定的情况下频繁发送数据；最后，通过分析和实验表明：RB-DDSC算法采用代表点结构及相应更新机制，能够发现分布式数据流中不同形状的聚簇并显著降低数据传输量。关键词：数据挖掘；数据流；聚类分析；密度；代表点； 基于密度的数据流聚类方法研究AbstractIn recent years, with the development of information technology, data stream as acommon data form has attracted more and more attention of the data mining researchers.Incontrast to static data, which stored in media of random query, data stream has the token ofcontinuous、intime and sequence which does notmake the traditional methods available.Theresearchers have done a lot of work on the clustering problem of data stream, and proposedmany quickly clustering algorithms to provide people the growing valuable information tomake decision. However, because of the complexity and diversity of data steam, thesealgorithms need to be improved to meet the new conditions and demands. There are manyproblems need to be researched and resolved, such as the improving the accuracy of clustering,finding the different density clusters and outliers, finding the different shape clusters on thedistribute data stream or the uncertain data stream. In this paper, we study the problem ofclustering data streams This paper aims the clustering analysis mission on the data stream,using density-based clustering technology, makes deep and detailed study on the four belowaspects:Firstly, the algorithms on clustering uncertain data stream are mostly based on theideology of partition, which are difficulty to find arbitrarily shape of clusters. In addition, theexisting density-based algorithms arent able to solve the problem on the attribute-leveluncertain. We propose the expectation distance criterion to measure the uncertain of the grids,which analyzes the clustering impact of attribute-level uncertain and considers the two factors:the number of points in grid and the uncertainty of grid; at the same time, we define the newdensity threshold and the grid fading standard, then classify the grads and design the clusteringalgorithm to catch the change of clusters. Combined the fading window technology, wepropose a grid density-based uncertain data stream algorithm(DBUSC), which finds theneighbor grids whose density is beyond the dynamic density threshold to get the clusters result.At last, experiments show: compared with conventional distance-based methods, the uncertaindata stream algorithm DBUSC has the merits of finding non-spherical clusters and does notneed the number of clusters, can get the better cluster quality while need the less time.Secondly, the micro-clusters accepted in micro-cluster-based stream algorithms dontkeep the information of data stream, affect the cluster accuracy, and reduce the efficiency ofalgorithm by using two-phase method. We propose the representative point structure as 哈尔滨工程大学博士学位论文synopsis to save the density information of data stream, define the circle point to get theclusters by searching iteratively them to find the connected representative point. In addition,by defining temporal weight of representative point, we propose the representative-based datastream algorithm (RB-Stream), use the test-update strategy to find the representative pointwhose weight is under the threshold or increasing. The algorithm improves the efficiencywhile finds the new clusters and the cluster disappear. At last, experiments show: comparedwith micro-clusters algorithms, the algorithm RB-Stream can get the better cluster accuracy,need the less time.Thirdly, the exiting density-based clustering stream algorithms mostly apply to the streamwith the constant density, and cant find the clusters with the different density. Furthermore,with the data flowing in, it is difficult to discover the changeable clusters and outliers. On thebase of the shared nearest neighbor graph, we define the SNN density, consider the degree thatdata object is surrounded by nearest neighbors and the degree that data object is demanded byaround data objects. The clustering result is from the influence of the density variation. Inaddition, we define the average distance of data object and the cluster density to identifyoutliers and clusters with bridge. Then we maintain the renewal of clusters on shared nearestneighbor graph over the sliding window, propose the SNN density-based data streamalgorithm (SNDStream). The algorithm searches the connected components in SNN graph toget the result. At last, experiments show: the algorithm SNDStream can get arbitrary shapeclusters with different density, can correctly find outliers and the chain between clusters. Thealgorithm has the better cluster quality, is suitable to the changeable clusters withoutspecifying the number of clusters.Finally, it is important to find the clusters of arbitrary shapes under the distributed datastreams environment, but the existing distributed stream clustering algorithms which based onthe distance or model cant deal well with the non-spherical clusters. We propose the distributedata stream clustering algorithm (RB-DDSC). The algorithm has two phases: first, on the baseof the representative point, the local model generated at the remote site is sent to thecoordinator site, then generate global clusters by combining the local models at coordinatorsite. Furthermore, we design test-update local model algorithm avoid frequently sending datawhen the data stream is stable and reduce the data transmission. At last, experiments show: thealgorithm RB-DDSC can get arbitrary shape clusters in distributed data streams and reduce thedata transmission by using the representative point and updating strategy.Keywords: Data mining; Data stream; Clustering analyse; Density; Representative point; 基于密度的数据流聚类方法研究目录第 1章绪论 11.1研究背景、目的和意义 11.2国内外的研究现状 31.2.1数据流聚类 31.2.2基于密度的微聚类数据流算法 91.2.3基于网格密度的数据流算法 131.3论文的研究内容171.4论文的组织结构18第 2章不确定数据流聚类方法研究202.1问题提出202.2相关研究基础212.2.1不确定数据聚类 212.2.2不确定数据流聚类 222.2.3数据空间划分方法 232.3基本概念252.3.1不确定数据流的表示 252.3.2单元格的平均期望距离及网格概率密度 262.3.3网格密度阈值与格簇 272.4基于网格密度的不确定数据流聚类算法 DBUSC282.4.1聚类与更新 292.4.2性能分析 312.5实验及结果分析312.5.1实验数据及参数设定 312.5.2聚类质量分析 322.5.3聚类处理时间分析 342.5.4参数影响分析 35 哈尔滨工程大学博士学位论文2.6本章小结36第 3章基于代表点的数据流聚类方法研究383.1问题提出383.2相关研究基础393.2.1基于密度聚类的基本原理 393.2.2扩展的基于密度的聚类方法 413.3基本概念423.3.1代表点模型 423.3.2时态权重 453.3.3簇结构 463.4基于代表点的数据流聚类算法 RB-Stream 473.5实验结果分析503.5.1实验数据及参数设定 503.5.2聚类质量分析 523.5.3聚类处理时间分析 553.5.4参数影响分析 563.6本章小结57第 4章基于共享最近邻密度的数据流聚类方法研究584.1问题提出584.2相关研究基础594.2.1不同密度簇的聚类方法 594.2.2滑动窗口技术 614.3基本概念624.3.1 k最近邻图与共享最近邻相似度 624.3.2共享最近邻图与 SNN密度634.3.3离群点与簇的桥接 644.4基于共享最近邻的演化数据流聚类算法 SNDStream 654.4.1算法基本思想与结构 654.4.2聚簇维护 66 基于密度的数据流聚类方法研究4.5实验及结果分析694.5.1实验数据 694.5.2聚类质量 704.5.3聚类有效性 724.5.4参数影响分析 744.6本章小结77第 5章分布式数据流聚类方法研究785.1问题提出785.2相关研究基础795.2.1分布式数据处理方式 795.2.2分布式数据流挖掘 805.2.3分布式数据流聚类 815.3基本概念825.3.1分布式数据流模型 825.3.2概要结构与局部模型 835.4基于代表点的分布式数据流聚类算法 RB-DDSC835.4.1算法基本思想 835.4.2远程站点处理 845.4.3协调站点处理 865.5实验及结果分析885.5.1聚类质量分析 895.5.2算法运行效率分析 905.5.3算法通信量分析 915.5.4参数影响分析 925.6本章小结93结论94参考文献96攻读博士学位期间发表的论文和取得的科研成果 107致谢 108 哈尔滨工程大学博士学位论文个人简历 109 第 1 章绪论第 1 章绪论1.1研究背景、目的和意义随着软件和硬件技术的快速发展，特别是互联网、物联网的出现，人们可以从多个领域采集数据，数据采集的能力不断提高，数据采集的方法也日益自动化和智能化。特别是在许多新出现的应用领域，不断快速产生需要处理的数据，例如网络访问记录、环境保护监测、网络安全监控、股票交易信息、事务日志、电子商务信息、卫星遥感数据等。这些应用的共同特点是，高速而实时地产生大量数据，这些数据不再固定地、永久地保存在磁盘等介质上，而是动态地、连续地不断出现，同时数据量是潜在无限的，因此大多数应用需要满足在线获取和处理数据的要求，快速地返回响应。这种由一系列连续且有序的，像水的流动一样组成的数据序列被称为数据流1-3。聚类分析是一种无监督学习方法，是重要的数据挖掘技术之一，一方面可以作为获取数据分布状态的技术单独使用，另一方面可以作为一个预处理步骤用于数据分类。聚类分析的目的是从研究的数据中发现有价值的规则，是在一个给定的数据对象集合中，利用选定的相似度标准，将数据集合中的对象分配到不同的类（簇）的过程，使得同一个类中的对象彼此之间的相似程度尽可能高，而不同类中的对象之间的相似程度尽可能低4。簇内的相似性越大，簇间的差别越大，得到的聚类效果就越好。聚类分析是一种重要的和基础的数据分析方法，广泛应用于人工智能、市场调研、目标识别、空间数据分析等领域5-8。数据流这种新的数据形态的出现，为聚类分析提供了更加广阔的空间，数据流聚类相对于在数据库中发现模式的传统聚类，不同之处是处理数据流中的数据对象。由于流数据的广泛存在，数据流聚类研究具有广阔的应用背景、重要的现实意义。例如，聚类传感器网络产生的数据流9,10，能够检测地理环境的改变，监控城市交通的实时情况以实现挖掘有价值信息的任务，如挖掘得到的交通拥堵模式往往对应着流量监测数据中显示的一个新的群集。聚类连锁零售企业产生的联机事务数据流，能够对消费者的行为进行分析，及时发现新的消费模式，或者发生于购物行为中的欺诈事件。聚类互联网中不断产生的网络访问数据流11-13，能够及时发现网络中的异常事件，如检测网络入侵行为及发现入侵行为所具有的共同特征，这些特征往往能够通过分析来自于相同源地址的快速形成地数据包簇得到。1 哈尔滨工程大学博士学位论文由于数据流数据规模巨大、数据实时到达、更新频繁，要求仅通过一遍扫描得到反馈结果，这使得传统的集中全部数据、执行多遍扫描操作的数据聚类技术不再可行。人们研究并设计出了若干面向数据流的聚类分析算法13，包括改进传统聚类算法以满足数据流增量聚类的要求，采用基于微聚类的两阶段聚类算法发现指定数目的簇，采用基于网格密度的算法发现任意形状的簇等等。但是，随着互联网、物联网、传感器等技术的发展，人们能够获取到越来越丰富的数据流，由于数据流本身的复杂性和多样性，现有算法仍然有待于进一步提高以适应新的条件和要求。在诸如提高聚类结果的精度，发现不同密度的聚簇和离群点，在分布式数据流和不确定数据流中发现不同形状的聚簇等方面仍然有很多迫切需要解决的问题等待进一步研究。基于密度的聚类技术一直是数据挖掘中聚类分析的一个重点问题，由于基于密度的聚类技术的内在优点，将其应用于数据流聚类有显著的优势14。首先，有利于发现具有不同形状的聚簇。对于许多应用，在数据流中发现不同形状的聚簇有重要的用途，例如，分析环境观测中产生的数据，发现相同环境条件的区域呈现出各种不同的形状。其次，无需预先假定聚簇的个数。很多聚类方法要求事先指定聚簇个数作为