（计算机软件与理论专业论文）基于嵌入式移动数据库的数据挖掘.pdf

基丁嵌入式移动数据库的数据挖掘 中文摘要 数据挖掘就是从大量的数据中提取或者 挖掘 知识 因此数据挖掘又被称 为数据库中的知识发现 它是一个涉及多学科领域的新兴学科 并随着这些学科 的发展而不断发展 随着p d a 手机 便携式和小巧的卡等移动计算设备在我 们的日常生活中扮演着越来越重要的作用 带有合理计算和存储容量的移动设备 的出现以及嵌入式数据库的发展开辟了高级数据挖掘和密集计算移动应用程序 的新时代 这就为挖掘基于移动设备的潜入式数据库提供了可能 这是一个实时 的嵌入式的数据挖掘环境 它能分析嵌入式数据库中的数据 并为用户的决策提 出建议 金融数据的实时分析 过程控制 规章的遵守 安全应用这些都是基于 嵌入式数据库的数据挖掘可以应用的领域 关联分析是传统数据挖掘的一个功能 它用于发现关联规则 关联规则描述了 给定数据集的项之间的有趣联系 目前 已经提出了许多挖掘关联规则的算法 其中最著名的是a p r i o r i 算法及其变形 这些传统的算法大多已经在传统的固定 大型数据库上得到了实现 但是基本上还没有在嵌入式移动数据库上得到实现 在嵌入式移动数据库上的实现应该考虑到嵌入式移动数据库的一些自身特点 为 了解决这些问题 本文介绍了关联分析在嵌入式移动数据库上的实现过程 本文首先介绍了数据挖掘的基本概念 存在问题及发展方向 其次介绍了嵌 入式数据库的基本概念 特点 发展 并比较了几种主要嵌入式移动数据库的特 点 然后介绍了传统的关联分析的基本概念 分类及一些常见的算法思想 其中 着重介绍了挖掘关联规则的经典算法 a d r i o r i 算法的基本思想和前人对它进 行的改进 随后介绍 为了把a p r i o r i 算法应用于嵌入式移动挖掘中 我对它所 进行的一些改进 最后介绍了一个自主设计实现的基于嵌入式移动数据库的数据 挖掘系统 它的数据挖掘引擎就是采用了由我改进的a p r i o r i 算法 关键词 数据挖掘 嵌入式数据库 关联规则 关联分析 权 基于嵌入式移动数据库的数据挖掘 a b s t r a c t d a t am i n i n gi st oe x t r a c to rm i n ek n o w l e d g ef r o ml a r g ea m o u n to f d a t a s oi ti s a l s oc a l l e dk n o w l e d g ed i s c o v e r yi nd a t a b a s e i ti san e ws u b j e c tt h a ti n v o l v e s al o to f s u b j e c t s a n d d e v e l o p s w i t ht h e s e s u b j e c t s w i t h p d a m o b i l ep h o n e p a c k e t p ca n dc a r dc o m p u t i n ge q u i p m e n tp l a yal o to fr o l ei no u rd a y l yl i f e t h ee q u i p m e n t w i t hr e a s o n a b l e c o m p u t i n ga n d s t o r e d c a p a b i l i t y t h ed e v e l o p m e n t o fe m b e d d e d m o b i l ed a t a b a s es t a r t a g e o fa d v a n c e dd a t a m i n i n g d e n s i t yc o m p u t i n g m o b i l e a p p l i c a t i o n t h e s e m a k ed a t a m i n i n g b a s e de m b e d d e dm o b i l ed a t a b a s eb e c o m e p o s s i b l e t h i si sr e a l t i m ee m b e d d e dd a t am i n i n ge n v i r o n m e n t i tc a na n a l y s i sd a t ai n e m b e d d e dd a t a b a s ea n dg i v eu s e ra d v i s et om a k ed e c i s i o n a n a l y s i so fr e a l t i m e f i n a n c i a ld a t a p r o c e s sc o n t r o l r u l eo b s e r v a n c e s e c u r i t ya p p l i c a t i o na r ef i e l d si nw h i c h d a t am i n i b a s e de m b e d d e dm o b i l ed a t a b a s ec a nb eu s e d a s s o c i a t i o na n a l y s i si saf u n c t i o no ft r a d i t i o n a ld a t am i n i n gs y s t e m i ti st of i n d a s s o c i a t i o nr u l e s a s s o c i a t i o nr u l e sd e s c r i b et h ei n t e r e s t i n gr e l a t i o n so ft h ei t e m si n t h eg i v e nd a t as e t a tp r e s e n t l o t so fa l g o r i t h m sf o rm i n i n ga s s o c i a t i o nr u l e sh a v e b e e n b r o u g h t f o r w a r d t h cm o s tf a m o u s a l g o r i t h m s a r e a p r i o r i a n di t s t r a n s f i g u r a t i o n t h e s e c o n d i t i o n a l a l g o r i t h m s a r ea l m o s t i m p l e m e n t e d i n h u g e d a t a b a s e b u ti sn e a r l yi m p l e m e n t e di ne m b e d d e dm o b i l ed a t a b s e t h er e a l i z a t i o ni n e m b e d d e dm o b i l ed a t a b a s es h o u l dc o n s i d e r e dt h ec h a r a c t e r i s t i co f e m b e d d e dm o b i l e d a t a b a s e i no r d e rt os o l v et h eq u e s t i o n t h i sp a p e ri n t r o d u c ep r o c e s so fr e a l i z a t i o no f a s s o c i a t i o ni ne m b e d d e dm o b i l ed a t a b a s e f i r s t l yt h i sp a p e ri n t r o d u c et h eb a s i cc o n c e p t q u e s t i o n d e v e l o p m e n td i r e c t i o no f d a t am i n i n g s e c o n d l y i ti n t r o d u c et h eb a s i cc o n c e p l c h a r a c t e r i s t i c t h ed e v e l o p m e n t o fe m b e d d e dd a t a b a s e ia l s o c o m p a r et h e c h a r a c t e r i s t i co fp r i m a r ye m b e d d e d d a t a b a s e t h i r d l y ii n t r o d u c e dt h eb a s i cc o n c e p t c l a s s i f i c a t i o na n ds o m ef a m i l i a r a l g o r i t h mi d e a so f a s s o c i a t i o na n a l y s i s t h ei d e ao ft h ec l a s s i c a la l g o r i t h ma p r i o r ii s t h e e m p h a s i sa n ds o m e o fi t st r a n s f o r m a t i v ea l g o r i t h m sm a d e b y f o m e ra r ci n t r o d u c e d t o i m p r o v e t h e e f f i c i e n c y t h e n ii n t r o d u c es o m er e f o r m a t i o nf o r a p r i o r i a l g o r i t h m sm a d eb ym e i no r d e rt oa p p l l i c a t ea p r i o r ii n t od a t am i n i n gs y s t e mb a s e d b ye m b e d d e dm o b i l ed a t a b a s e i nt h ee n d ii n t r o d u c ead a t am i n i n gs y s t e mb a s e db y e m b e d d e dm o b i l ed a t a b a s ec o n s t r u c t e db ym e t h em i n i n ge n g i n eo f t h a ts y s t e ma d o p t t h e a p r i o r ia l g o r i t h m sr e f o r m e db y m e k e y w o r d s d a t am i n i n g e m b e d d e dd a t a b a s e a s s o c i a t i o nr u l e s a s s o c i a t i o na n a l y s i s w e i g h t 一u 基于嵌入式移动数据库的数据挖艄 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果 据我所知 除了文中特别加以标注和致谢的 地方外 论文中不包含其他人已经发表或撰写过的研究成果 也 不包含为获得电子科技大学或其它教育机构的学位或证书而使用 过的材料 与我一同工作的同志对本研究所傲的任何贡献均已在 论文中作了明确的说明并表示谢意 签名 莲注l 乏冱 日期 2 0 0 4 年2 月2 5 日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留 使用学位论文 的规定 有权保留并向国家有关部门或机构送交论文的复印件和磁 盘 允许论文被查阅和借阅 本人授权电子科技大学可以将学位论文 的全部或部分内容镇入有关数据库进行检索 可l 置采用影印 缩印或 扫描等复制手段保存 汇编学位论文 保密的学位论文在解密后应遵守此规定 签名 基于嵌入式移动数据库的数据挖捌 引言 在二十世纪后半段 信息技术以日新月异的速度飞速发展 由此带动了数据 库技术的迅猛发展 各种存储着大量信息的数据库不断出现 这些数据库大多容 量巨大 需要有有效的数据处理技术对它们进行分析处理 以从中得到人们想要 的信息 数据挖掘技术就是一门重要的数据处理技术 p d a 手机 便携式和小巧的卡等移动计算设备在我们的日常生活中扮演着 越来越重要的作用 带有合理计算和存储容量的移动设备不断出现 无线通信技 术的飞速发展使无线传输更稳定更快速 这些都使基于嵌入式数据库的数据挖掘 的出现成为可能和必要 基于嵌入式数据库的数据挖掘可以帮助人们实时的完成 许多有用的工作 做出更加明智的决策 目前 基于嵌入式数据库的数据挖掘的 技术正处在一个不断发展的过程中 有着很好的发展前景 同时也有很多未知的 问题需要解决 经过一段时间的资料查阅 理论研究 经过吴跃教授的精心指导与同教研室 同学的多次讨论后 我对基于嵌入式数据库的数据挖掘这一技术有了比较多的了 解和掌握 并形成了自己的一些心得 在总结这些心得的基础上 写下了这篇论 文 作为我的毕业论文 本文共分四章 具体内容如下 第一章 数据挖掘 本章首先介绍了数据挖掘的产生 然后介绍了数据挖掘 的基本概念 应用范围和功能 最后介绍了数据挖掘面l 临的主要问题及其发展方 向 第二章 嵌入式数据库 本章首先介绍了嵌入式数据库的产生 然后介绍了 嵌入式数据库的基本概念 应用范围 功能和特点 总结了它和普通数据库的不 同 然后介绍了当今流行的嵌入式数据库 以及各自的特点 优势和劣势 其中 着重介绍了小金灵嵌入式移动数据库 以及说明为什么要选择 小金灵 嵌入式移 动数据库做为平台的原因 第三章 关联分析 本章首先从一个示例出发 介绍了关联规则的基本概念 然后讨论了关联规则的分类 最后详细介绍了挖掘关联规则的常用算法的基本思 想 并讨论了提高关联规则挖掘效率一些方法 第四章 基于 小金灵 嵌入式移动数据库的数据挖掘系统 本章主要介绍 了一个自主基于嵌入式移动数据库的数据挖掘的原型 详细的讨论了它的需求 设计的思想 结构框架 实现步骤 其中也详细的叙述了为什么要选片 i 小金灵 基于嵌入式移动数据库的数据挖拥i 嵌入式数据库作为平台 还介绍了为了把a p r i o r i 算法应用到嵌入式移动挖掘中 我对它进行的改进 在本章的最后还得出了基于 小金灵 嵌入式移动数掘库的 运用关联分析方法的数据挖掘结果 并对该结果进行了分析 1 1 数据挖掘的产生 基于嵌入式移动数据库的数据挖掘 第一章数据挖掘 近年来 随着数据库技术的不断发展 存储在数据库中的信息量也在大量增 加 怎样从一大堆随机的数据中发掘出一些有价值的信息逐渐成为一个重要的课 题 由此带动了数据挖掘技术的产生和飞速发展 数据的丰富带来了对强有力的数据分析工具的需求 大量的数据被描述为 数据丰富 但信息贫乏 因为存储在大型数据库中的数据可以用海量来形容 理解这些数据中隐含的知识己经超出了人力的范围 没有强有力的分析工具 这 些数据就变成了 数据坟墓 很难再访问的数据档案 于是 数据挖掘技 术应运而生 利用数据挖掘工具进行数据分析 可以发现重要的数据模式 对商 务决策 知识库 科学和医学研究作出了重大贡献 数据和信息之间的鸿沟要求 系统地开发数据挖掘工具 将数据的 坟墓 转变成知识的 金块 1 2 数据挖掘的一般性讨论 1 2 1 数据挖掘的基本概念 简单地说 数据挖掘就是从大量的数据中提取或者 挖掘 知识 在许多场 合下 数据挖掘又被称为数据库中的知识发现 k n o w l e d g ed i s c o v e r y i n d a t a b a s e 简称k d d 但是 更科学的说法是将数据挖掘视为数据库知识发现 的一个基本步骤 在这种情况下 数据库的知识发现过程由以下几个步骤组成 1 数据清理 消除噪声或者不一致数据 2 数据集成 多种数据源可以组合在一起 它和数据清理一起被视为预 处理步骤 结果数据存放在数据仓库中 3 数据选择 从数据库中检索与分析任务相关的数据 4 数据变换 将数据变换或统一成适合挖掘的形式 如通过汇总或聚集 操作 在有些场合下 数据变换在数据选择过程之前进行 特别是在数据仓库的 情况下 5 数据挖掘 使用智能方法提取数据模式 6 模式评估 根据某种兴趣度度量 识别表示知识的真正有趣的模式 7 知识表示 使用可视化和知识表示技术 向用户提供挖掘的知识 尽管将数据挖掘视为数据库知识发现过程的一个基本步骤更为科学 但是在 产业界 媒体和数据库研究界 将数据挖掘赢接当作数据库中的知识发现更为流 丛于嵌入式移动数据库的数据挖掘 行 因此数据挖掘有了一个更加广泛的概念 数据挖掘是从存放在数据库 数据 仓库或其他信息库中的大量数据中挖掘有趣知识的过程 基于这种观点 一个典 型的数据挖掘系统可以由以下几个主要成分组成 数据库 数据仓库或其他信息库 这是一个或一组数据库 数据仓库 电 子表格或其他类型的信息库 可以在数据上进行数据清理和集成 数据库或数据仓库服务器 根据用户的数据挖掘请求 数据库或数据仓库 服务器负责提取相关数据 知识库 用于指导搜索或评估结果模式的兴趣度 数据挖掘引擎 数据挖掘系统基本的部分 由一组功能模块组成 用于特 征化 关联 分类 聚类分析以及演变和偏差分析 模式评估模块 通常 此成分使用兴趣度度量 并与数据挖掘模块交互 以使将搜索聚焦在有趣的模式上 它可能使用兴趣度阀值过滤发现的模式 模式 评估模块也可以与挖掘模块集成在一起 这依赖于所用的数据挖掘方法的实现 图形用户界面 实现用户和数据挖掘系统之阔的通信 允许用户与系统交 互 指定数据挖掘查询或任务 提供信息 帮助搜索聚焦 根据数据挖掘的中间 结果进行探索式数据挖掘 此外 此成分还允许用户浏览数据库和数据仓库模式 或数据结构 评估挖掘的模式 以不同的形式对模式可视化 1 3 数据挖掘的发展历程 从时矧轴上来看 数据挖掘技术经历了入下四个阶段 如表1 1 所示 表l l 数据挖掘技术经历的四个阶段 l 4 数据挖掘的应用范围 基于嵌入式移动数据库的数据挖掘 数据挖掘的应用范围是指数据挖掘能够在什么样的数据存储上进行 从原则 上讲 数据挖掘应该能够在任何类型的信息存储上进行 包括关系数据库 数据 仓库 事务数据库 嵌入式数据库 高级数据库系统 展开文件和w w w 1 4 1 关系数据库 数据库系统 通常又被称为数据库管理系统 d b m s 由一组内部相关的数 据和一组管理和存储数据的软件程序组成 软件程序涉及以下机制 数据库结构 定义 数据存储 并发 共享 或分布的数据访问 在面对系统瘫痪或未经授权 的访问时确保数据的一致性和安全性 关系数据库是表的结合 每个表都赋予一个唯一的名字 每个表包含一组属 性 列或字段 并通常存放大量元组 记录或行 关系中的每个元组代表一个 被唯一的关键字标识的对象 并被一组属性值描述 语义数据模型 如实体 联系 e r 数据模型 将数据库作为一组实体和它们之间的联系进行建模 关系数据库通常采用数据查询的方式进行访问 数据查询使用关系查询语 言 如著名的s q l 语言 或者借助于图形用户界面书写 当数据挖掘应用于关 系数据库时 可以进一步搜索趋势或数据模式 例如 数据挖掘系统可以分析顾 客数据 根据顾客的收入 年龄和以前的信用信息来预测新顾客的信用风险 在 数据挖掘应用的数据源中 关系数据库是最流行和最丰富的 因此也是数据挖掘 研究的主要数据形式 1 4 2 数据仓库 数据仓库是一种全新的数据存储模式 它是一种语义上一致的数据存储 充 当决策支持数据模型的物理实现 并存放企业战珞决策所需的信息 与其他数据 存储系统相比 数据仓库具有以下四个明显的特征 面向主题的 数据仓库围绕一些主题 如顾客 供应商 产品和销售进行 组织 数据仓库关注决策者的建模与分析 而不是集中于组织机构的日常操作和 事务处理 集成的 数据仓库通常是将多个异种数据源 如关系数据库 一般文件和 联机事务处理记录 集成在一起 因此 数据仓库排除对于决策无用的数据 提 供特定主题的简明视图 时变的 数据存储从历史 如过去的5 i o 年 的角度提供信息 数据仓 库巾的若键结构 隐式或显式地包含时间元素 非易失的 数掂仓库总是物理地分离存放数据 这些数据源于操作环境下 基于嵌入式移动数据库的数据挖掘 的应用数据 出于这种分离 数据仓库不需要事务处理 恢复和并发控制机制 通常 它只需要两种数据访问 数据的初始化装入和数据访问 1 4 3 事务数据库 事务数据库通常出一个文件组成 其中每个记录代表一个事务 通常 一个 事务包含一个唯一的事务标识号 t r a n s a c t i o ni d 简称t i d 和一个组成事务 的项的列表 事务可以存放在表中 每个记录代表一个事务 1 4 4 嵌入式数据库 所谓移动数据库是指支持移动计算环境的分布式数据库 由于移动数据库系 统通常应用在诸如掌上电脑 p d a 车载设备 移动电话等嵌入式设备中 因此 它又被称为嵌入式移动数据库系统 1 4 5 高级数据库系统和高级数据库应用 高级数据库系统是面向特殊应用的数据库系统 包括以下一些 面向对象的数据库 采用基于面向对象的程序设计范例 每个实体被看作 为一个对象 涉及一个对象的数据和代码封装在一个单元中 对象 关系数据库 基于对象 关系模型构造 此模型通过提供处理 复杂对象的丰富数据类型和对象定位 扩充关系模型 此外 它还包含关系查询 语言的特殊构造 以便管理增加的数据类型 空间数据库 包含涉及空间的信息 这种数据库包含地理 地图 数据库 v l s i v e r yl a r g es c a l ei n t e g r a t i o n 超大规模集成电路 芯片设计数据库 医疗 和卫星图象数据库 空间可能以光栅格式 r a s t e rf o r m a t 提供 由n 维位图 或象素图构成 时间和时间序列数据库 存放与时间有关的数据 文本数据库 包含对象文字描述的数据库 通常这种描述不是简单的关键 词 而是长句子或短文 如产品介绍 汇总报告等 文本数据库可能是高度非结 构化的 如w w w 上的网页 可能是半结构化的 如e m a i l 消息和一些 x m l h t m l 网页 也可能是良结构化的 如图书馆数据库 多媒体数据库 存放图象 音频和视频数据 它们用于基于图象内容的检 索 声音传递 视频点播 w w w 和识别口语命令的基于语音的用户界面等方 面 基于酞入式移动数据库的数据挖掘 异种数据库 出一组互连的 自治的成员数据库组成 这些成员问相互通 信 以便交换信息和回答查询 一个成员数据库中的对象可能与其他成员数据库 中的对象很不相同 使得很难将它们的语义吸收进一个整体的异种数据库中 遗产数据库 是一组异种数据库 它将不同的数据系统组合在一起 基于w w w 的全球信息系统 w w w 和与之关联的分布式信息服务提供 了丰富的 世界范围的联机信息服务 在这里 数据对象被链接在一起 便于交 互访问 1 5 数据挖掘的功能 数据挖掘功能用于指定数据挖掘任务中要找的模式类型 数据挖掘任务一般 可以分为两类 描述和预测 描述性挖掘任务刻划数据库中数据的一般特性 而 预测性挖掘任务则在当前数据上进行推断 以进行预测 在很多情况 用户并不知道什么样的模式是有趣的 因此可能想探索多种不 同的模式 以从中选择出自己感兴趣的模式 这就要求数据挖掘系统应该能够挖 掘多种类型的模式 以适应不同的需求 此外 数据挖掘系统应该能够发现各种 粒度 即不同的抽象层 的模式 应当允许用户给出提示 指导或聚焦有趣模 式的搜索 数据挖掘的功能以及可以发现的模式类型有 概念 类描述 关联分析 分类 和预测 聚类分析 孤立点分析和演变分析 类 概念描述 数据可以与类或概念相关联 用汇总的 简洁的 精确的方式描述每个 类和概念可能是有用的 这种类或概念的描述称为类 概念描述 这种描述可 以通过以下方法得到 数据特征化 是目标类数据的一般特征或特性的汇总 数据区分 将目标类对象的一般特性与一个或多个对比类对象的一般 特性比较 数据特征化和区分 同时应用数据特征化和数据区分进行描述 关联分析 关联分析用于发现关联规则 关联规则描述了给定数据集中的项之间的 有趣联系 关联分析广泛应用于购物篮或事务数据分析 从大量商务事务记 录中发现有趣的关联关系 可以帮助许多商务决策的制定 如分类设计 交 叉购物和贱卖分析等 基丁嵌入式移动数据厍的数据挖掘 分类和预测 分类是找出描述并区分数据类或概念的模型的过程 以便能够使用模型 预测类标记未知的对象类 预测是构造和使用模型评估无标号样本类 或评 估给定样本可能具有的属性值或值区间 分类和预测之间的区别在于 分类 是预测类标号 或离散值 而预测是建立连续值函数模型 例如 可以建 立一个分类模型 对银行贷款的安全或风险进行分类 同时可以建立预测模 型 给定潜在顾客的收入和职业 预测他们在计算机设备上的花费 聚类分析 聚类将数据对象分组成为多个类或簇 在同一个簇中的对象之间具有较 高的相似度 而不同簇中的对象差别较大 与分类不同的是 它要划分的类 是未知的 孤立点分析 在数据库中经常存在一些数据对象 它们不符合数据的一般模型 这样 的数据对象被称未孤立点 它们与数据的其他的部分不同或不一致 孤立点 可能是度量或执行错误所导致的 例如 数据库记录中有一些人的年龄是 一9 9 9 这可能是这些人年龄没有被记录 而系统给未记录的年龄的缺省值就 是 9 9 9 孤立点也可能是固有的数据变异后的结果 例如 一个公司总裁的 薪水可能远远高于其他职员的薪水 他的薪水就成为了一个孤立点 在许多 时候 孤立点被视为噪声或遗产而被丢弃 但是 在一些应用中 孤立点可 能会很有用 例如 在医疗分析中 某些对多种治疗方式的不寻常的反应数 据可能成为孤立点 但是这些数据对于治疗却非常重要 对孤立点数据进行 分析称为孤立点分析 演变分析 数掘演变分析描述行为随时间变化的对象的规律或趋势 并对其建模 这种分析可能包括时间相关数据的特征化 区分 关联 分类或聚类 但是 它的不同特点包括时间序列数据分析 序列或周期模式匹配和基于类似性的 数据分析 1 6 数据挖掘面临的主要问题 数据挖掘面l 临的主要问题有三大类 挖掘方法和用户交互的问题 性能问题 和存储数据的数据库类型具有多样性的问题 1 6 1 挖掘方法和用户交互问题 基t 嵌入式移动数据库的数据挖掘 这类问题涉及到数据挖掘技术的多个方面 主要有以下一些内容 在数据库中挖掘不同类型的知识 出于不同的用户感兴趣的知识类型可 能会很不相同 这就要求数据挖掘系统应当覆盖范围很广的数据分析和知识发现 任务 包括数据特征化 区分 关联 分类 聚类 趋势和偏差分析以及类似性 分析 这些方式可能以不同的方式使用相同的数据库 并需要开发大量的数据挖 掘技术 多个抽象层的交互知识挖掘 由于在进行数据挖掘之前很难知道将要挖 掘出来的是什么样的知识 因此需要数掘挖掘的过程具有交互性 对于大型的数 据库 应当使用抽样技术进行交互式的数据探查 交互式挖掘允许用户聚焦搜索 模式 根据返回的结果提出和精炼数据挖掘请求 从而使用户可以以不同的粒度 和从不同的角度观察数据和发现模式 结合背景知识 可以使用背景知识或关于所研究领域的信息来指导发现 过程 并使得发现的模式以简洁的形式在不同的抽象层表示 关于数据库的领域 知识 如完整性约束和演绎规则 可以帮助聚焦和加快数据挖掘过程 或评估发 现的模式的兴趣度 数据挖掘查询语言和特定的数据挖掘 与现在存在大量的高级程序开发 语言相比 数据挖掘还缺乏一门统一的高级语言用于描述数据挖掘的过程和结 果 关系查询语言 如s q l 智能允许用户提出特定的数据检索查询 而对数 据挖掘高级语言的要求则更高 它应该能够使用户通过说明分析任务的相关数据 集 领域知识 所挖掘的数据类型 被发现的模式必须满足的条件和约束 描述 特定的数据挖掘任务 这种语言应当与数据库或数据仓库查询语言集成 并且对 于有效的 灵活的数据挖掘是优化的 数据挖掘结果的表示和显示 高级语言 可视化表示或其他形式的表示 方法可以使知识易于理解 能够被人们直接使用 这要求系统采用有表达能力的 知识表示技术 如树 表 规则 图 图表 交叉表 矩阵或曲线 处理噪声和不完全数据 存放在数据库中的数据可能反映噪声 异常情 况或不完全的数据对象 它们可能搞乱分析过程 导致数据与所构造的知识模型 过分适应 由此导致所发现的模式精确性很差 这就需要处理数据噪声的数据清 理方法和数据分析方法 以及发现和分析异常情况的孤立点挖掘方法 模式评估 兴趣度问题 数据挖掘方法发现的模式通常数以千计 怎 样从中选择出用户感兴趣的模式是一个极具挑战性的问题 l 6 2 性能问题 基于嵌入式移动数据库的数据挖 数掘挖掘算法的有效性和可伸缩性 数据挖掘算法的有效性要求算法的 运行时 1 i j 应尽可能地少 而可伸缩性则要求算法能够适应不同大小的数据库容 量 算法的运行时间应尽可能地与数据库的容量保持线性比例的增减关系 并行 分布式和增量挖掘算法 并行和分布式数据挖掘算法将数掘划分 成多个部分 这些部分可以并且处理 然后将各个处理结果合并 这种类型的算 法可以对付数据库的大容量 数据的广泛分布和一些数据挖掘算法的计算复杂性 的问题 而数据挖掘过程的高花费导致了对增量挖掘算法的需求 这种类型的算 法和数掘库更新结合在一起 它不必随着数据库的更新重新挖掘全部数据 而只 需要在原有挖掘结果的基础上修正和加强业已发现的知识 1 6 t 3 关于数据库类型的多样性问题 关系的和复杂的数据类型的处理 由于数据库类型的多样性 指望一个 系统挖掘所有类型的数据是不现实的 为挖掘特定类型的数据 应当构造特定的 数据挖掘系统 由异种数据库和全球信息系统挖掘信息 局域网和广域网 如互连网 提供了大量庞大的 分布式的和异种的数据库 从具有不同语义的结构化的 半 结构化的和非结构化的不同数据源发现知识 是数据挖掘技术面临的一个巨大挑 战 1 7 数据挖掘的研究与开发方向 数据挖掘现在是数据库研究 开发和应用最活跃的分支之一 它涉及了计算 机科学中的多个领域 这些领域包括传统的数据库技术 人工智能 机器学习 神经网络 统计学 模式识别 知识库系统 知识获取 信息提取 高性能计算 和数据可视化等学科 随着这些学科的不断发展 数据挖掘也需要不断的发展 作为一门新兴的技术 数据挖掘的发展也是适应科技发展大潮流的需要 针对数 据挖掘现在面l 临的主要问题 数据挖掘的研究与开发最主要的方向有以下一些 与数据仓库与在线分析处理技术结合 数据仓库可以为在线分析处理和数 据挖掘提供经过滤化的 完整的数据资源 在线分析处理可以看作为一个简化的 对数据进行聚合的数据挖掘形式 与在线分析处理工具相结合 一个数据挖掘器 d a t am i n e r 能够深入到一个数据立方体 d a t ac u b e 的任意一维 从而在不同的 抽象层上找到用户感兴趣的形式 由此也增加了数据挖掘与数据仓库系统的用 途 挖掘多种类型的知识 数据挖掘除了最常见的分类与关联之外 还有许 基于嵌入式移动数据库的数据挖掘 多重要的任务待开发 包括描述 比较 聚合 预测模型以及时间相关形式分析 等等 提供埘数据挖扣 的查询语言和高效 交互式及特殊数据挖掘的支持 与 相关语言类似 高层次的数据挖掘语言应该能够允许用户定制特殊的数据挖掘任 务 处理复杂数据 挖掘关联性和事务性的数据是目前数据挖掘的中心 但 是对于半结构化以及非结构化的数据进行挖掘 也是 个非常重要而极富挑战性 的方面 高性能的数据挖掘 高效性和可伸缩性是目前数据挖掘算法的焦点 随 着并行的 分布式的以及增长式的数据挖掘技术的发展 这种趋势将会继续得到 发展 可视化和数据挖掘 数据库内容和数据挖掘结果的可视化可以帮助用户 理解和评估挖掘结果 从而对数据挖掘进行相应的调整 对交互式的挖掘来说 开发易用与易看的工具是一个很有发展空间的领域 数据挖掘的应用 如何将数据挖掘技术应用于现实世界也是 个非常重 要的课题 基于嵌入式移动数据库的数据挖捌 第二章嵌入式数据库 2 1 嵌入式移动数据库的发展现状 数据库技术一直随着计算的发展而不断进步 随着移动计算时代的到来 嵌 入式操作系统对移动数据库系统的需求为数据库技术开辟了新的发展空间 嵌入 式移动数据库技术目前已经从研究领域逐步走向广泛的应用领域 随着智能移动 终端的普及 人们对移动数据实时处理和管理要求的不断提高 嵌入式移动数据 库越来越体现出其优越性 从而被学界和业界所重视 嵌入式数据库除了具有关系数据库的主要功能外 还针对嵌入式系统和移动 计算的特点 在数据库的体系结构 功能设置 应用开发等方面另具特色 它适 用于p a l m p u h p c p d a w a p 手机 车裁盒 工控产品以及一些信息家电等 以增强系统的性能和提高开发效率 目前国内市场已有许多嵌入式移动数据库产 品 如人大金仓 小金灵 东大o p e n b a s e m i n i i b md b 2 e v e r y p l a c e s y b a s e u l t r a l i t e o r a c l e8 il i t e 等 2 2 移动计算和嵌入式移动数据库的基本概念 移动计算是一种新型的技术 它使得计算机或其他信息设备在没有与固定的 物理连接设备相连的情况下能够传输数据 移动计算的作用在于 将有用 准确 及时的信息与中央信息系统相互作用 分担中央信息系统的计算压力 使有用 准 确 及时的信息能提供给在任何时间 任何地点需要它的任何用户 所谓移动数据库是指支持移动计算环境的分布式数据库 由于移动数据库系 统通常应用在诸如掌上电脑 p d a 车载设备 移动电话等嵌入式设备中 因此 它又被称为嵌入式移动数据库系统 移动计算环境比传统的计算环境更为复杂和灵活 计算平台的移动性 连接 的频繁断接性 网络条件的多样性 网络通讯的非对称性 系统的高伸缩性和低 可靠性以及电源能力的有限性等因素对移动数据库的性能提出了相当高的要求 移动技术的发展必将对嵌入式移动数据库的发展起强大的推动作用 同时嵌入式 移动数据库的发展也能促进移动计算的广泛应用 2 3 嵌入式系统中数据库的地位 23 1 嵌入式设备对数据库的支持 基于嵌入式移动数据库的数据挖抓 嵌入式处理器主要由一个单片机或微控制器组成 目前多是8 b 1 6 b 和3 2 b 公理器 支持硬件有显卡 r o m 和r a m 通讯设备及i o 设备等 嵌人式系 统有别于一般的计算机系统 整个系统结构紧凑 针对性强 硬件资源遵循 够 用为原则 处理能力有限 它一般不配备像硬盘那样大容量低价格的存储器 而大多使用闪存 f i s hm e m o 刚作为辅储 2 3 2 嵌入式系统对软件的限制 嵌入式软件包括与硬件相关的底层软件 操作系统 图形界面 通讯协议 数据库系统 w e b 浏览器和应用软件等 它具有以下显著特点 硬件资源占用少 支撑软件功能简单 没有或仅有较简单的操作系统支持 高可靠性 易用性好 免维护 需要在专用的开发系统上编写软件 许多程序存储在r o m 中 用户一般不能修改或配置程序 系统突发性事件可能造成效据丢失 2 3 3 嵌入式系统对数据库的需求 嵌入式系统主要由嵌入式处理器 相关支掺硬件和嵌入式软件组成 它是集 软硬件于一体的独立工作的 器件 根掘设备功能的强弱 可将移动设备分为 3 个档次 1 低端系统 内存在i m b 以下 应用较简单 采用文件系统管理数据即可 并不迫切的需要数据库 2 中端系统 内存在1 m b 8 m b 之问 应用较复杂 数据管理功能明显高于 低端系统 同时它能够提供d b m s 所需的存储空间和处理能力 因此有必要采 用数据库管理数据 3 高端系统 内存在8 m b 以上 处理能力不低于4 8 6 p c 机 此类系统能很 好地支持数据库 其实在很小的嵌入式系统中也有对数据库的需求 如 p i c o d b m s 就是一种应用在s m a n c a r d 系统中的数据库 而高档的掌上电脑 如 联想天玑5 0 0 0 c o m p a qi p a q 等处理能力与低档p c 机相当 既可很好地支持数 据库 又对数据库有强烈的需求 从技术上看低端移动设备中的数据库最具挑战 性 它既要适应低端设备的资源限制 又必须提供数据库基本功能 基j 嵌入式移动数据库的数据挖掘 我们认为用户对嵌入式数据库的需求着重在4 个方面 1 d b n d 的功能够用而不多余 这主要是由于嵌入设备资源紧张 2 系统稳定性好 可靠性商 这样才能符合嵌入设备应用群体的特点 3 歼发工具功能完备 易学易用 这样才能保证开发效率 4 d b m s 可裁剪或可定制 以适应嵌入式设备种类繁多 设备之间的性能 差别极大的特点 2 4 移动数据库管理系统的特性 移动d b m s 的计算环境是传统分布式d b m s 的扩展 它可以看作客户端与 固定服务器结点动态连接的分布式系统 因此移动计算环境中的数据库管理系统 是一种动态分布式数据库管理系统 由于嵌入式移动数据库管理系统在移动计算 的环境下应用在嵌入式操作系统之上 所以它有自己的特点和功能需求 微小内核结构 考虑到嵌入式设备的资源有限 嵌入式移动d b m s 应采用微型化技术实 现 在满足应用的前提下紧缩其系统结构以满足嵌入式应用的需求 对标准s q l 的支持 嵌入式移动d b m s 应能提供了对标准s q l 的支持 支持s q l 9 2 标准的 子集 支持数据查询 连接查询 予查询 排序 分组等 插入 更新 删除多种标准的s q l 语句 充分满足嵌入式应用开发的需求 事务管理功能 嵌入式移动d b m s 应具有事务处理功能 自动维护事务的完整性 原子 性等特性 支持实体完整性和引用完整性 完善的数据同步j 0 t 数据同步是嵌入式数据库最重要的特点 通过数据复制 可以将嵌入式 数据库或主数据库的变化情况应用到对方 保证了数据的一致性 嵌入式移 动数据库管理系统应具有以下的特点 1 提供多种数据同步方式 具有上载同步 下载同步和完全同步三种 同步方式 2 具有完善的冲突检测机制和灵活的冲突解决方案 具有冲突日志记 录功能 3 支持快速同步 系统同步时 只传递变化的数据 节省了大量的同 步时问 基于嵌入式移动数据库的数据挖掘 4 支持表的水平分割和垂直分割复制 最大限度地降低了嵌入式数据 库的大小 5 支持异构数据源连接同步 可以用支持o d b c 的异构数据源作为主 数据库和嵌入式设备上的数据库进行数据同步 6 具有主动同步的功能 允许用户对系统提供的同步事件自定义过程 实现 提供了最大灵活度的同步过程 支持多利 连接协议 嵌入式移动d b m s 应支持多种通信连接协议 可以通过串行通信 t c p 1 p 红外传输 蓝牙等多种连接方式实现与嵌入式设备和数据库服务器 的连接 完备的嵌入式数据库的管理功能 嵌入式移动d b m s 应具有自动恢复功能 基本无需人工干预进行嵌入式 数据库管理并能够提供数据的备份和恢复 保证用户数据的安全可靠 支持多种嵌入式操作系统 嵌入式移动d b m s 应能支持w i n d o w sc e p a l mo s 等多种目前流行的 嵌入式操作系统 这样才能使嵌入式移动数据库管理系统不受移动终端的限 制 另外 一种理想的状态是用户只用一台移动终端 如手机 就能对与他相关 的所有移动数据库进行数据操作和管理 这就要求前端系统具有通用性 而且要 求移动数据库的接口有统一 规范的标准 前端管理系统在进行数据处理时自动 生成统一的事务处理命令 提交当前所连接的数据服务器执行 这样就有效的增 强了移动数据库的通用性 扩大了嵌入式移动数据库的应用前景 总之 在嵌入式移动数据库管理系统中还需要考虑诸多传统计算环境下不需 要考虑的问题 如对断接操作的支持 对跨区长事务的支持 对位置相关查询的 支持 对查询优化的特殊考虑以及对提高有限资源的利用率和对系统效率的考虑 等等 为了有效地解决上述问题 诸如复制与缓存技术 移动事务处理 数据广 播技术 移动查询处理与查询优化 位置相关的数据处理及查询技术 移动信息 发布技术 移动a g e n t 等技术仍在不断的发展和完善 他们会进一步促进移动数 据库技术的发展 2 5 移动性对嵌入式数据库的影响 移动汁算的主要特征是计算组件能与计算资源动态改变绑定关系 表现出移 基1 战八式移动数捌阼的数据挖扭 动性 有两类关注移动特性的计算 m o b i l ec o m p u t i n g 和m o b i l ec o m p u t a t i o n 2 5 1 嵌入式设备的移动特性 嵌入设错中有相当一部分具有移动性 移动的嵌入设备对效据库又有新要求 使d b m s 的技术更为复杂 有3 种不同的移动信息系统 1 主机移动系统 2 代理移动系统 3 厦务伴随漫游系统 本文主要针对第一种移动系统 移动计算的网络环境具有鲜明的特点 移动性 断接性 带宽多样性 可伸 缩性 弱可敲性 网络通信的非对称性 电源能力局限性等 嵌入式移动系统兼 有嵌入式和移动两者的优势 同时在应用中又要克服两者的弱点 2 5 2 移动系统的分布性 移动设备的移动性和断接性必然要求系统具有较高的自治性 但移动性 数 据存储和处理能力的局限性又要求移动设备上的数据库与其它数据库有密切的 联系 因此 e m d b 与固定数据库应构成分布式数据库系统 应用不同 分布 能力也不同 分布性表现为数据的物理独立性 数据有较大的冗余度 各设备有 很强的自治性 数据库有较强的同步和复制能力等 高度的透明性会给开发者带 来很大方便 但同时会增加系统的复杂程度 2 5 3 移动性对数据库的特殊要求 按是否具有移动性来划分嵌入式数据库的应用分为 固定式嵌入设备应用和 移动式嵌入设备应用 移动设备在信息处理系统中既可作为移动客户机又可作为 移动服务器 而前者最为普遍 本文仅讨论此类系统中的数据库 移动性使得数 据库面临这样一些关键技术 移动事务处理 移动事务属于分布事务 该事务一部分在客户机上完成 一部分在服务器上完成 数据 播 数据复制 缓冲技术 陔技术是解决移动数据断接性的关键技术 移动查询处理 上述技术在现实的e m d b m s 中并不一定要全部解决 嵌入式系统中应遵循 的一一个重要原则是 用不到的功能一定不要有 可有可无的功能最好也不要有 基于嵌入式移动数据库的数据挖拥 2 6 嵌入