足球比分直播

基于概率密度网格结构的不确定数据流聚类算法分析.pdf

返回
基于概率密度网格结构的不确定数据流聚类算法分析.pdf_第1页
第1页 / 共61页
基于概率密度网格结构的不确定数据流聚类算法分析.pdf_第2页
第2页 / 共61页
基于概率密度网格结构的不确定数据流聚类算法分析.pdf_第3页
第3页 / 共61页
基于概率密度网格结构的不确定数据流聚类算法分析.pdf_第4页
第4页 / 共61页
基于概率密度网格结构的不确定数据流聚类算法分析.pdf_第5页
第5页 / 共61页
点击查看更多>>
资源描述:
A Dissertation in Computer Application Technology RESEARCH OF PROBABILITY DENSITY GRID-BASED CLUSTERING FOR UNCERTAIN DATA STREAMS by Chen Lijuan Supervisor Professor He Haitao Yanshan University 2011.12 万方数据燕山大学 硕 士学位论文原创性声明 本人郑重声明此处所提交的 硕 士学位论文 基于概率密度网格结构的不确定数据流聚类算法研究 ,是本人在导师指导下,在燕 山大学攻读 硕 士学位期间独立进行研究工作所取得的成果。 论文中除已注明部分外不包含他人已发表或撰写过的研究成果。对本文的研究工作做出重要贡献的个人和集体,均已在文中以明确方式注明。本声明的法律结果将完全由本人承担。 作者签字 日期 年 月 日 燕山大学 硕 士学位论文使用授权书 基于概率密度网格结构的不确定数据流聚类算法研究 系本人在燕山大学攻读 硕 士学位期间在导师指导下完成的 硕 士学位论文。本论文的研究成果归燕山大学所有,本论文的研究内容不得以其它单位的名义发表。本人完全了解燕山大学关于保存、使用学位论文的规定,同意学校保留并向有关部门送交论文的复印件和电子版本,允许论文被查阅和借阅。本人授权燕山大学,可以采用影印、缩印或其它复制手段保存论文,可以公布论文的全部或部分内容。 保密□,在 年解密后适用本授权书。 本学位论文属于 不保密□。 (请在以上相应方框内打“√”) 作者签名 日期 年 月 日 导师签名 日期 年 月 日 万方数据摘 要 - I - 摘 要 近年来,国内外学者对不确定数据流的聚类 问题进行了大量的 研究 ,但仍 有不少问题尚待 解决 。大多数不确定数据流聚类算法不能在线得到精确的聚类结果;现有算法采用固定划分网格的方法, 不能 有效 处理边界点; 已有 基于网格的算法,对概率密度网格单元 缺少 有效的存储结构。 这些问题的研究对于不确定数据流 的聚类分析 以及在具体领域的应用都具有 重要的意义。 首先, 为了 实现对不确定数据流的 在线聚类,提出 了 一种基于概率密度网格结构的不确定数据流聚类算法 。该算法 采用计数型滑动窗口 ,以 反映不确定数据流的当前情况。同时, 采用 概率密度网 格 的存储结构 ,以 使 算法能够发现任意形状的簇 。另外, 还定义 网格概率密度相似度 , 以实现初始化及更新聚类,提高算法的实时性。 其次, 为了 更好地处理边界点问题, 提出 了 一种基于可调整的概率密度网格结构的 不确定数据流 聚类算法 。该算法采用可调整的概率密度网格技术来处理稀疏网格单元 ,以提高聚类质量 。同时,还定义 概率密度网格聚类特征用以存储不确定数据流的概要信息。另外, 在概率密度的定义中引入 时间 衰减 因子,以 降低历史数据对聚类结果 的影响 。 最后, 为了有效存储网格单元, 提出 了 一种基于概率密度网格树的不确定数据流聚类算法 。该算法 将一种树型概要数据结构引入到不确定数据流聚类算法中 。首先把 不确定元组按其属性值分配到一棵多叉树中 ,以 消除空网格对聚类结果的影响 。 同时, 设置时间间隔,以提高算法的执行效率。 另外, 还引入 噪音阈值函数,以有效 发现噪音叶子节点 。 本文通过实验对上述提出的算法 进行 验证,并与已有经典算法 进行 比较分析。 关键词 不确定数据流 ; 聚类 ; 在线聚类; 可调整的 概率密度网格 ; 概率密度 网格树 万方数据Abstract - II- Abstract In recent years, clustering algorithms for uncertain data stream have been extensively studied, but there are still many issues to be researched and resolved. Most existing uncertain data stream clustering algorithms can not generate the final accurate clustering results. And the existing traditional grid-based clustering algorithms used the fixed meshing have the disadvantage of low clustering accuracy. Simultaneously, they are lack of effective storage structure for probability density grid cells. The solution of these problems has an important influence on optimizing clustering algorithms of uncertain data stream, application and so on. Firstly, in order to clustering uncrtain data streams online, this paper proposes a novel algorithm PDG-OCUStream, Probability Density Grid-based Online Clustering for Uncertain Data Streams, where a count-based sliding window is introduced to reflect the current situation of the uncertain data stream. Meanwhile, in order to achieve initializing and updating clusters, the grid probability density similarity is defined. In addition, in order to obtain clusters of arbitrary shapes, this paper adopts the storage structure based on probability density grid structure, and the clustering quality can be effectively controlled by setting probability density threshold. Secondly, in order to improve the accuracy of clustering uncertain data streams, this paper proposes a novel algorithm APDG-CUStream, Adjustable Probability Density Grid-based Clustering Algorithm. It adopts adjustable probability density grid structure technology to enchance the accuracy of clustering. Meanwhile, the definition of Probability Density Grid Clustering Feature is defined to store the summary ination of uncertain data streams. In addition, the time decay factor is introuduced to reduce the influence of outdated data on clustering results. Lastly, in order to store the probability density grid cells effectively, this paper proposes a novel algorithm PDGT-CUStream, Clustering Uncertain Data Streams based on Probability Density Grid-Tree, where a tree summary data structure is introduced to the enviroment of clustering uncertain data streams. Firstly, the 万方数据Abstract - III - uncertain tuples are assigned to a probability density tree, to eliminate the effects impact on the clustering results by the empty grids. Meanwhile, the time interval is setted to reduce the computation and improve the efficiency of algorithm. In addition, the noise threshold function is introuduced to find the noise leafnodes effectively. The feasibility and effectiveness of the above proposed algorithms are verified through experiments. Combining with classical algorithms and s, they are analyzed and compared. Keywords uncertain data streams; clustering; online clustering; adjustable probability density grid; probability density grid tree 万方数据目 录 - IV- 目 录 摘 要 ...................................................................................................................... I Abstract .................................................................................................................... II 第 1 章 绪 论 ......................................................................................................... 1 1.1 不确定数据流挖掘技术 ................................................................................ 1 1.1.1 不确定数据流挖掘研究背景和意义 ...................................................... 1 1.1.2 不确定数据流挖掘的任务 ...................................................................... 2 1.2 不确定数据流聚类分析研究现状 ................................................................. 3 1.2.1 国内外研究现状 ..................................................................................... 3 1.2.2 存在的问题 ............................................................................................. 5 1.3 课题的主要研究内容 .................................................................................... 6 1.4 本文的结构安排 ............................................................................................ 7 第 2 章 基于概率密度网格结构的不确定数据流在线聚类算法研究 ................... 9 2.1 引言 ................................................................................................................ 9 2.2 问题定义 ...................................................................................................... 10 2.3 PDG-OCUStream 聚类算法设计 ................................................................. 13 2.3.1 PDG-OCUStream 聚类算法框架 .......................................................... 13 2.3.2 初始化聚类子算法 ............................................................................... 15 2.3.3 更新聚类子算法 ................................................................................... 15 2.4 本章小结 ...................................................................................................... 17 第 3 章 基于可调整的概率密度网格结构的不确定数据流聚类算法研究 ......... 18 3.1 引言 .............................................................................................................. 18 3.2 问题定义 ...................................................................................................... 19 3.3 APDG-CUStream 算法设计 ......................................................................... 21 3.3.1 APDG-CUStream 聚类算法框架 .......................................................... 21 3.3.2 初始调整聚类算法 ............................................................................... 22 3.4 本章小结 ...................................................................................................... 23 万方数据目 录 - V - 第 4 章 基于概率密度网格树的不确定数据流聚类算法研究 ............................ 25 4.1 引言 .............................................................................................................. 25 4.2 问题定义 ...................................................................................................... 26 4.3 PDGT-CUStream 算法设计 .......................................................................... 28 4.3.1 时间间隔 gap 与噪音阈值函数的确定 ................................................ 28 4.3.2 PDGT-CUStream 聚类算法框架 ............................................................ 29 4.3.3 初始化算法和聚类叶子节点算法 ........................................................ 30 4.4 本章小结 ...................................................................................................... 31 第 5 章 算法实现及性能分析 ............................................................................... 33 5.1 实验数据和实验环境 .................................................................................. 33 5.2 PDG-OCUStream 算法性能分析 ................................................................. 34 5.2.1 PDG-OCUStream 算法聚类质量分析 .................................................. 34 5.2.2 PDG-OCUStream 算法执行效率分析 .................................................. 35 5.2.3 不同概率密度阈值对 PDG-OCUStream 算法的影响 .......................... 36 5.3 APDG-CUStream 算法性能分析 ................................................................. 37 5.3.1 APDG-CUStream 算法聚类质量分析 .................................................. 37 5.3.2 APDG-CUStream 算法执行效率分析 .................................................. 38 5.3.3 不同概率密度网格粒度对 APDG-CUStream 算法的影响 .................. 40 5.4 PDGT-CUStream 算法性能分析 .................................................................. 41 5.4.1 PDGT-CUStream 算法执行效率分析 ................................................... 41 5.4.2 不同划分精度对 PDGT-CUStream 算法的影响 .................................. 42 5.5 本章小结 ...................................................................................................... 44 结 论 .................................................................................................................... 45 参考文献 ................................................................................................................ 47 攻读硕士学位期间承担的科研任务与主要成果 .................................................. 52 致 谢 .................................................................................................................... 53 作者简介 ................................................................................................................ 54 万方数据第 1 章 绪 论 - 1 - 第 1 章 绪 论 随着 通信技术、计算机和互联网络的快速发展 , 以及传统的确定性数据管理技术的不断发展,信息技术正在不断改变整个人类社会,而数据库技术和系统已经成为信息化社会基础设施建设的主要支撑 [1],确定性数据流的 管理与查询处理方法也得到了极大的发展。在传统的数据库中,数据均 是确定性的、 以精确的形式存在 。近年来,随着科学技术的进步以及各种数据收集与处理技术的不断发展,数据采集方法也越来越复杂,同时数据采集方法通常是不准确的,且基于不完整或不精确的信息等 [2],从而 导致数据存在不确定性。 同时,在如传感器网络、基于位置的服务、网络通信量监控等应用领域时时刻刻都在不断地产生的数据流中也都存在着大量的不确定性 [3],但与传统的确定性数据流不同,我们称之为不确定数据流。 再者,不确定信息的存在势必会影响数据挖掘结果的质量,而已有的数据挖掘算法只适合应用于确定数据流环境下,其中聚类作为数据挖掘的重要方法,使得不确定数据流聚类分析已成为数据挖掘领域的主要研究热点 之一 。 1.1 不确定 数据流挖掘 技术 数据挖掘 是指 通过分析大量数据来提取或“挖掘”知识,即 潜在的 有意义的关系、趋势或模式的过程。传统的 数据 流 挖掘 算法是用于确定性数据流环境下的 ,而不确定 数据流挖掘技术是 在不确定数据流中挖掘用户 感兴趣的有意义的潜在的模式。但是在不确定数据流模型中, 因为数据除了具有数据流本身的连续的、 海量的、 突变的 和 高速的 等特点 之 外,还具有不确定性,且不确定性的存在会严重影响数据挖掘的 最终 结果。因此,在数据 挖掘过程中需要对具有较高不确定性的属性与具有较低不确定性的属性采用 不同的处理方法 [4]618-619。不确定数据流 挖掘对 数据流中 不确定元组 的 不确定信息的处理技术有较高的要求。 1.1.1 不确定 数据流 挖掘研究 背景 和意义 不同于确定性数据流,不确定数据在数据挖掘范畴内的表现形式可分为存在不确定性和 属性不确定性 两种 [4]609-611, 存在 不确定性 元组不确定性 主要描述 数万方数据燕山大学工学硕士学位论文 - 2- 据 元组的存在与否 具有一定的概率,这种概率性同时又会影响到其他数据元组的存在,在通常情况 下,假设各元组之间是相互独立的,以便在不同的应用中进行数据处理; 而 属性 不确定性 值不确定性 常 以概率 密度 函数 或其他统计量 方差 、标准差 等 来 描述特定属性的不确定性。由于 不确定性信息的存在 , 传统的 适用于确定 性 数据流的数据挖掘技术难以对 不确定 数据 流 的不确定信息进行处理,从而降低了挖掘结果的质量。 目前 , 基于不确定数据流模型的研究已成为重要的研究课题。 针对不确定数据流的研究主要包括 两大方面, 数据管理和数据挖掘。 一方面 ,由于传统的数 据管理技术已经无法更好地处理 数据中的不确定信息,大批学者和工业界对研究和发现 新型的不确定数据管理技术产生了浓厚的兴趣。主要研究方向包括数据不确定性的表示与模型定义 [5,6]、预处理和集成 [7-11]、存储与索引 [12-15]以及查询分析处理 [16-19]等等。 例如 针对不确定 数据流的索引技术研究了概率阙值索引技术 [20]和 U-Tree 技术 [21];针对不确定 数据流研究新的数据 流分析方法 包括 计算相异元素个数的 pFMProbabilistic Flajolet-Martin方法 和 计 算 F2 的pAMSProbabilistic Alon-Matias-Szegedy方法 [22],以及处理 不确定 数据流上的 聚类 问题的 ECFError-based Clustering Feature方法 [23], 等 等 。 另一方面 ,基于不确定 数据 的挖掘技术也得到了广泛 的研究 ,包括聚类 分析 [24]、分类 [25]、频繁项集挖掘 [26]和孤立点检测 [27]等。 不确定数据流挖掘技术在现实应用 的许多应用领域 中 都 有着广阔的前景,例如, GPS 定位系统管理、 传感器网络监测 、股票分析 以及 信息检索 等 都是不确定数据流挖掘的重要问题。 鉴于 传统的数据 流 挖掘方法只能应用于确定性数据流环境下, 因此, 如何 使用有限的内存空间对不确定数据流进行快速有效地分 析以获取有用的信息;如何扩展已有的确定性数据流挖掘算法使其适用于在 不确定数据流 模型下进行数据挖掘;如何在现有的硬件基础上改进算法以提高对不确定数据流的挖掘 质量和挖掘效率等等都给 基于 不确定数据流 的 挖掘技术的研究带来了空前的机遇与挑战。 1.1.2 不确定 数据流 挖掘的 任务 不确定 数据流挖掘 是从 不断到来的 不确定 数据流中挖掘 出有意义的用户感兴趣的模式。目前针对不确定 数据流的挖掘技术主要包括 聚类 分析 、频繁 模式 挖万方数据第 1 章 绪 论 - 3 - 掘和孤立点检测等。因此, 不确定数据流挖掘的任务有聚类分析、频繁模式挖掘及孤立点分析等。 聚类分析 作为数据挖掘的一种主要 方法,是指把数据集合中的数据对象划分为若干组不同的类或簇的过程,并使得同一组内对象的相似度尽可能的高,而不同组间对象的相似度尽可能的低。 目前针对不确定数据的聚类研究主要有基于划分的聚类算法,基于密度的聚类算法以及基于网格的聚类算法。 聚类分析已被广泛的应用于许多领域,如在信息检索领域中可以对文档进行分类,改善检索的效率,从而提高人们的工作效率;在生物学上可以用来对动植物以及基因进行分类,获取对 种群的认识;在 电子商务中 可以通过聚类分析得到具有相似浏览行为的客户,并分析客户的共同特征,可以更好的了解客户,为用户提供个性化的服务 [28]。 频繁 模式 挖掘是关 联分析的核心部分,主要是用来挖掘隐藏在数据库中的令人感兴趣的关系 模式。不确定 数据流的频繁 模式 挖掘主要是通过对传统的频繁 模式 挖掘算法改进,例如 UF-streaming[29]等。频繁 模式 挖掘技术在商业领域的应用,可以为商业制定销售策略。 孤立点检测 是发现不能与预先建立模型 拟合的点、远离大部分其它数据点或者是低密度区域中远离近邻的点。孤立点检测可以消除孤立点对聚类算法产生的簇集合的影响。在 医学 和 商业 等领域,通过对孤立点检测有利于 领导者制定更准确的 决策。 1.2 不确定 数据流聚类 分析研究现状 数据流是实时、 有序 、 连续的 数据序列,数据流中的元组按时间先后顺序 依次 出现。数据流聚类分析是指对一个给定的数据集合,将其划分为一个或多个簇的过程,使处于同一簇中的对象具有较高的相似性, 而 不同簇中的对象具有较大的差异性。传统的数据流聚类算法只是针对确定性数据流而言的,随着各种 数据处理分析技术的发展, 使得 不确定数据流存在于各个应用领域。因此,基于 不确定数据流 模型 的聚类研究 与 分析 已成为一个 新的研究课题 。 1.2.1 国内外研究现状 不确定数据流聚类分析作为聚类分析 的一个重要研究方向,受到了国内外研究学者的广泛关注 。近年来,国 内 外学者对不确定数据流聚类算法做了大量的研万方数据
展开阅读全文
收藏
下载资源

加入会员免费下载





足球比分直播