数据挖掘报告

1 摘要 数据挖掘技术可以在浩瀚的数据中进行统计 分析 综合 推理 发现数 据内部关联 并作出预测 提供数据信息 为决策提供辅助支持 目前 数据 挖掘技术已经广泛应用在商业领域 同样 可以将数据挖掘技术与国家教育项 目相结合 对项目中的各类数据信息进行挖掘分析 提取隐藏的数据信息 为 项目开发部门提供决策依据 进一步提高项目的科学性和高效性 本文结合自身参与教育部指定的关于城市集群竞争力项目的实践经验 分 析数据挖掘技术在国家教育项目中应用的可行性 并以此为例 采用 JAVA 语言 编写实现 KNN 算法 在项目实施方案中 以城市集群的数据为基础 完成数据挖掘的全过程 确定数据挖掘的对象和目标 数据清理和预处理 对某个指标缺失的数据引入 神经网络方法进行预测填补 对缺失较多的数据引入对比和类比的方法进行预 测填补 采用 KNN 算法实现数据分类 形成指标体系 利用数据挖掘的结果 通过对指标数据的分析 预测决定城市集群竞争力的主要因素 从而为今后城 市集群的发展方向和职能定位提供参考 为城镇体系的总体发展指明方向 为 提高我国城市集群整体经济实力和综合竞争力提供一些有益的建议和对策 促 进成熟集群向一体化方向发展 同时也可以为国内其他城市集群的发展提供给 一些有益的参考 关键词 数据挖掘 KNN 算法 数据分类 JAVA 城市集群竞争力 2 目录 摘要 1 目录 2 第一章绪论 2 1 1 研究背景和研究意义 2 第二章 数据挖掘技术的研究 4 2 12 1 数据挖掘的功能数据挖掘的功能 4 4 2 22 2 数据挖掘的对象数据挖掘的对象 6 6 2 32 3 数据挖掘的过程数据挖掘的过程 7 7 2 42 4 数据挖掘算法数据挖掘算法 9 9 第三章 KNN 算法介绍与实现 10 3 13 1 KNNKNN 算法介绍算法介绍 1010 3 23 2 KNNKNN 算法的算法的 JAVAJAVA 实现实现 1212 第四章 总结 17 3 第一章 绪论 1 1 研究背景和研究意义 1 研究背景 随着信息社会的发展 计算机技术和数据库管理系统的应用 产生了大量的 数据信息 数据库存储的数据量也在日益增长 但对于此数据却是 数据丰 富 信息贫乏 人们迫切需要从此类数据中获取信息 即将此类数据转换成 有用的信息和知识 并且被广泛应用于事物管理 信息检索和数据分析中 这 种需求导致了对数据分析工具的需求扩大 数据挖掘技术就是在此信息技术发 展下产生的 数据挖掘 Data Mining 就是从大量的 不完全的 有噪声的 模糊的 随机的实际应用数据中 提取隐含在其中的 人们事先不知道的 但又是潜在 有用的信息和知识的过程 数据挖掘涉及多学科技术的集成 包括数据库技术 统计学 机器学习 高性能计算 模式识别 神经网络 数据可视化 信息检索 图像与信号处理 和空间数据分析等 数据挖掘技术在商业等赢利性领域中已经取得了广泛的应用 但在高校 政府等非赢利组织的应用并不广泛 结合自身参与项目的经验 利用数据挖掘 技术快速而又准确的从浩瀚的数据资源中提取出所需信息 从而在实际应用中 将管理信息转化为可供决策使用的知识 这不仅具有理论价值 更具有极大的 现实意义 2 研究意义 本文利用数据挖掘的结果 通过对指标数据的分析 预测决定城市集群竞 争力的主要因素 从而为今后城市集群的发展方向和职能定位提供参考 为城 镇体系的总体发展指明方向 为提高我国城市集群整体经济实力和综合竞争力 提供一些有益的建议和对策 促进成熟集群向一体化方向发展 同时也可以为 国内其他城市集群的发展提供给一些有益的参考 4 第二章 数据挖掘技术的研究 2 1 数据挖掘的功能 数据挖掘的功能用于指定数据挖掘任务中要找的模式类型 数据挖掘任务 一般分为两类 描述和预测 描述性挖掘任务记录数据库中数据的一般特性 预测性挖掘任务在当前数据上进行推断以及预测 数据挖掘功能以及他们可以发现的模式类型为 一 概念描述 数据可以与类或概念相关联 用汇总的 简洁的 精确的方式描述每个类 或概念 概念描述就是产生数据特征化和比较的描述 数据特征化是目标类数据的一般特征或特性的汇总 通常 用户指定类的 数据通过数据库查询收集 数据特征的输出可以用多种形式提供 包括饼图 条图 曲线 多维数据立方体和包括交叉表在内的多维表 结果描述也可以用 概化关系或规则形式 数据区分是将目标类对象的一般特性与一个或多个对比类对象的一般特性 比较 目标类和对比类由用户指定 而对应的数据通过数据库查询检索 输出 的形式类似于特征描述 但区分描述应当包括比较度量 帮助区分目标类和对 比类 用规则表示的区分描述成为区分规则 二 关联分析 关联分析发现关联规则 这些规则展示属性值频繁地在给定数据集中一起 出 现的条件 即两个或两个以上数据项的取值之间存在某种规律性 就称为关联 可以建立起这些数据项的关联规则 关联分析广泛用于购物篮或事务数据分析 包含单个谓词的关联规则称作单维关联规则 在多个属性或谓词之间的关联 采用多维数据库 每个属性称为一维 则此规则称作多维关联规则 数据关联是数据库中存在的一类重要的 可被发现的知识 它反映一个事 5 件和其他事件之间依赖或关联 如果两项或多项属性之问存在关联 那么其中 一项的属性值就可以依据其他属性值进行预测 在大型数据库中 关联规则可 以产生很多 这就需要进行筛选 一般用 支持度 和 可信度 两个阈值来淘 汰那些无用的关联规则 三 分类和预测 分类是指找出描述并区分数据类或概念的模型 或函数 以便能够使用模 型预测类标记未知的对象类 分类是数据挖掘中应用得最多的任务 分类就是 找出一个类别的概念描述 并用这种描述来构造模型 可采用多种形式如分类 规则 判定树 数学公式或神经网络 等导出模型对训练数据集 即其类标记已 知的数据对象 的分析 分类可以用来预测数据对象的类标记 然而 在某些应用中 人们可能希 望预测某些空缺的或不知道的数据值 而不是类标记 当被预测的值是数值数 据时 通常称之为预测 预测是利用历史数据找出变化规律 建立模型 并由 此模型对未来数据的种类及特征进行预测 典型的预测方法是回归分析 即利用大量的历史数据 以时间为变量建立 线性或非线性回归方程 预测时 只要输入任意的时间值 通过回归方程就可 求出该时间的状态 尽管预测可以涉及数据值预测和类标记预测 通常预测限 于值预测 并因此不同于分类 预测也包含基于可用数据的分布趋势识别 在 分类和预测之前可能需要进行相关分析 它试图识别对于分类和预测无用的属 性并排除 四 聚类分析 与分类和预测不同 聚类 clustering 分析数据对象 而不考虑已知的类标 记 一般情况下 训练数据中不提供类标记 因为不知道从何开始 聚类 可 以用于产生这种标记 对象根据最大化类内的相似性 最小化类问的相似性的 原则进行聚类或分组 即对象的簇 聚类 这样形成 使得在一个簇中的对象具 有很高的相似性 而与其他簇中的对象很不相似 所形成的每个簇可以看作一 个对象类 由它可以导出规则 聚类也便于分类编制 将观察到的内容组织成 类分层结构 把类似的事件组织在一起 五 异常分析 6 数据中可能包含一些数据对象 他们与数据的一般行为或模型不一致 这些 数据对象是异常的 大部分数据挖掘方法将异常数据视为噪声而丢弃 异常分 析就是探测和分析那些不符合数据的一般模型的数据对象 并对其建模 然而 在一些应用中 如欺骗检测 罕见的事件可能比正常出现的那些更有趣 称作 孤立点挖掘 六 演变分析 数据演变分析描述行为随时间变化的对象的规律或趋势 并对其建模 尽管 这可能包括时间相关数据的特征化 区分 关联 分类或聚类 这类分析的不 同特点包括时间序列数据分析 序列或周期模式匹配和基于类似性的数据分析 2 2 数据挖掘的对象 关系数据库系统广泛地用于商务应用 随着数据库技术的发展 出现了各 种高级数据库系统 以适应新的数据库应用需要 新的数据库应用包括处理空间数据 如地图 工程设计数据 如建筑设计 系统部件 集成电路 超文本和多媒体数据 包括文本 影象 图象和声音数 据 时间相关的数据 如历史数据或股票交易数据 和 WWW 通过 Internet 可以 使巨大的 广泛分布的信息存储 依据不同的数据类型 数据挖掘的对象包括 以下几种 一 关系数据库 当数据挖掘用于关系数据库时 可以进一步搜索趋势或数据模式 例如 数据挖掘系统可以分析顾客数据 根据顾客的收人 年龄和以前的信用信息预 测新顾客的信用风险 数据挖掘系统也可以检测偏差 如与以前的年份相比 哪种商品的销售出入预料 这种偏差可以进一步考察 例如 包装是否有变化 或价格是否大幅度提高 关系数据库是数据挖掘最流行的 最丰富的数据源 因此它是我们数据挖掘研究的主要数据形式 二 数据仓库 一般 数据仓库用多维数据库结构建模 数据仓库的实际物理结构可以是 7 关系数据存储或多维数据立方体 它提供数据的多维视图 并允许预计算和快 速访问汇总的数据 通过提供多维数据视图和汇总数据的预计算 数据仓库非 常适合联机分析处理 OLAP OLAP 允许在不同的抽象层提供数据 同时允许用 户在不同的汇总级别观察数据 三 事务数据库 一般地说 事务数据库由一个文件组成 其中每个记录代表一个事务 事 物数据库可有一些相关联的附加表 事务可以存放在表中 由于大部分关系数 据库系统不支持嵌套关系结构 而记录数据为一个嵌套关系 使用事务数据库 通常存放在一表格式的展开文件中 或展开到类似的标准关系中 当需要识别 频繁的事物之间的关联时即可采用通过事务数据的数据挖掘系统 四 文本数据库 文本数据库是包含对象文字描述的数据库 通常 这种词描述不是简单的 关键词 而是正片文档 文本数据库可能是高度非结构化的 如 www 页 半结 构化的 如 email 或结构化的 如图书馆数据库 文本数据库上的数据挖掘可 以发现对象类的一般描述 以及关键字或内容的关联和文本对象的聚类行为 为做到这一点 需要将标准的数据挖掘技术与信息检索技术和文本数据特有的 层次构造 如字典和辞典 以及面向学科的 如化学 医学 法律或经济 术语 分类系统集成在一起 五 多媒体数据库 多媒体数据库存放图象 音频和视频数据 它们用于基于图象内容的检索 声音传递 视频点播 www 和识别口语命令的基于语音的用户界面等方面 多 媒体数据库必须支持大对象 如视频这样的数据对象可能需要兆字节级的存储 还需要特殊的存储和搜索技术 因为视频和音频数据需要以稳定的 预先确定 的速率实时检索 防止图象或声音间断和系统缓冲区溢出 因此这种数据称为 连续媒体数据 对于多媒体数据库挖掘 需要将存储和搜索技术与标准的数据挖掘方法集 成在一起 有前途的方法包括构造多媒体数据立方体 多媒体数据的多特征提 取和基于相似性的模式匹配 8 2 3 数据挖掘的过程 数据挖掘的过程实际是一个数据库知识的发现过程 依据发现过程可以分 为以下几个步骤执行 一 确定挖掘目标 清晰明确的定义出问题 认清数据挖掘的最终业务目标 一般来说 目标 可以是关联规则发现 数据分类 回归 聚类 数据汇总 概念描述 相关分 析建模或误差检测及预测或综合应用等 二 数据准备 在数据准备阶段又可以进一步细分为三步 数据集成 数据选择和预处理 数据变换和压缩 1 数据集成 选择一个数据集或针对一个变量或数据样本的子集 在这个 集合上进行挖掘 此时应考虑如何选取同类的数据 考虑过程中的动态情况和 变化 采样策略 样本是否足够 自由度和其他一些问题 2 数据选择和预处理 考虑如何正确去除噪声模型或解决噪声问题 决定 采取何种策略去解决丢失的数据或数据库设计不完善带来的问题 以及解决时 间序列信息和正确标准化等问题 3 数据变换和压缩 根据任务的目标 查找有用的特性来表示数据 利用 空间压缩或变换的方法来减少要考虑的有效数目或找到数据的不变表示 一般 方法把数据投影到某个空间上以利于问题解决 三 数据挖掘 1 选择数据挖掘方法 根据数据库知识发现过程的目标 选择相应的数据 挖掘方法 如统计分析 机器学习 模式识别方法和人工神经元方法等 2 选择数据挖掘算法 选择用来查找模式或符合数据的模型的算法 确定 合适的模型和参数 另外 数据挖掘方法必须和目标相匹配 3 数据挖掘 查找感兴趣的模式 模式一般表示为一种特殊的形式或一套 表达式 如关联规则 分类规则或分类树 回归结构和聚类集等 四 评估与表示 9 1 结果表达 尽量直观地表示挖掘结果 便于用户理解和使用 可利用可 视化方法表示为图表等形式 2 结果评价 筛选和评价挖掘结果中的有用部分 查找可接受的结果 可 定义兴趣度指标 考虑结果的正确度 新颖度 有用性和简单性 把知识从输 出中过滤出来 利用可视化方法帮助用户决定所提取知识的有效性和对基本的 数据或现象做出结论 3 知识巩固 把挖掘出的知识结合到执行系统中 了解这些知识的作用或 证明这些知识 用预选知识且可信的知识来检查和验证所挖掘的知识 解决可 能存在的矛盾 也可以只是简单地记录所挖掘出的知识 并把它报告给用户 由用户进一步分析 2 4 数据挖掘算法 数据挖掘的核心部分就是数据挖掘算法 设计数据挖掘算法的方法很多 不同的方法服务于不同的目标 每种方法都有自己的优缺点 因此 一个功能 全面的数据挖掘系统应该综合利用各种不同的方法 常用的数据挖掘算法主要 包括 1 决策树方法 利用信息论中的信息增益寻找数据库中具有最大信息量的 字段 建立决策树的一个结点 再根据字段的不同取值建立树的分支 在每个 分 支子集中重复建立树的下层结点和分支的过程 2 神经网络方法 是一组连接的输入 输出单元 其中每个连接都与一个 权相联 在学习阶段 通过调整神经网络的权 使得能够预测输入样本的正确 类标号来学习 由于单元之间的连接 神经网络学习又称连接者学习 3 遗传算法 是一种优化技术 试图结合自然进化的思想 基于达尔文的 进化论中基因重组 突变和自然选择等概念 利用生物进化的一系列概念进行 问题的搜索 最终达到优化的目的 4 KNN 算法 是一种理论上比较成熟的分类和回归算法 该方法定类决 策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别 10 5 粗糙集方法 可以用于分类 发现不准确数据或噪声数据内在的结构联 系 它用于离散值属性 粗糙集理论基于给定训练数据内部的等价类的建立 形成等价类的所有数据样本是不加区分的 即对于描述数据的属性 这些样本 是等 价的 6 模糊集方法 利用模糊集合理论 对实际问题进行模糊判断 模糊决策 模糊模式识别等 对于数据挖掘系统进行分类 模糊逻辑是有用的 它提供了 在 高抽象层处理的便利 第三章 KNN 算法介绍与实现 3 1 KNN 算法介绍 通过参与城市集群竞争力项目的实践 结合自己所学的 JAVA 语言 为了更 好的利用 KNN 算法实现项目数据的分类和预测 采取了用 JAVA 语言编写和改进 KNN 算法的方式 1 KNN 的优缺点 优点 原理简单 实现起来比较方便 支持增量学习 能对超多边形的复 杂决策空间建模 缺点 计算开销大 需要有效的存储技术和并行硬件的支撑 2 KNN 算法原理 基于类比学习 通过比较训练元组和测试元组的相似度来学习 将训练元 组和测试元组看作是 n 维 若元组有 n 的属性 空间内的点 给定一条测试元 组 搜索 n 维空间 找出与测试元组最相近的 k 个点 即训练元组 最后取 这 k 个点中的多数类作为测试元组的类别 11 相近的度量方法 用空间内两个点的距离来度量 距离越大 表示两个点 越不相似 距离的选择 可采用欧几里得距离 曼哈顿距离或其它距离度量 多采用欧几里得距离 3 KNN 算法中的细节处理 数值属性规范化 将数值属性规范到 0 1 区间以便于计算 也可防止大 数值型属性对分类的主导作用 可选的方法有 v v vmin vmax vmin 当然也可以采用其它的规范化方法 比较的属性是分类类型而不是数值类型的 同则差为 0 异则差为 1 有 时候可以作更为精确的处理 比如黑色与白色的差肯定要大于灰色与白 色的差 缺失值的处理 取最大的可能差 对于分类属性 如果属性 A 的一个或 两个对应值丢失 则取差值为 1 如果 A 是数值属性 若两个比较的元 组 A 属性值均缺失 则取差值为 1 若只有一个缺失 另一个值为 v 则 取差值为 1 v 和 0 v 中的最大值 确定 K 的值 通过实验确定 进行若干次实验 取分类误差率最小的 k 值 对噪声数据或不相关属性的处理 对属性赋予相关性权重 w w 越大说明 属性对分类的影响越相关 对噪声数据可以将所在的元组直接 cut 掉 4 KNN 算法流程 准备数据 对数据进行预处理 选用合适的数据结构存储训练数据和测试元组 设定参数 如 k 维护一个大小为 k 的的按距离由大到小的优先级队列 用于存储最近邻 训练元组 12 随机从训练元组中选取 k 个元组作为初始的最近邻元组 分别计算测试 元组到这 k 个元组的距离 将训练元组标号和距离存入优先级队列 遍历训练元组集 计算当前训练元组与测试元组的距离 将所得距离 L 与优先级队列中的最大距离 Lmax 进行比较 若 L Lmax 则舍弃该元组 遍历下一个元组 若 L Lmax 删除优先级队列中最大距离的元组 将 当前训练元组存入优先级队列 遍历完毕 计算优先级队列中 k 个元组的多数类 并将其作为测试元组 的类别 测试元组集测试完毕后计算误差率 继续设定不同的 k 值重新进行训练 最后取误差率最小的 k 值 5 KNN 算法的改进策略 将存储的训练元组预先排序并安排在搜索树中 如何排序有待研究 并行实现 部分距离计算 取 n 个属性的 子集 计算出部分距离 若超过设定的 阈值则停止对当前元组作进一步计算 转向下一个元组 剪枝或精简 删除证明是 无用的 元组 3 2 KNN 算法的 JAVA 实现 1 JAVA 代码 package KNN KNN 结点类 用来存储最近邻的 k 个元组相关的信息 public class KNNNode private int index 元组标号 private double distance 与测试元组的距离 private String c 所属类别 public KNNNode int index double distance String c super this index index this distance distance this c c 13 public int getIndex return index public void setIndex int index this index index public double getDistance return distance public void setDistance double distance this distance distance public String getC return c public void setC String c this c c package KNN KNN 算法主体类 import java util ArrayList import java util Comparator import java util HashMap import java util List import java util Map import java util PriorityQueue public class KNN 设置优先级队列的比较函数 距离越大 优先级越高 private Comparator comparator new Comparator public int compare KNNNode o1 KNNNode o2 if o1 getDistance o2 getDistance return 1 else return 0 获取 K 个不同的随机数 14 param k 随机数的个数 param max 随机数最大的范围 return 生成的随机数数组 public List getRandKNum int k int max List rand new ArrayList k for int i 0 i k i int temp int Math random max if rand contains temp rand add temp else i return rand 计算测试元组与训练元组之前的距离 param d1 测试元组 param d2 训练元组 return 距离值 public double calDistance List d1 List d2 double distance 0 00 for int i 0 i d1 size i distance d1 get i d2 get i d1 get i d2 get i return distance 执行 KNN 算法 获取测试元组的类别 param datas 训练数据集 param testData 测试元组 param k 设定的 K 值 return 测试元组的类别 public String knn List List datas List testData int k PriorityQueue pq new PriorityQueue k comparator List randNum getRandKNum k datas size for int i 0 i k i int index randNum get i List currData datas get index String c currData get currData size 1 toString KNNNode node new KNNNode index calDistance testData currData 15 c pq add node for int i 0 i datas size i List t datas get i double distance calDistance testData t KNNNode top pq peek if top getDistance distance pq remove pq add new KNNNode i distance t get t size 1 toString return getMostClass pq 获取所得到的 k 个最近邻元组的多数类 param pq 存储 k 个最近近邻元组的优先级队列 return 多数类的名称 private String getMostClass PriorityQueue pq Map classCount new HashMap for int i 0 i pq size i KNNNode node pq remove String c node getC if classCount containsKey c classCount put c classCount get c 1 else classCount put c 1 int maxIndex 1 int maxCount 0 Object classes classCount keySet toArray for int i 0 i maxCount maxIndex i maxCount classCount get classes i return classes maxIndex toString 16 package KNN KNN 算法测试类 import java io BufferedReader import java io File import java io FileReader import java util ArrayList import java util List public class TestKNN 从数据文件中读取数据 param datas 存储数据的集合对象 param path 数据文件的路径 public void read List List datas String path try BufferedReader br new BufferedReader new FileReader new File path String data br readLine List l null while data null String t data split l new ArrayList for int i 0 i t length i l add Double parseDouble t i datas add l data br readLine catch Exception e e printStackTrace 程序执行入口 public static void main String args TestKNN t new TestKNN String datafile new File getAbsolutePath File se