基于共享最近邻的聚类算法的研究与应用

摘要

本文针对现有的共享最近邻聚类算法，提出一种新型的基于共享最近邻的聚类算法，并将改进后的算法应用到真实数据集和零件的组合过程中。通过聚类结果和实验仿真表明，本文提出的共享最近邻算法能够提高算法有效性，同时节省算法执行时间。
　　为了避免求k-最近邻带来的庞大计算量，本文提出一种k-最近邻空间划定方法，降低算法的整体时间复杂度。根据先验知识给出待划分维的数目，在确定个数的特征向量上进行操作，有利于减少求点对之间距离所需的计算量。根据方差最大化原理确定待划分的维，在较为离散的数据分布中获得相对理想的划分效果，使其能够最大程度地代表数据对象的基本特征，同时提高搜索效率。最后，对确定的维进行基于密度的划分，每个数据对象在其数据空间范围内对k-最近邻进行求取。该k-最近邻空间划定方法极大地减少算法的计算量，在保证结果精度的前提下大大提高算法执行效率。
　　传统的共享最近邻定义只针对共享数据对象的个数，并没有充分考虑距离带来的影响，具有一定的局限性。改进后的共享最近邻综合考虑数据对象距离远近和个数两个因素，通过权值的方式对邻近性度量进行优化，体现其距离意义，使度量标准更符合实际要求。
　　在k-最近邻空间划定方法和改进后的共享最近邻定义的基础上，本文提出一种新型的基于共享最近邻的聚类算法。通过在真实数据集Iris和Pendigits上的聚类实验表明，优化后的算法运行速度更高、聚类结果更准确，其优势在大规模数据集中体现地更加明显。
　　将改进后的算法应用到零件组合的实验中，以聚类后的簇为单位进行组合，有效地避免传统的以零件为单位进行组合带来的庞大计算量。通过两种算法在零件组合实验中的运行结果可知，改进后的聚类算法具有更高的聚类精度，同时大大减少算法的运行时间。为了更好地适应实际的大批量生产模式，使用改进后的算法对不同规模数据集和不同维度数据集进行聚类。通过实验仿真结果可知，本文提出的共享最近邻算法具有较高的可伸缩性。

目录

封面

声明

中文摘要

英文摘要

目录

第1章 绪论

1. 1 选题的背景及意义

1. 2 国内外的研究现状及发展趋势

1. 3 论文的主要研究内容

1. 4 论文的组织结构

第2章 数据挖掘与聚类分析

2. 1 数据挖掘概述

2. 2 聚类分析概述

2. 3 常用的聚类算法及其分析

2. 4 本章小结

第3章 基于共享最近邻的聚类算法及改进措施

3. 1 最近邻关系

3. 2 传统的基于共享最近邻的聚类算法

3. 3 k-最近邻空间的划定

3. 4 改进的共享最近邻度量标准

3. 5 改进的基于共享最近邻的聚类算法

3. 6 聚类实验及其分析

3. 7 本章小结

第4章 共享最近邻聚类算法的实验应用

4. 1 实验背景

4. 2 实验总体设计

4. 3 实验分析

4. 4 组合方案

4. 5 实验仿真与分析

4. 6 实验结论

4. 7 本章小结

第5章 总结与展望

参考文献

个人简介

致谢