开题报告张传晓.docx

开题报告张传晓.docx

《开题报告张传晓.docx》由会员分享，可在线阅读，更多相关《开题报告张传晓.docx（7页珍藏版）》请在冰点文库上搜索。

开题报告张传晓

山东科技大学泰山科技学院

本科毕业设计（论文）开题报告

题目基于密度聚类的应用研究

系部名称：

信息工程系

专业班级：

计算机科学与技术2011-2班

学生姓名：

张传晓

学号：

1143010226

指导教师：

苏娜

填表时间：

2013年4月12日

设计（论文）题目

基于密度聚类的应用研究

设计（论文）类型

工程设计

应用研究

开发研究

基础研究

其它

√

一、课题目的和意义

聚类分析是数据挖掘中的一个重要研究领域没事一种数据划分或分组处理的重要手段和方法。

聚类无论在商业领域，还是在生物学、web文档分类、图像处理等其他领域都得到了有效的应用。

目前聚类算法大体上分为基于划分的方法、基于层次的方法、基于密度的方法、基于网格的方法、基于模型的方法以及模糊聚类。

聚类的用途很广泛。

在商业上，聚类可以帮助市场分析人员从他们的消费者数据库中区分出不同的消费群体来，并且概括出每一类消费者的消费模式或者说习惯；在生物学中，它可以用来辅助研究动物植物的分类，可以迎来分类具有相似功能的基因，还可以用来发现人群中一些潜在的结构等等；聚类还可以从保险公司的数据库中发现汽车保险中具有较高赔率的人群；还可以从一个城市的房地产信息数据库中，根据房型，房价以及地理位置分成不同的类；还可以用来从万维网上分类不同类型的文档等。

同时，聚类分析作为数据挖掘中的一个模块，它既可以单独作为一个单独的工具以发现数据库中数据分布的一些深入的信息，并概括出每一类的特点，或者把注意力放在某一个特定的类上以做出进一步的分析；聚类分析也可以作为数据挖掘算法中其他分析算法的一个预处理步骤。

本文采用聚类分析方法，主要是基于密度的聚类方法，对于数据流进行聚类分析。

基于密度的聚类方法在聚类分析技术中占有很重要的地位，在金融、市场营销，信息检索，信息过滤，科学观测与工程给个领域广泛应用，是聚类分析中的研究重点。

本文对基于密度的聚类算法就行了研究，并以DBSCAN（Density-BasedSpatialClusteringofApplicationwithNoise）为基础。

二、文献综述（课题的应用背景和前景）

早期有学者提出，可以将处理大规模数据集的聚类算法应用到数据流聚类上，基于密度的方法（density一basedmethod）的基本思想是：

将具有足够密度的区域划分为簇，即对于给定类中的数据点，如果临近区域的密度超过某一个闭值，则继续进行聚类，从而可将获得的簇视为数据空间中由低密度区域分割开的高密度数据对象区域，其目的是发现任意形状的簇”基于密度的方法与其它方法的一个根本区别是：

它不是基于各种各样的距离的，而是基于密度的”这样就能克服基于距离的算法只能发现/类圆形0的聚类的缺点”这个方法的知道思想就是，只要一个区域中的点的密度大过某个阀值，就把它加到与之相近的聚类中去”也就是说，对于给定类中的每个数据点，在一个给定范围的区域内必须至少包含一定数目的点”这样可以过滤/噪音0数据，发现任意形状的簇”代表算法有：

DBSCAN算法，OPTICS算法，DENCLUE算法等”。

DBSCAN（Density一BasedspatialClusteringofApplieationswithNoise）是一种基于密度的聚类算法，其基本思想是：

对于一个聚类中的每一个对象，在其给定半径的领域中包含的对象不能少于某一给定的最小数目，然后对具有密度连接特性的对象进行聚类”在该算法中，发现一个聚类的过程是基于这样的事实：

一个聚类能够被其中的任意一个核心对象所确定”DBSCAN算法可以挖掘任意形状的聚类，对数据输入顺序不敏感，并且具有处理异常数据（噪声）的能力”该算法将具有足够高密度的区域划分为簇，并可以在带有/噪音0的空间数据库中发现任意形状的聚类。

OPTICS算法由于DBSCAN算法需要输入两个参数，对于真实的高维数据集，参数的设置一般很难确定，而且高维的实际数据分布经常是不对称的，聚类算法只使用一个全局参数显然不能代表数据集内在的聚类结构。

为了解决这个难题，Mihael等人提出了OPTICS（OrderingPointstoIdentifytheclusteringstruCture）聚类分析方法。

OPTICS算法并不产生数据集的聚类，而是生成代表基于密度的聚类结构的一个参数化的数据库的排序”这种聚类排序包含的信息，等同于从一个宽广的参数设置范围所获得的基于密度的聚类”但这样处理，每个对象需要存储两个值一一核心距离（COre一distance）和可达距离（reaehability一distanee）。

DENCLUE（DENsity-basedCLUstEring）是一个基于一组密度分布函数的聚类算法”该算法主要基于下的思想：

（1）每个数据点的影响可以用一个数学函数来形式化的模拟，它描述了一个数据点在领域内的影响，被称为影响函数（influencefunction）；

（2）数据空间的整体密度可以被模拟为所有数据点的影响函数的总和；（3）然后聚类可以通过确定密度吸引点（densityattractor）来得到，这里的密度吸引点是全局密度函数的局部最大值。

CLQUE（ClusteringInQUEST）聚类算法对于大型数据库中的高维数据的聚类比较有效，可以高效地发现精确的聚类，它结合了基于密度的方法和基于网格的方法”CLIQUE的核心思想是给定一个多维数据点的大集合，数据点在数据空间中通常不是均衡分布的CLIQUE区分空间中稀疏的和拥挤的区域，以发现数据集合的全局分布模式”如果一个单元中的包含的数据点超过了某个输入参数，则该单元的密集的”在CLIQUE中，相连的密集单元的最大集合定义为簇。

其他基于密度的算法。

马帅等人提出了一种基于参考点和密度的快速聚类算法CURD（ClusteringUsingRefereneesandnensity）。

Man”ranjan等人提出将基于距离的k一means聚类算法和基于密度的DBSCAN聚类算法结合起来，形成一种新的聚类算法DRIDGE。

钱卫宁等人提出了面向大规模数据库的基于距离和密度的混合聚类算法等等。

三、课题主要内容（提纲）及拟解决的关键问题

DBSCAN（Density-basedSpatialClusteringofApplicationswithNoise）

是一种基于高密度联通区域的聚类算法，它将类簇定义为高密度相连点的最大集合。

它本身对噪声不敏感，并且能发现任意形状的类簇。

DBSCAN中的的几个定义：

Ε领域：

给定对象半径为Ε内的区域称为该对象的Ε领域

核心对象：

如果给定对象Ε领域内的样本点数大于等于MinPts，则称该对象为核心对象。

直接密度可达：

对于样本集合D，如果样本点q在p的Ε领域内，并且p为核心对象，那么对象q从对象p直接密度可达。

密度可达：

对于样本集合D，给定一串样本点p1，p2…。

pn，p=p1，q=pn，假如对象pi从pi-1直接密度可达，那么对象q从对象p密度可达。

密度相连：

对于样本集合D中的任意一点O，如果存在对象p到对象o密度可达，并且对象q到对象o密度可达，那么对象q到对象p密度相连。

可以发现，密度可达是直接密度可达的传递闭包，并且这种关系是非对称的。

密度相连是对称关系。

DBSCAN目的是找到密度相连对象的最大集合。

Eg：

 假设半径Ε=3，MinPts=3，点p的E领域中有点{m，p，p1，p2，o}， 点m的E领域中有点{m，q，p，m1，m2}，点q的E领域中有点{q，m}，点o的E领域中有点{o，p，s}，点s的E领域中有点{o，s，s1}。

那么核心对象有p，m，o，s（q不是核心对象，因为它对应的E领域中点数量等于2，小于MinPts=3）；

点m从点p直接密度可达，因为m在p的E领域内，并且p为核心对象；

点q从点p密度可达，因为点q从点m直接密度可达，并且点m从点p直接密度可达；

点q到点s密度相连，因为点q从点p密度可达，并且s从点p密度可达。

拟解决的问题将区域内对象遍历，在数据库中发现簇和噪声。

簇可等价于集合D中，这个簇核心对象密度可达的所有对象的集合。

算法：

DBSCAN

输入：

E — 半径

 MinPts — 给定点在E领域内成为核心对象的最小领域点数

 D — 集合

输出：

目标类簇集合

方法：

repeat

1） 判断输入点是否为核心对象。

2） 找出核心对象的E领域中的所有直接密度可达点。

util 所有输入点都判断完毕。

 repeat针对所有核心对象的E领域所有直接密度可达点找到最大密度相连对象集合，中间涉及到一些密度可达对象的合并。

Util 所有核心对象的E领域都遍历完毕。

四、拟采用的思路和方法

DBSCAN（Density-BasedSpatialClusteringofApplacationswithNoise）是一个比较有代表性的基于密度的聚类算法。

与划分和层次聚类方法不同，它将簇定义为密度相连的点的最大集合，能够把具有足够高密度的区域划分为簇，并可在噪声的空间数据库中发现任意形状的聚类。

DBSCAN算法具有足够高密度的区域划分为一类，并可以在带有噪声的空间数据库中发现任意形状的聚类

DBSCAN算法是基于密度的聚类算法，它将类看作是数据空间中被低密度区域分割开的高密度对象区域。

在该算法中，发现一个聚类的过程是基于这样的事实：

一个聚类能够被其中的任意一个核心对象所确定。

其基本思想是：

考察数据库D中的某一个点P，若P是核心点，则通过区域查询得到该点的邻域，邻域中的点和P同属于一个类，这些点将作为下一轮的考察对象，并通过不断地对种子点进行区域查询来扩展它们所在的类，直至找到一个完整的类。

DBSCAN算法在对类的划分时采用的方法是：

比较此数据点到各类中心的距离，若小于某阈值，则属于此类。

可见阈值的选择直接影响类的划分及类的数目。

这种方法带来的问题就是：

距离近的不一定属于同一类，在阈值半径内的不一定属于同一类。

五、课题总体安排和进度计划

此处填写课题进行的阶段与时间划分：

第一阶段：

需求获取或背景研究；4月10日至4月15日；

第二阶段：

资料整理、归纳或可行性研究与需求分析；4月16日至4月20日；

第三阶段：

系统分析与总体设计阶段；4月21日至4月25日。

第四阶段：

数据库的设计；4月26日至5月2日。

第五阶段：

详细设计阶段；5月3日至5月15日。

第六阶段：

进行测试。

；5月16日至5月20日。

第七阶段；编写论文准备答辩。

参考文献（不少于8篇）

主要参考文献

[1]张天成，岳德君，于戈，等。

数据流挖掘研究及其进展[J]。

小型微型计算机系统，2008，29（12）：

2241-2246。

（ZhangTC，YueDJ，YuG，etal。

Researchanddevelopmentondatastreammining[J]。

Mini-micrcSystems，2008，29（12）：

2241-2246。

）

[2]周水庚,周傲英,曹晶.基于数据分区的DBSCAN算法[J].计算机研究与发展,2000,37（10）：

1153一1159

[3]WooKG,LeeJH.Findit：

Afastandintelligentsubspaceclusteringalgorithmusingdimensionvoting[J].InformationandSoftwareTechnology,2004,46（4）：

255-271.

[4]杨春宇,周杰.一种混合属性数据流聚类算法[J].计算机学报,2007,30（8）：

1364-1371.（YangCY,ZhouJ.Aheterogeneousdatastreamclusteringalgorithm[J].ChineseJofComputers,2007,[5]刘青宝,何勇,邓苏等基于相对密度的多分辨率聚类算法[J].小型微型计算机系统，2007（6）：

（1364-1371.）

[6]董麓，数据分析方法[M]大连：

东北财经大学出版社，2001：

103~108。

[7]候丽娟，王国胤。

粗糙集理论中的离散化问题[J]。

计算机科学，2000，27（12）：

89~94。

[8]王实。

数据挖掘中的聚类算法[J]。

计算机科学，2002，27（4）：

42

[9]《北京科技大学学报》2014年11期

[10]赵文;夏桂书;苟智坚;闫振兴;;一种改进的DBSCAN算法[J];四川师范大学学报（自然科学版）;2013年02期

[11]夏鲁宁;荆继武;;SA-DBSCAN:

一种自适应基于密度聚类算法[J];中国科学院研究生院学报;2009年04期

指导教师意见

指导教师（签名）：

年月日

所在系（部）意见

负责人（签章）：

年月日