空间对象和移动对象聚类算法研究

摘要

聚类分析作为数据挖掘的一个重要研究分支,根据在数据中发现的描述对象及其关系的信息,依据各簇内对象相似性最大化和各簇间对象相似性最小化的基本聚类分析原则,将对象划分为紧密且独立的簇集。目前,由于各应用数据库中的数据越来越大,聚类分析已广泛应用于各种研究领域,成为数据挖掘领域中一个非常活跃的研究课题。随着数据收集技术、计算机网络和数据库技术的飞速发展,各种复杂类型的数据有了爆炸性的增长,因此迫切需要对复杂数据类型探索新的数据挖掘技术。本文对空间非移动对象聚类和移动对象轨道聚类这两个问题进行研究,从改善空间非移动对象聚类效果、移动对象聚类效果、提高算法时间复杂度和减少输入参数敏感性等角度对其中急需解决的问题进行了研究,主要工作如下:
　　 (1)根据空间对象的邻域、反邻域和局部密度构造了基于邻域的局部异常因子,提出了一种基于微簇的对称邻域聚类算法BMSNC。BMSNC首先运用经典的聚类算法将原数据集进行聚类产生一定量的微簇,然后将每一个微簇的中心代表这整个微簇,通过对称邻域聚类算法在进一步进行聚类。该算法能有效快速的对大数据集进行聚类分析,并且解决了不能从大的、稀疏的聚类中识别出小的、稠密的邻近聚类这一缺陷,这就使得聚类结果的准确度大大提高。在真实和合成数据集上的实验结果表明,BMSNC是可行、有效的。
　　 (2)k-近邻算法的结果依赖于距离度量的选取,这种距离通常涉及所有的特征,在距离公式中引入一些特征权参数后,其聚类结果将依赖于这些权值,从而可以通过调整这些权值来优化聚类结果。本文根据一种学习权值算法以改进聚类准确率提出了基于加权邻域聚类算法BWNC,BWNC就是为每一个属性加一个特征权参数,让不同的属性在聚类中起不同的作用。从数学意义上讲,这种权值学习相当于欧氏空间中对一组点进行线性变换。不仅对每个属性学习权值,而且可以对每一个测试样本点的近邻基于它们到测试点的距离进行加权,通过实验表明该算法能很大程度上使得聚类结果更加准确、有意义。
　　 (3)在已有的轨道聚类算法TRACLMS基础上,提出了一种基于对称邻域的轨道聚类改进算法BSNTC。BSNTC解决了TRACLUS由于使用两个全局参数Eps和MinLns,存在不能从大的、稀疏的轨道聚类中识别出小的、稠密的邻近轨道聚类这一缺陷,同时BSNTC只需要输入一个参数k,减少了算法对输入参数敏感性问题。通过一系列的实验结果表明,BSNTC在保持TRACLUS时间效率的同时改善了轨道聚类效果。

目录

文摘

英文文摘

图表清单

注释表

第一章 绪论

1.1 数据挖掘概述

1.1.1 产生和发展

1.1.2 研究目的和意义

1.1.3 国内外研究状况

1.2 选题依据

1.3 本文的主要内容和组织结构

第二章 聚类分析

2.1 聚类分析

2.1.1 聚类分析的定义

2.1.2 聚类分析的基本要求

2.1.3 主要聚类方法综述

2.2 空间对象聚类分析

2.2.1 空间索引

2.2.2 k最近邻聚类算法

2.2.3 聚类结果的评估标准

2.3 移动对象聚类分析

2.3.1 代表性聚类算法

2.3.2 聚类结果的评估标准

2.4 本章小结

第三章 空间对象聚类分析

3.1 对称邻域的相关概念

3.1.1 k-近邻相关概念

3.1.2 对称邻域引入及其概念

3.2 基于微簇的对称邻域聚类算法BMSNC

3.2.1 微簇的概念

3.2.2 BMSNC算法

3.2.3 实验与性能分析

3.3 加权邻域聚类算法BWNC

3.3.1 问题的提出

3.3.2 特征权值的学习

3.3.3 实验及分析

3.3.4 时间效率评价

3.4 本章小结

第四章 移动对象聚类分析

4.1 轨道聚类简述

4.1.1 轨道聚类相关概念

4.1.2 轨道聚类框架

4.2 基于对称邻域的轨道聚类算法BSNTC

4.2.1 相关概念

4.2.2 基于对称邻域轨道聚类算法

4.2.3 实验数据分析和评价

4.3 本章小结

第五章 结束语

5.1 本文的总结

5.2 未来研究方向

参考文献

致谢

在学期间的研究成果及发表的学术论文