移动数据库课程设计报告VIP

道路网络中基于结点道路网络中基于结点 的静态聚类算法的静态聚类算法 java 移动数据库课程设计报告 班级 学号 姓名 指导老师 学号 年 月 目目 录录 第一章第一章聚类算法基本思想聚类算法基本思想 1 1 1聚类分析 1 1 2基本模型 1 1 3基于结点的算法 2 第二章第二章代码设计代码设计 4 2 1需求分析 4 2 2设计思想 4 2 3具体设计 4 2 4总体流程 7 2 5总体流程图 8 第三章第三章异常处理异常处理 8 第四章第四章运行效果及实现功能运行效果及实现功能 8 5 1查看文件 8 5 2运行控制台 9 5 3实现功能 9 第五章第五章设计体会设计体会 9 第六章第六章源代码源代码 10 移动数据库课程设计移动数据库课程设计 中国地质大学 武汉 1 5 题 基于结点的静态聚类算法 Java 第一章第一章聚类算法基本思想聚类算法基本思想 1 1 聚类分析 总述 在这里我们主要讨论基于道路的静态聚类算法 道路网络中有两种聚类方法 一种是基于边的 另一种是基于结点的 基于边的需要先分裂后聚集 基于结点的要通过结点直接聚合 两种方法完全不 同 以下只讨论基于结点基于结点的 聚类分析 对数据对象进行分组 使得同一组中的对象之间具有较高的相似度 而不同组中的对象 差别较大 1 2 基本模型 1 网络表示 一个网络表示为一个无向带权图 G V E W 其中 V 是顶点集合 E 是边集合 W 为正实数集合 表示边所对应的权值 网络中的一个对象位于网络中的边 e 上 对象在网络中的位置 可以表示为一个三元组用以取代欧氏的空间坐标 其中 ni nj 是对象所在网络边的两个结点 是对象与结点 ni 之间的相对距离 注 一个对象位于且仅位于一条网络边上 注 一个对象位于且仅位于一条网络边上 2 网络距离 对象之间的网络距离对象之间的网络距离 点 假设 p 和 q 为网络中的两个对象 点 其位置分别为 和 则这两个对象点的直接距离为 其中 对象 p 和 q 在同一条网络边上 即 na nc 且 nb nd 否则 对象 p 和 q 不在同一 网络边上 其直接距离为无穷大 同一网络边上的对象与结点之间对象与结点之间的直接距离 这里的结点指的是边的交叉点 聚类之间的网络距离聚类之间的网络距离 聚类不同边界对象之间最小的网络距离 3 聚类块 为根据阈值 e 构建的某个网络边上的一个微小聚类 CB 表示为 其中 O 为对象的集合 其中 O 为对象的集合 满足 移动数据库课程设计移动数据库课程设计 中国地质大学 武汉 2 即任意两个相邻对象之间的直接距离小于等于 e na nb 为聚类块所在的边 head tail 分别为聚类块 的起点位置和终点位置 通过相对于边起点的相对距离来表示 ObjNum 为 CB 中对象的个数 所有的对 象都在相同的边 na nb 上 聚类的位置由 head tail 来决定 其长度为 tail head 4 聚合过程 聚类块的 e 有效结点为 聚类块所在边的两个结点中与聚类块的距离小于等于 e 的结点 对于聚类块 假设 O1 和 Om 分别为聚类块相对于结点 na 和 nb 的两个边界 对象 若 则 na 是 CB 的有效结点 若 则 nb 不是 CB 的有效结点 即 聚类的即 聚类的 e 有效结点为相邻结点和所包含的结点中与该聚类之间的距离小于等于有效结点为相邻结点和所包含的结点中与该聚类之间的距离小于等于 e 的结点的结点 1 3 基于结点的算法 总述 基于结点的对象聚类首先从某个结点出发 把结点周围的对象聚类在一起 并扩展到相邻结 点 将相邻结点周围满足条件的对象也包含到该聚类中 直到聚类不再扩张 然后 对没有遍历过的结 点循环这个过程 直到结点周围的对象都已指定给某个聚类为止 最后对网络边上未形成聚类的对象 根据对象的聚类条件来判断是否能单独形成聚类 1 两个步骤 初始阶段 先判断每个相邻边上与结点相邻的对象与该结点距离是否小于等于阈值 e 以此来过滤掉 不必遍历的边 然后对满足条件的相邻边按照对象与结点的距离排序 将结点最邻近的对象作为初 始聚类 扩展阶段 按顺序依次遍历相邻边上的对象来扩展初始聚类 继续扩展到相邻结点 再对相邻结点 周围的相邻边进行排序 按顺序遍历相邻边上的对象 直到相邻对象之间的距离大于阈值 e 聚类不 能再扩展为止 2 实例分析 假设阈值 e 10 如图为只以结点 J1 聚合后的效果图 3 算法实现 移动数据库课程设计移动数据库课程设计 中国地质大学 武汉 3 移动数据库课程设计移动数据库课程设计 中国地质大学 武汉 4 第二章第二章代码设计代码设计 2 1 需求分析 根据题目 我自己设计给定位于一个网络中 N 个对象点的集合 如 1 2 5 表示对象点在第一和第 二条边的道路道路上 并且到第一条边的距离为 5 然后通过对这些对象进行聚类的过程即转换为根据它们 的直接距离形成聚类块 并根据聚类块之间的网络距离合并聚类块 2 2 设计思想 首先 要给定两种类型的值 我定义了第一种类型 对象点 在道路内的平凡点 A ni nj pos 表示该 A 对象点 i 和点 j 上 且到 i 点的距离为 pos 存储在一个文件中 第二种类型边的类型 ni nj dis 表示边 i 和边 j 的距离为 dis 存储在另一个文件中 其次 要从文件中读取数的值 以此来初始化链表和边的长度值 然后以各个边为一个链表 从起始的边结点边结点开始 选出距离最近的对象点 满足条件的则加入链表中 然后将该对象点作为下 一个起始点 依次循环 出现不满足条件则回到边的结点边的结点 每次访问对象点时判断该对象点到该边上的结点距离是否小于 e 若小于则将该边结点也加入这个聚 合中 然后 如果遍历到终点时还是在阈值范围内的 就从这个边结点边结点开始循环遍历 2 3 具体设计 总述 我把代码分成了三个文件 一个是 Funtion java 用于实现调用和进行具体比较对象和从文件 读取点 一个是 nodebased java 用于进行初始化链表及主函数调用 另一个是 point java 表示 point 的 类 通过这三个文件具体实现这个程序功能 1 动态初始化链表 选用存储原始样本点 pointsList中存放一堆Point 这些点都是初始化后的对象点 arraylist在Java中 相当于链表 而这里的point是类似于结构体 用class中定义 存储最后的聚类结果 resultList中存放一堆List列表 List中用存放一堆Point对象 根据题目要求 Point类的定义主要为边的起始结点x 边的末节点y 还有距离z private static List pointsList new ArrayList private static List List resultList new ArrayList List 移动数据库课程设计移动数据库课程设计 中国地质大学 武汉 5 2 读取文件 分别读取两个文件中的值 一个是边的距离points txt 另一个文件存储对象点 以下是读取边的距离 并将它分别加入链表中 读取另一文件 并将对象点储存在链表中 public class Point private int x private int y private int z public static List getPointsList1 throws IOException List lst1 new ArrayList BufferedReader br new BufferedReader new FileReader points txt String str while str br readLine null br close return lst1 public static List getPointsList2 throws IOException List lst2 new ArrayList BufferedReader br new BufferedReader new FileReader points1 txt String str while str br readLine null for Iterator it1 lst2 iterator it1 hasNext 迭代器模式 是否存在下一个数据 Point p it1 next next br close return lst2 移动数据库课程设计移动数据库课程设计 中国地质大学 武汉 6 3 遍历访问对象点 判断是否属于该边 将对象点对象点 x y z 与边结点的 x y z 比较 将x与y相等的属于同一个链 表 判断是否在阈值e范围内 在该范围内则加入链表中 然后将该对象点作为下一个起始点 依次循环 出现不满足条件则回到边的结点 然后 依次按顺序可以访问到每个边结点的边 并将可以合并的聚类聚集到一起 if p getX q getX distance Math sqrt dz dz else if p getX q getX int dz q getZ distance Math sqrt dz dz return distance public static List KeyPoint List lst Point p int e List tmpLst new ArrayList for Iterator it lst iterator it hasNext Point q it next if getDistance p q e if tmpLst contains q 判断点 q 是否在 tmpLst 中 tmpLst add q return tmpLst for int i 0 i length i for int j 0 j length j if i j if Funtion mergeList resultList get i resultList get j resultList get j clear 移动数据库课程设计移动数据库课程设计 中国地质大学 武汉 7 通过显示函数display 将各个聚类得到的链表结果显示在控制台控制台上 最后得到的链表为 resultlist 这是以链表为数组的链表 里面包含一堆链表一堆链表 这些链表中包含一些 point 对象 2 4 总体流程 1 函数及类调用 Funtion java文件 主要用于对点和链表进行具体的操作 其中包含了较多功能函数 getdistance 计算对象点距离 keypoint 将对象点加入链表 返回的是该链表 getpointlist1 得到文件中的边边的情况 getpointlist2 得到文件中的对象点的情况 display 显示在控制台上 nodebased java文件 主要用于做链表初始化及循环遍历点和链表 Init 进行点和链表的初始化 point java文件 主要包括point的类 结构体 里面主要封装了如何从文件文件中得到point的x y z的值 x代表起始点 y 表示终点 z表示距离 这样既可以确定对象点所在的边 还可以确定每条边的距离 public static void display List List resultList int index 1 for Iterator List it resultList iterator it hasNext List lst it next if lst isEmpty continue System out println 第 index 个聚类 for Iterator it1 lst iterator it1 hasNext Point p it1 next System out println p print index 移动数据库课程设计移动数据库课程设计 中国地质大学 武汉 8 2 5 总体流程图 Nodebased Main Nodebased Init Funtion keynode funtion getpointlist1 funtion getpointlist2 Funtion display 第三章第三章异常处理异常处理 4 1出现SQL异常 使用数据库语句或调用 更新时 都必须通过 try catch SQLException e 否则会出现异常 4 2读取文件异常 在读文件中的点集时我用逗号来分割 因此 其中就要把字符串解析为数组 并且要用逗号来分割 在 其中加入如下语句 String p str split 将字符串解析为数组 以逗号来分割 this x Integer parseInt p 0 this y Integer parseInt p 1 this z Integer parseInt p 2 我把这几句放入 point 类的构造函数中 这样每次读取点时就能自动得到我们想要的值 第四章第四章运行效果及实现功能运行效果及实现功能 5 1 查看文件 查看边边和对象点对象点的数据文件 左图为边的文件 右图为对象点的文件 移动数据库课程设计移动数据库课程设计 中国地质大学 武汉 9 5 2 运行控制台 5 3 实现功能 1 将文件中的对象点聚合后加入各自的聚类中 2 增加文件的信息项 对应的输出也会增加 3 由于是依次遍历的 所以聚类的合并过程直接在扩展阶段就完成了 第五章第五章设计体会设计体会 这次课程设计作业遇到一些问题 集中在算法和语言上 1 主要把书本的算法看懂 基本过程就完成一大半了 2 其次 由于用 java 写 本身没有学过用 java 写这样的列表和队列的问题 因此许多问题通过上网 查找资料 才完成 确实花费了很大功夫 但是上机实习后 对 arraylist 的使用有了更广泛的认识 对基于结点的聚类算法也真正有了实际的体会 移动数据库课程设计移动数据库课程设计 中国地质大学 武汉 10 同时也认识到自己确实有很多不足 在遇到不懂的知识时解决问题的能力有待提高 最后 谢谢老师的 题目和上机实习时的辅导 给予了自己很大的帮助 第六章第六章源代码源代码 Nodebased java文件文件 package designtest import java io IOException import java util public class nodebased private final static int e 2 阈值阈值 private static List pointinit new ArrayList private static List List List resultlist new ArrayList List List private static List pointsList new ArrayList 存储原始样本点 存储原始样本点 pointsList中存放一堆中存放一堆Point private static List List resultList new ArrayList List 存存 储最后的聚类结果储最后的聚类结果 resultList中存放一堆中存放一堆List列表 列表 List中用存放一堆中用存放一堆Point对象对象 private static void init throws IOException pointinit Funtion getPointsList1 pointsList Funtion getPointsList2 for int index 0 index pointinit size index List tmpLst new ArrayList Point p pointinit get index tmpLst Funtion KeyPoint pointsList p e if tmpLst null resultList add tmpLst int length resultList size System out println lenght length for int i 0 i length i for int j 0 j length j if i j if Funtion mergeList resultList get i resultList get j 移动数据库课程设计移动数据库课程设计 中国地质大学 武汉 11 resultList get j clear private static void applyDbscan throws IOException pointsList Utility getPointsList for int index 0 index pointsList size index System out println index index List tmpLst new ArrayList Point p pointsList get index if p isClassed continue tmpLst Utility isKeyPoint pointsList p e minp if tmpLst null resultList add tmpLst int length resultList size System out println length length for int i 0 i length i for int j 0 j length j if i j if Utility mergeList resultList get i resultList get j resultList get j clear public static void main String args try init Funtion display resultList catch IOException e e printStackTrace 移动数据库课程设计移动数据库课程设计 中国地质大学 武汉 12 Function java package designtest import java io BufferedReader import java io FileReader import java io IOException import java util public class Funtion 计算距离计算距离 public static double getDistance Point p Point q int dx p getX q getX int dy p getY q getY double distance 10000 if p getX q getX distance Math sqrt dz dz else if p getX q getX int dz q getZ distance Math sqrt dz dz return distance else if p getX q getY distance Math sqrt dz dz return distance double distance Math sqrt dx dx dy dy return distance public static List KeyPoint List lst Point p int e List tmpLst new ArrayList for Iterator it lst iterator it hasNext Point q it next if getDistance p q minp p setKey true return tmpLst return null 合并两个链表 前提是合并两个链表 前提是b中的核心点包含在中的核心点包含在a中中 public static boolean mergeList List a List b boolean merge false if a null b null return false for Iterator it1 b iterator it1 hasNext 迭代器模式 迭代器模式 hasNext 是否存在下一个数据 是否存在下一个数据 Point p it1 next next 返回当前值返回当前值 System out println p print for int index 0 index b size index System out println index index Point p b get index if p isKey break if merge for int index 0 index b size index if a contains b get index a add b get index return merge 获取文本中的样本点集合获取文本中的样本点集合 public static List getPointsList1 throws IOException 移动数据库课程设计移动数据库课程设计 中国地质大学 武汉 14 List lst1 new ArrayList String txtPath points txt BufferedReader br new BufferedReader new FileReader points txt String str while str br readLine null for Iterator it1 lst1 iterator it1 hasNext 迭代器模式 迭代器模式 hasNext 是否存在下一个数据 是否存在下一个数据 Point p it1 next next 返回当前值返回当前值 System out println p print br close return lst1 public static List getPointsList2 throws IOException List lst2 new ArrayList String txtPath points txt BufferedReader br new BufferedReader new FileReader points1 txt String str while str br readLine null for Iterator it1 lst2 iterator it1 h