移动数据库课程计报告.docx

道路网络中基于结点的静态聚类算法（java） ————移动数据库课程设计报告班级： 学号： 姓名： 指导老师： 学号： 年 月目 录第一章聚类算法基本思想11.1聚类分析11.2基本模型11.3基于结点的算法2第二章代码设计42.1需求分析42.2设计思想42.3具体设计42.4总体流程72.5总体流程图8第三章异常处理8第四章运行效果及实现功能85.1查看文件85.2运行控制台95.3实现功能9第五章设计体会9第六章源代码105题：基于结点的静态聚类算法（Java）聚类算法基本思想 聚类分析【总述】在这里我们主要讨论基于道路的静态聚类算法，道路网络中有两种聚类方法，一种是基于边的，另一种是基于结点的，基于边的需要先分裂后聚集，基于结点的要通过结点直接聚合，两种方法完全不同，以下只讨论基于结点的。【聚类分析】：对数据对象进行分组，使得同一组中的对象之间具有较高的相似度，而不同组中的对象差别较大. 基本模型网络表示：一个网络表示为一个无向带权图G=(V, E, W)， （其中，V是顶点集合，E是边集合，W为正实数集合表示边所对应的权值）。网络中的一个对象位于网络中的边e ( ) 上，对象在网络中的位置可以表示为一个三元组用以取代欧氏的空间坐标），其中(ni, nj)是对象所在网络边的两个结点； 是对象与结点ni之间的相对距离。 （注：）一个对象位于且仅位于一条网络边上。网络距离：对象之间的网络距离（点），假设p和q为网络中的两个对象（点），其位置分别为 和，则这两个对象点的直接距离为（其中，对象p和q在同一条网络边上，即na = nc 且 nb=nd; 否则，对象p和q不在同一网络边上，其直接距离为无穷大）同一网络边上的对象与结点之间的直接距离，这里的结点指的是边的交叉点 聚类之间的网络距离：聚类不同边界对象之间最小的网络距离聚类块：为根据阈值e构建的某个网络边上的一个微小聚类，CB表示为：（其中：O为对象的集合，其中：O为对象的集合，满足：，）即任意两个相邻对象之间的直接距离小于等于e；（na,nb）为聚类块所在的边；head, tail 分别为聚类块的起点位置和终点位置，通过相对于边起点的相对距离来表示；ObjNum为CB中对象的个数。所有的对象都在相同的边（na,nb）上，聚类的位置由(head, tail)来决定，其长度为|tail - head|.聚合过程 聚类块的e有效结点为：聚类块所在边的两个结点中与聚类块的距离小于等于e的结点；对于聚类块 ，假设O1和Om分别为聚类块相对于结点na和nb的两个边界对象，若，则na是CB的有效结点；若，则nb不是CB的有效结点。即：聚类的e有效结点为相邻结点和所包含的结点中与该聚类之间的距离小于等于e的结点 基于结点的算法【总述】： 基于结点的对象聚类首先从某个结点出发，把结点周围的对象聚类在一起，并扩展到相邻结点，将相邻结点周围满足条件的对象也包含到该聚类中，直到聚类不再扩张；然后，对没有遍历过的结点循环这个过程，直到结点周围的对象都已指定给某个聚类为止；最后对网络边上未形成聚类的对象，根据对象的聚类条件来判断是否能单独形成聚类。 （1）两个步骤：：初始阶段：先判断每个相邻边上与结点相邻的对象与该结点距离是否小于等于阈值e，以此来过滤掉不必遍历的边；然后对满足条件的相邻边按照对象与结点的距离排序，将结点最邻近的对象作为初始聚类。扩展阶段：按顺序依次遍历相邻边上的对象来扩展初始聚类，继续扩展到相邻结点；再对相邻结点周围的相邻边进行排序，按顺序遍历相邻边上的对象，直到相邻对象之间的距离大于阈值e，聚类不能再扩展为止。（2）实例分析假设阈值e=10，如图为只以结点J1聚合后的效果图：（3）算法实现：代码设计 需求分析根据题目，我自己设计给定位于一个网络中N个对象点的集合（如：（1，2，5）表示对象点在第一和第二条边的道路上，并且到第一条边的距离为5）。然后通过对这些对象进行聚类的过程即转换为根据它们的直接距离形成聚类块，并根据聚类块之间的网络距离合并聚类块。 设计思想首先，要给定两种类型的值，我定义了第一种类型（对象点）在道路内的平凡点：A（ni，nj，pos）表示该A对象点i和点j上，且到i点的距离为pos，存储在一个文件中；第二种类型边的类型（ni，nj，dis），表示边i和边j的距离为dis，存储在另一个文件中。其次，要从文件中读取数的值，以此来初始化链表和边的长度值，然后以各个边为一个链表。从起始的边结点开始，选出距离最近的对象点，满足条件的则加入链表中，然后将该对象点作为下一个起始点，依次循环，出现不满足条件则回到边的结点。每次访问对象点时判断该对象点到该边上的结点距离是否小于e，若小于则将该边结点也加入这个聚合中然后，如果遍历到终点时还是在阈值范围内的，就