数据挖掘实验指导书(2)

长沙学院信息与计算科学系 数据挖掘实验指导书

实验二 DBSCAN算法实现

一、实验目的

要求掌握DBSCAN算法的聚类原理、了解DBSCAN算法的执行过程。在此基础上，利用DBSCAN算法对给定样本数据实现聚类过程。

实验类型：综合 计划课间：4学时

二、实验内容

1、了解DBSCAN算法的聚类原理； 2、了解DBSCAN算法的执行过程； 3、编程实现DBSCAN算法； 4、对给定样本数据实现聚类过程

三、实验方法

3.1、DBSCAN算法的基本概念

? 对象的ε-邻域：给定对象在半径ε内的区域；

? 核心对象：若一个对象ε-邻域至少包含最小数目MinPts个对象，则称该对

象为核心对象；

? 直接密度可达：给定一个对象集合D，若p是在q的ε-邻域内，而q是一个核

心对象，则称对象p从对象q出发是直接密度可达的；

? 密度可达：若存在一个对象链p1,p2,?,pn,p1=q,pn=p,对pi∈D,pi+1是从pi

关于ε和MinPts直接密度可达的，则称对象p是从对象q关于ε和MinPts是密度可达的；

? 密度相连：若对象集合D中存在一个对象o，使得对象p和q是从o关于ε和

MinPts是密度可达的，则对象p和q是关于ε和MinPts密度相连的； ? 噪声：一个基于密度的簇是基于密度可达性的最大的密度相连对象的集合，

不包含在任何簇中的对象被认为是噪声

3.2、实现的基本思想

通过检查数据集中每个对象的ε-邻域来寻找聚类。如一个点p的ε-邻域包含多于MinPts个对象，则创建一个p作为核心对象的新簇。然后，DBSCAN寻找从这些核心对象直接密度可达的对象，这个过程可能涉及一些密度可达簇的合并，当没有新的点可以被添加到任何簇时，聚类过程结束。

第6页

长沙学院信息与计算科学系 数据挖掘实验指导书

3.3 算法描述

输入：包含n个对象的数据库，半径，最小数目MinPts; 输出：所有生成的簇，达到密度要求 过程： Repeat

从数据库中抽取一个未处理的点；

IF 抽出的点是核心点 THEN 找出所有从该店密度可达的对象，形成一个簇； ELSE 抽出的点是边缘点(非核心对象)，跳出本次循环，寻找下一点； Until 所有点都被处理

四、实验步骤 4.1 数据结构的分析 Struct List

{Int data[TOTALPOINT]; Int head=0; Int tail=-1;} List ClusterList; Struct Node

{ int Attribute1; int Attribute2} Node DataBase[TOTALPOINT];

Boolean Neighbor[TOTALPOINT][TOTALPOINT]; Int ClusterNo[TOTALPOINT];

4.2 实验数据 P186 表5-8

4.3 计算临近

For (i=0;i

For (j=0;j

If (dist(DataBase[i],DataBase[i])<ε then Neighbor[i][j]=true;Neighbor[j][i]=true;

第7页

长沙学院信息与计算科学系 数据挖掘实验指导书

4.4 聚类划分 CurrentClusterNO=0; For (i=0;i

NeighborPointsNum=0;

for (j=0;j

if (Neighbor[i][j]==true)NeighborPointsNum++; if (NeighborPointsNum)>=MinPts {

// 记录邻居中已被划分的簇号 ClusterList.tail=-1; ClusterList.head=0; For (j=0;j

If (Neighbor[i][j]==true) &&(ClusterNo[j]>0)

Then {ClusterList.tail++;

ClusterList.data[tail]=ClusterNo[j]} // 当前核心对象的邻居对象划分为一簇 For (j=0;j

ClusterNo[j]=CurrentClusterNO;

// 将多个簇合并

While ClusterList.head<=ClusterList.tail { for (j=0;j

If (ClusterNo[j]==ClusterList.data[head]) ClusterNo[j]=CurrentClusterNO;

ClusterList.head++; } } }

4.5 聚类结果输出

For (i=-1;i

第8页

长沙学院信息与计算科学系 数据挖掘实验指导书

{

Printf(“\\n输出第%d簇的对象：”,i); For (j=0;j

If (ClusterNo[j]=i) printf(“%d\\t”,j); }

五、注意事项 5.1. 噪声数据的处理

5.2 已划分的类存在直接密度可达时的相关类数据的合并

第9页

长沙学院信息与计算科学系 数据挖掘实验指导书

实验三 ID3算法实现

一、实验目的

通过编程实现决策树算法，信息增益的计算、数据子集划分、决策树的构建过程。加深对相关算法的理解过程。 实验类型：验证 计划课间：4学时

二、实验内容

1、分析决策树算法的实现流程；

2、分析信息增益的计算、数据子集划分、决策树的构建过程； 3、根据算法描述编程实现算法，调试运行； 4、对课后P161的第10题进行验算，得到分析结果。

三、实验方法

算法描述：

以代表训练样本的单个结点开始建树；

若样本都在同一个类，则该结点成为树叶，并用该类标记；

否则，算法使用信息增益作为启发信息，选择能够最好地将样本分类的属性； 对测试属性的每个已知值，创建一个分支，并据此划分样本； 算法使用同样的过程，递归形成每个划分上的样本决策树 递归划分步骤，当下列条件之一成立时停止： 给定结点的所有样本属于同一类；

没有剩余属性可以进一步划分样本，在此情况下，采用多数表决进行

四、实验步骤

1、算法实现过程中需要使用的数据结构描述： Struct

{int Attrib_Col; // 当前节点对应属性 int Value; // 对应边值 Tree_Node* Left_Node; // 子树

Tree_Node* Right_Node // 同层其他节点 Boolean IsLeaf; // 是否叶子节点 int ClassNo; // 对应分类标号 }Tree_Node;

第10页

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据挖掘实验指导书(2)在线全文阅读。