（计算机应用技术专业论文）移动数据库中动态数据广播策略的研究.pdf

摘要 随着计算机技术和通信技术的迅猛发展，移动计算机f 在逐步取代有线网络 和固定主机。移动设备的大量普及，许多移动节点要求随时随地和网络建立连接， 移动计算使得计算机或其他信息设备在没有与固定的物理连接设备相连的情况 下能够传输数据。其中，动态数据广播技术作为实现移动数据库的关键技术，很 大程度上影响着移动数据库应用的速度和效率。它是解决嵌入式移动数据库系统 用户规模庞大及网络通信非对称性问题的一种有效办法，服务器将大多数用户频 繁访问的热点数据以一定的方式组织起来，主动周期性地广播出去，这样充分利 用了有限的网络带宽，极大地提高了系统的可伸缩性。在数据广播的研究中，需 要解决广播的调度问题。 本文首先概要介绍了移动数据库和数据挖掘的基本知识，然后对移动数据库 的各种数据广播策略进行了分析，将数据挖掘聚类算法中的c u r e 算法引入动 态广播策略中，利用c u r e 算法的特点，使算法分析结果更适合提高对现有事 务请求的响应，并结合改进的c u r e 算法和数据挖掘技术提出了更高效的动态 数据广播策略，而且针对这种算法实现了简单的系统，并将此算法的思想应用到 实际系统的应用分析中。 c u r e 算法的引入，使动态数据广播策略有了更有效的分析方法；对c u r e 算法的改进，提高了该算法在执行算法分析过程中的效率。 关键词：移动数据库数据挖掘数据广播c u r e 聚类算法最邻近算法 a b s t r a c t a l o n g w i t ht h e r a p i dd e v e l o p m e n to ft e c h n o l o g yi n c o m p u t e r a n d c o m m u n i c a t i o n s ，m o b i l ec o m p u t e ri sr e p l a c i n gw i r e n e t w o r ka n df i x e dh o s ts t e pb y s t e p a sm a s sp o p u l a r i z a t i o no fm o b i l ed e v i c e ，m o b i l en o d e ( m o b i l es e r v e rs t a t i o n ，。 m s s ) n e e dc o n n e c tt on e t w o r ka ta n ym o m e n ta n da n y w h e r e ，m o b i l ec o m p u t em a k e c o m p u t e ra n do t h e rd e v i c et r a n s f o r mi n f o r m a t i o nw i t h o u tc o n n e c t i n gt of i x e dp h y s i c a l c o n n e c t o r a so n eo ft h ek e yt e c h n i q u et or e a l i z i n gm o b i l ed a t a b a s e ，d y n a m i cd a t a b r o a d c a s t i n gh a sg r e a te f f e c to ns p e e da n de f f i c i e n c yo fm o b i l ed a t a b a s ea p p l i c a t i o n s i ti sa l le f f e c t i v ew a yt os o l v el a r g es c a l eu s e r si ns y s t e mo fe m b e d d e dm o b i l e d a t a b a s ea n da s y m m e t r yn e t w o r kc o m m u n i c a t i o n s ，s e r v e r sc o l l e c th o td a t aw h i c ha r e a c c e s s e db ym a j o r i t yu s e r si ns o m ew a y , a n db r o a d c a s tt h e ma c t i v e l ya n d p e r i o d i c a l l y , i tc a nm a k eu s eo fl i m i t e db a n d w i d t hn e t w o r ki nf u l l ，a n de n h a n c es y s t e mf l e x i b i l i t y l a r g e l y i nt h es t u d yo fd a t ab r o a d c a s t i n g ，w es h o u l ds e t t l es c h e d u l i n gp r o b l e mo f b r o a d c a s t i n g t h i sp a p e ra n a l y s e sm a n yk i n d so fd a t ab r o a d c a s t i n gs t r a t e g i e si nm o b i l e d a t a b a s e ，i n t r o d u c ec u r ea l g o r i t h m ，w h i c hi sac l u s t e r i n ga l g o r i t h mi nd a t am i n i n g ， i n t od y n a m i cb r o a d c a s t i n gs t r a t e g y , u s i n gi t ss p e c i a l t yt om a k ei tm o r ec o m p a t i b l et o t h er e q u i r e m e n t ，a n db r i n g sf o r w a r dam o r ee f f i c i e n ts t r a t e g yw i t hi m p r o v e dc u r e a l g o r i t h ma n dt e c h n i q u eo fd a t am i n i n g ，a l s oc a r r i e so u tas i m p l es y s t e mu s i n gt h e a l g o r i t h m ，a n da p p l i e st h ei d e ao ft h ea l g o r i t h mt op r a c t i c a la p p l i c a t i o n t h ei n t r o d u c t i o no fc u r ea l g o r i t h mm a k e sd y n a m i cb r o a d c a s t i n gs t r a t e g yh a v e n e wa n a l y z em e t h o d ，a n dt h ei m p r o v ea l g o r i t h mo fc u r ee n h a n c e st h ee f f i c i e n c yo f e x e c u t i n ga n a l y z ew i t ht h ea l g o r i t h m k e y w o r d s ：m o b i l ed a t a b a s e ，d a t am i n i n g ，d a t ab r o a d c a s t ，c u r ec l u s t e r i n ga l g o r i t h m ， n e a r e s tn e i g h b o r a l g o r i t h m 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得丞洼王些丕堂或其他教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示了谢意。 学位论文作者签名： 主谚 签字日期：腓；月夕同 学位论文版权使用授权书 本学位论文作者完全了解丞洼王些太堂有关保留、使用学位论文的规定。 特授权丞洼王些太堂可以将学位论文的全部或部分内容编入有关数据库进行 检索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学 校向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 舌厶 签字日期万年驷7 日 导师签名： 劫琶贸 签字日期：1 阳年、月夕日 学位论文的主要创新点 一、将聚类算法中的c u r e 算法应用于动态数据广播策略的分析中， 利用c u r e 算法在适合的数据类型、发现的聚类类型、对脏数据或 异常数据的敏感性和对数据输入顺序的敏感性等方面的特点，建立新 的动态数据广播策略，提高了现有事务请求的相应速度。 二、将应用了最邻近算法的改进c u r e 算法应用于实际项目中，实 现动态数据的增量分析，通过避免对原始数据的重复计算带来的不必 要开销，在得剑相似分析结果的基础上，提高算法的执行效率。 第一章绪论 第一章绪论 1 1 课题的背景及研究意义 从计算的发展来看，数据库技术一直都同计算环境的发展保持基本同步，并 且相互促进。计算机技术和无线通讯技术的发展与结合使得一种全新的计算环境 移动计算成为现实。这种被形容为“o i lt h eg o ”的移动计算环境使我们在任何 时间、任何地点都可以方便的访问网络，获取所需要的信息。它是在分布式计算 的基础上结合各种移动设备和具有无线通信能力的服务网络形成的新的计算环 境，比传统的计算环境更为复杂和灵活。在这样的环境下，移动数据库应运而生， 它为数据库技术开辟了新的发展空问。随着智能移动终端的普及，人们对移动数 据库实时处理和管理要求不断提高，加上移动计算平台的移动性、连接的频繁断 接性、网络条件的多样性、网络通信的非对称性、系统的高伸缩性和低可靠性以 及电源能力的有限性等因素，这些都对移动数据库的性能提出了相当高的要求。 移动技术的发展对移动数据库的发展起着强大的推动作用，同时移动数据库的发 展也能促进移动计算的广泛应用。由于对其应用要求的迫切性，“移动计算”和“移 动数据库”迅速发展成为一个研究的热点领域。移动讨。算技术与刚络基础建设、 电子商务和软件应用一起被认为是对未来最有影向的四大技术方向f l l 。 移动设备的应用，使得很多情况下我们都需要在移动设备上储存一些数据。 在移动数据库问世之前，所有的数据都是存放在文件中，当数据量比较大时，对 数据进行检索、删除等操作的效率是非常低的。现在很多公司考虑到移动设备的 多样性，普遍使用x m l 来保存数据，虽然x m l 是一种和平台无关的文档标准， 但是由于当前移动设备的处理能力的限制，解析一个包含较多数据的x m l 文件 时，其性能的开销是无法满足实际需求的，为了达到较高的使用效率，所以移动 设备上的数据量受到了很大的限制。而移动数据库之所以能够称为数据库，就是 因为移动数据库包含的数据量可以达到相当的规模，而并非少量的数据( 几十或 几百条记录) 可以比拟的，而且在对数据的操作上效率也得到了很大的提蒯2 1 。 移动数据库技术有着很高的学术起点并涉及到多个学科领域，在数据的存 储、组织和管理等方面要借助和继承传统数据库技术，但又不与之完全等同；在 数据的传播方面又涉及到无线通讯技术和计算机网络技术。总之，在移动数据库 中还需要考虑诸多传统计算环境下不需要考虑的问题，如对断接操作的支持、对 跨区长事务的支持、对位置相关查询的支持、对查询优化的特殊考虑以及对提高 有限资源的利用率和对系统效率的考虑等等。为了有效地解决上述问题，诸如复 第一章绪论 制与缓存技术、移动事务处理、数据广播技术、移动查询处理与查询优化、位置 相关的数据处理及查询技术、移动信息发布技术、移动a g e n t 等技术仍在不断发 展和完善，它们会进一步促进移动数据库技术的发展i 引。 本文对移动数据库中的数据广播技术进行分析，用关联规则挖掘算法和聚类 挖掘算法实现了更高效的动态数据广播策略，并将改进后的聚类算法应用于实际 项目中进行测试。 1 2 移动数据库的发展与应用 1 2 1移动数据库的特性 嵌入式移动数据库或简称为移动数据库是指支持移动计算环境的分布式数 据库，通常应用在诸如掌上电脑、p d a 、车载设备、移动电话等嵌入型设备中。 简单地说，数据并不是纯粹地存储在服务器或p c 机上的，也可以存放在内存和 处理性能受限的移动设备上。这些安装在移动设备上，用来管理和操作数据的系 统就是所谓的移动数据库l 训。 移动数据库的计算环境是由传统的分布式数据库发展而来，是传统分布式数 据库的扩展，它将分布式的概念应用到客户端与固定服务器节点的动态连接上， 因此移动计算环境中的数据库管理系统是一种动态分布式数据库管理系统l 孤。根 据移动数据库的应用环境特点，它具有与普通数据库不同的特点，在功能需求方 面也存在很大差别1 3 】o 1 内核结构微小 移动数据库是应用在嵌入型操作系统上，一般来说，嵌入型设备的资源相对 有限，所以移动数据库应采用微型化技术实现，即在满足应用的前提下应尽量紧 缩其系统结构以满足嵌入型应用的需求。 2 数据同步机制 数据同步是移动数据库最重要的特点。通过数据复制，可以将移动数据库或 主数据库的变化情况应用到对方，保证数据的一致性。移动数据库管理系统应具 有以下的特点： ( 1 ) 提供多种数据同步方式。具有上载同步、下载同步和完全同步三种同步 方式。 ( 2 ) 具有完善的冲突检测机制和灵活的冲突解决方案，具有冲突日志记录功 能。 ( 3 ) 支持快速同步。系统同步时，只传递变化的数据，节省了大量的同步时 2 第一章绪论 间。 ( 4 ) 支持表的水平分割和垂直分割复制，最大限度地降低了移动数据库的大 小。 ( 5 ) 支持异构数据源连接同步。可以用支持o d b c 的异构数据源作为主数据 库和嵌入型设备上的数据库进行数据同步。 ( 6 ) 具有主动同步的功能。允许用户对系统提供的同步事件自定义过程实 现，提供了最大灵活度的同步过程。 3 支持标准s q l 移动数据库应能提供对标准s q l 的支持。支持s q l 9 2 标准的子集，支持数 据查询( 连接查询、子查询、排序、分组等) 、插入、更新、删除等多种标准的 s o l 语句，充分满足嵌入型应用开发的需求。 4 事务管理功能 移动数据库应具有事务处理功能，自动维护事务的完整性、原子性等；支持 实体完整性和引用完整性。 5 支持多种连接协议 移动数据库应支持多种通信连接协议。可以通过串行通信、t c p i p 、红外传 输、蓝牙等多种连接方式实现与嵌入型设备和数据库服务器的连接。 6 完备的数据库管理功能 移动数据库应具有自动恢复功能，基本无需人工干预进行移动数据库管理并 能够提供数据的备份和恢复，保证用户数据的安全可靠。 7 支持多种嵌入型操作系统 移动数据库应能支持w i n d o w sc e 、p a l mo s 等多种目前流行的嵌入型操作 系统，这样才能使它不受移动终端的限制。 1 2 2 移动数据库应用 当移动计算环境初现端倪时，为了抢占商机和市场，世界上几家著名的大型 数据库软件公司相继推出了各自的移动计算解决方案和产品。比如关系数据库领 域的巨头o r a c l e 公司推出的支持移动计算机访问数据库的产品m o b i l e a g e n t ；l n f o r m i x 公司推出的基于移动计算机、应用a g e n t 服务器、数据库服务 器三层的体系结构的移动计算解决方案；s y b a s e 公司推出的采用数据复制技术来 支持移动计算的s y b a s es q l a n y w h e r e 和s q lr e m o t e 两种产品( 官方网站) 1 5 l 。 我国从上个世纪九十年代就对移动数据库开始了研究，并取得了许多成果。中国 人民大学已经成功研制出“小金灵”嵌入式移动数据库管理系统，并在许多行业进 行应用。 第一章绪论 移动数据库技术目前已经从研究领域向更广泛的应用领域发展，随着移动通 信技术的进步和人们对移动数据处理和管理需求的不断提高，与各种智能设备紧 密结合的移动数据库技术已经得到了学术界、工业界、军事领域、民用部门等各 方面的重视。移动数据库技术可以实现场地内或场地间的移动应用、现场审计和 检查，以及在金融业、零售业和分销业、卫生保健、法律和公共安全、运输业等 行业应用，此外，还有其它一些专门的移动应用，如航空、铁路等服务行业，它 们都要求提供方便、快捷的服务，而自动交通税收、自动仪表信息收集和电子地 图等应用更具有明显的行业特殊性。人们将发现，不久的将来移动数据库将无处 不在。人们希望随时随地存取任意数据信息的愿望终将成为现实。 目前，根据各个行业的特点，很多系统都采用了满足其户外工作人员需求的 行业解决方案： 1 政府工作解决方案 现在很多政府部门也在逐渐采用无线解决方案来提高工作效率。比如北京政 府的很多部门都使用了移动办公系统，无论何时何地，通过移动办公系统可以处 理公文审批、人事管理、绩效审核等管理工作，有效解决因出差、会议等延误时 间的问题，极大提高办公效率。此外，部门内部可通过短信定位发送、群组发送 的形式进行会议活动通知、日程安排提醒、邮件从文流转提醒。 2 工作人员提高办公效率 对于某些工作性质的关系，很多时候需要人员到现场进行数据的采集和记 录，比如输电线路、铁路等线路的巡检f 6 】，海关港口集装箱检验，家庭用户煤气 使用量、水用量等的查看，都需要出外勤的工作人员，他们可应用移动数据库提 高办公效率，并且记录的数据比纸制数据方便整理、保存和统计。 3 快递行业移动服务 投递员在开始一天的工作时，就可以直接通过p d a 查看今天将要发送的所 有包裹的信息，例如包裹的收件人、收件地址和联系方式，并且还可以给出一个 最佳的投递路线。除此之外，当包裹送达后，客户还可以直接在p d a 上进行签 名以确认货物的送达，而后投递员就可以将客户签名和货物送达信息直接通过无 线网络传递给中心服务器，避免了一系列的“纸上操作”过程，大大加快了工作的 效率。 4 交通路线查询系统 在北京、上海和广州等大城市，交通出行是一个非常大的问题。如果我们可 以将某个城市的交通路线信息都保存到移动数据库中，日后出行时就可以通过携 带的移动设备方便地查看乘车路线。如果开发这类的程序，可以根据不同的需求 采用不同的实现方法。最简单的一种就是将城市的所有路线信息都保存到移动数 4 第一章绪论 据库中，这样做的缺点就足缺乏灵活性，当城巾的某些路线发生变化时，无法实 时地获得最新的路线信息。当然，我们也可以通过网络从中心数据库检索信息， 而后存放到移动数据库，这样不但可以具备较好的实时性，而且减少了多次联网 带来的费用问题。 5 无线点菜 以信息技术为代表的当今科技已逐步渗透到各行各业，并从根本上改变着我 们的工作和生活方式。餐饮业也不例外，这个传统的服务行业也在经历着信息化 的洗礼，无线点菜其实就是一个很有前景的市场应用。无线点菜最大的优势就是 可以将消费者的菜单直接发送到厨房中心的计算机上，避免了服务人员在餐厅和 厨房中心之间的来回奔波。除此之外，无线点菜系统还可以将消费者的最终消费 情况直接发送至结算中心，这样就可以提前为消费者准备好消费清单，减少了消 费者结账的等待时间。我们所常见的传统的一张纸、一纸笔的点菜方式，收银结 账敲计算器，收银员挥汗如雨，收银台一片忙乱的情形正悄悄地离我们而去，这 一切都是信息化所带来的便利。 6 股票看盘系统 这两年的中国股市真可谓风云变幻，但正因为这样，越来越多的中国人逐渐 加入了炒股的大潮中。现在很多手机生产厂商已经将股票看盘系统集成到手机 中，作为它的一个卖点来吸引股民的眼球。通过网络，股民可以实时地获得股市 的“指数走势”、“个股走势”、“行情揭示”等信息，也可以通过无线的方式对股票 进行买入卖出的操作。除此之外，我们还可以将一些重要数据保存到移动数据库 中，以便日后的查询分析。 为了保证商品软件的一致性和可用性，新的数据库管理系统一般不走重新设 计的方法，大多是在原有数据管理系统产品的基础上进行修改而成，所以在移动 数据库技术的复制和缓存、数据广播、移动查询优化和事务处理及安全技术这些 关键技术方面都还存在着许多问题，因此，从移动数据库的研究到实际系统的应 用，还有大量的工作要做。 随着移动技术的逐步成熟，移动数据库的应用将会越来越多。现在，中国的 无线网络覆盖面积已经非常的广泛，而且3 g 也即将在中国全面铺开，这将大大 缓解当前无线网络存在的速度瓶颈问题。另外，使用智能手机的人越来越多，应 用无线网络的移动设备程序也会逐步增多。但即使3 g 到来，也不可能实现所有 的程序仅通过网络就可以完成所有的功能，毕竟还存在很多不确定的因素，比如 无线网络的覆盖问题。解决上述问题最好的办法就是采用移动数据库，当无线网 络畅通时，就可以利j j 无线网络获取所需的信息，并将这些重要的信息存放到移 动数据库中。如果无线网络无法连接的话，我们就可以使用移动数据库中存放的 5 第一章绪论 数据，完成相应的操作。而后当无线网络再次畅通时，我们就可以将移动数据库 中的数据改变回传至中心服务器数据库。而且，中心服务器数据库中如果存在新 的数据和信息的话，移动数据库也会自动加载这些新信息，确保了移动数据库和 中- t x , n 务器数据库之间的数据同步。 1 3 移动数据库的发展与应用 1 3 1 数据挖掘技术产生背景 随着信息技术的高速发展，人们积累的数据量急剧增长：从现代的信息传播 途径网络的信息量来看，据统计，目前，我国手机用户约为4 8 亿【7 】，手机 上网用户总量已经超过8 0 0 0 万人i 引，互联网用户从1 9 9 9 年初的2 1 0 万到现在的 约为1 亿，跃居世界第二l 引，截止到2 0 0 7 年5 月，全国已经推出和正在实施的 网络报纸的报社共有8 8 家，报纸达2 5 0 种，全国4 5 0 多家出版社出版的电子书 已经达到了3 0 多力种，已成为全球单一语种最大的电子书库【9 j o 随着数据库技 术的迅速发展以及数据库管理系统的广泛应用，人们积累的数据越来越多。大量 信息在给人们带来方便的同时也带来了一大堆问题：第一是信息过量，难以消化： 第二是信息真假难以辨识；第三是信息安全难以保证；第四是信息形式不一致， 难以统一处理。 激增的数据背后隐藏着许多重要的信息，人们希望能够对其进行更高层次的 分析，以便更好地利用这些数据。目前的数据库系统可以高效地实现数据的录入、 查询、统计等功能，但无法发现数据中存在的关系和规则，无法根据现有的数据 预测未来的发展趋势。缺乏挖掘数据背后隐藏的知识的手段，导致了“数据爆炸 但知识贫乏”的现象。 如何从海量的数据中提取有用的知识成为当务之急。数据挖掘( d a t am i n i n g ) 就是为顺应这种需要应运而生发展起来的数据处理技术，是知识发现 ( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ) 的关键步骤。数据挖掘技术是人们长期对数 据库技术进行研究和开发的结果。 1 3 2数据挖掘技术发展 数据挖掘其实是一个逐渐演变的过程，电子数据处理的初期，人们就试图通 过某些方法来实现自动决策支持，当时机器学习成为人们关心的焦点。机器学习 的过程就是将一些已知的并己被成功解决的问题作为范例输入计算机，机器通过 6 第一章绪论 学习这些范例总结并生成相应的规则，这些规则具有通用性，使用它们可以解决 某一类的问题。随着神经网络技术的形成和发展，人们的注意力转向知识工程， 知识工程不同于机器学习那样给计算机输入范例，让它生成出规则，而是直接给 计算机输入已被代码化的规则，而计算机是通过使用这些规则来解决某些问题。 专家系统就是这种方法所得到的成果，但它有投资大、效果不甚理想等不足。8 0 年代人们又在新的神经网络理论的指导下，重新回到机器学习的方法上，并将其 成果应用于处理大型商业数据库。随之在8 0 年代末产生了一个新的术语，它就 是数据库中的知识发现，简称k d d ( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ) ，它泛指 所有从源数据中发掘模式或联系的方法，人们接受了这个术语，并用k d d 来描 述整个数据发掘的过程，包括最开始的制定业务目标到最终的结果分析，而用数 据挖掘来描述使用挖掘算法进行数据挖掘的子过程。但最近人们却逐渐开始使用 数据挖掘中有许多工作可以由统计方法来完成，并认为最好的策略是将统计方法 与数据挖掘有机的结合起来。 起初各种商业数据是存储在计算机的数据库中的，然后发展到可对数据库进 行查询和访问，进而发展到对数据库的即时遍历。数据挖掘使数据库技术进入了 一个更高级的阶段，它不仅能对过去的数据进行查询和遍历，并且能够找出过去 数据之间的潜在联系，从而促进信息的传递。现在数据挖掘技术在商业应用中已 经可以马上投入使用，因为对这种技术进行支持的三种基础技术：海量数据搜集、 强大的多处理器计算机、数据挖掘算法已经发展成熟。 数据挖掘的核心模块技术历经了数十年的发展，其中包括数理统计、人工智 能、机器学习。今天，这些成熟的技术，加上高性能的关系数据库引擎以及广泛 的数据集成，让数据挖掘技术在当前的数据仓库环境中进入了实用的阶段。 1 3 3 数据挖掘技术的应用及前景 目前，在很多领域，数据挖掘都有广泛的应用，尤其是在如银行、电信、保 险、交通、零售( 如超级市场) 等商业领域。数据挖掘所能解决的典型商业问题 包括：数据库营销( d a t a b a s em a r k e t i n g ) 、客户群体划分( c u s t o m e rs e g m e n t a t i o n & c l a s s i f i c a t i o n ) 、背景分析( p r o f i l ea n a l y s i s ) 、交叉销售( c r o s s s e l l i n g ) 等市 场分析行为，以及客户流失性分析( c h u ma n a l y s i s ) 、客户信用记分( c r e d i t s c o r i n g ) 、欺诈发现( f r a u dd e t e c t i o n ) 等等。 1 在市场营销中的应用 数据挖掘技术在企业市场营销中得到了比较普遍的应用，通过收集、加工和 处理涉及消费者消费行为的大量信息，确定特定消费群体或个体的兴趣、消费习 惯、消费倾向和消费需求，进而推断出相应消费群体或个体下一步的消费行为， 7 第一章绪论 然后以此为基础，对所识别出来的消费群体进行特定内容的定向营销，这与传统 的不区分消费者对象特征的大规模营销手段相比，大大节省了营销成本，提高了 营销效果，从而为企业带来更多的利润。 商业消费信息来自市场中的各种渠道。例如，每当我们用信用卡消费时，商 业企业就可以在信用卡结算过程收集商业消费信息，记录下我们进行消费的时 间、地点、感兴趣的商品或服务、愿意接收的价格水平和支付能力等数据：当我 们在申办信用卡、办理汽车驾驶执照、填写商品保修单等其他需要填写表格的场 合时，我们的个人信息就存入了相应的业务数据库；企业除了自行收集相关业务 信息之外，甚至可以从其他公司或机构购买此类信息为自己所用。这些来自各种 渠道的数据信息被组合，应用超级计算机、并行处理、神经元网络、模型化算法 和其他信息处理技术手段进行处理，从中得到商家用于向特定消费群体或个体进 行定向营销的决策信息。 2 在商业银行中的应用 数据挖掘技术在美国银行金融领域应用广泛。金融事务需要搜集和处理大量 数据，对这些数据进行分析，发现其数据模式及特征，然后可能发现某个客户、 消费群体或组织的金融和商业兴趣，并可观察金融市场的变化趋势。商业银行业 务的利润和风险是共存的。为了保证最大的利润和最小的风险，必须对账户进行 科学的分析和归类，并进行信用评估。 当前，数据挖掘知识发现( d a t am i n i n gk n o w l e d g ed i s c o v e r y ，d m k d ) 研 究方兴未艾，预计研究将在以下几个方面集中： ( 1 ) 发现语言的形式化描述，即研究专门用于知识发现的数据挖掘语言，也 许会像s q l 语言一样走向形式化和标准化； ( 2 ) 寻求数据挖掘过程中的可视化方法，使知识发现的过程能够被用户理 解，也便于在知识发现的过程中进行人机交互； ( 3 ) 研究在网络环境下的数据挖掘技术( w e bm i n i n g ) ，特别是在因特网上 建立d m k d 服务器，并且与数据库服务器配合，实现w r e bm i n i n g ； ( 4 ) 加强对各种非结构化数据的挖掘( d a t am i n i n gf o r a u d i o v i d e o ) ，如对 文本数据、图形数据、视频图像数据、声音数据乃至综合多媒体数据的挖掘；处 理的数据将会涉及到更多的数据类型，这些数据类型或者比较复杂，或者是结构 比较独特。为了处理这些复杂的数据，就需要一些新的和更好的分析和建立模型 的方法，同时还会涉及到为处理这些复杂或独特数据所做的费时和复杂数据准备 的一些工具和软件。 ( 5 ) 交互式发现； ( 国知识的维护更新。 8 第一章绪论 只有从数据中有效地提取信息，从信息中及时地发现知识，才能为人类的思 维决策和战略发展服务。 就目前来看，将来的几个热点包括网站的数据挖掘( w e bs i t ed a t am i n i n g ) 、 生物信息或基因( b i o i n f o r m a t i c s g e n o m i c s ) 的数据挖掘及其文本的数据挖掘 ( t e x t u a lm i n i n g ) 。 1 网站的数据挖掘( w e bs i t ed a t am i n i n g ) 随着w e b 技术的发展，各类电子商务网站风起云涌，建立起一个电子商务 网站并不困难，困难的是如何让您的电子商务网站有效益。要想有效益就必须吸 引客户，增加能带来效益的客户忠诚度。电子商务业务的竞争比传统的业务竞争 更加激烈，原因有很多方面，其中一个因素是客户从一个电子商务网站转换到竞 争对手那边，只需点击几下鼠标即可。网站的内容和层次、用词、标题、奖励方 案、服务等任何一个地方都有可能成为吸引客户、同时也可能成为失去客户的因 素。而同时电子商务网站每天都可能有上百万次的在线交易，生成大量的记录文 件( l o gf i l e s ) 和登记表，如何对这些数据进行分析和挖掘，充分了解客户的喜 好、购买模式，甚至是客户一时的冲动，设计出满足于不同客户群体需要的个性 化网站，进而增加其竞争力，几乎变得势在必行。若想在竞争中生存进而获胜， 就要比您的竞争对手更了解客户。 在对网站进行数据挖掘时，所需要的数据主要来自于两个方面：一方面是客 户的背景信息，此部分信息主要来自于客户的暨记表；而另外一部分数据主要来 自浏览者的点击流( c l i c k s t r e a m ) ，此部分数据主要用于考察客户的行为表现。 但有的时候，客户对自己的背景信息十分珍重，不肯把这部分信息填写在登记表 上，这就会给数据分析和挖掘带来不便。在这种情况之下，就不得不从浏览者的 表现数据中来推测客户的背景信息，进而再加以利用。 就分析和建立模型的技术和算法而言，网站的数据挖掘和原来的数据挖掘差 别并不是特别大，很多方法和分析思想都可以运用。所不同的是网站的数据格式 有很大一部分来自于点击流，和传统的数据库格式有区别。因而对电子商务网站 进行数据挖掘所做的主要工作是数据准备。目前，有很多厂商正在致力于开发专 门用于网站挖掘的软件，研究领域也有很多对网络日志挖掘算法的创新和改进 0 0 1 0 2 生物信息或基因( b i o i n f o r m a t i c s g e n o m i c s ) 的数据挖掘 生物信息或基因数据挖掘则完全属于另外一个领域，在商业上很难讲有多大 的价值，但对于人类却受益非浅。例如，基因的组合千变万化，患某种病的人的 基因和正常人的基因到底差别多大，能否找出其中不同的地方，进而对其不同之 处加以改变，使之成为正常基因，这都需要数据挖掘技术的支持。 9 第一章绪论 对于尘物信息或基因的数据挖掘和通常的数据挖掘相比，无论在数据的复杂 程度、数据量还有分析和建立模型的算法而言，都要复杂得多。从分析算法上讲， 更需要一些新的和好的算法。现在很多厂商证在致力于这方面的研究。但就技术 和软件而言，还远没有达到成熟的地步。 3 文本的数据挖掘( t e x t u a lm i n i n g ) 人们很关心的另外一个话题是文本数据挖掘。举个例子，在客户服务中心， 把同客户的谈话转化为文本数据，再对这些数据进行挖掘，进而了解客户对服务 的满意程度和客户的需求以及客户之问的相互关系等信息。从这个例子可以看 出，无论是在数据结构还是在分析处理方法方面，文本数据挖掘和前面谈到的数 据挖掘相差很大。文本数据挖掘并不是一件容易的事情，尤其是在分析方法方面， 还有很多需要研究的专题。目前市场上有一些类似的软件，但大部分方法只是把 文本移来移去，或简单地计算一下某些词汇的出现频率，并没有真正的分析功能。 随着计算机计算能力的发展和业务复杂性的提高，数据的类型会越来越多、 越来越复杂，数据挖掘将发挥出越来越大的作用。 1 4 本课题主要研究内容及论文结构 本文对移动数据库的各种数据广播策略进行分析，提出用数据挖掘中的聚类 方法将待广播的数据进行分类和排序，利用数据挖掘中分类和预测的功能特点实 现更具有实用性的数据广播算法。其中数据挖掘的聚类方法使用的是文献【1 1 】中 提出的c u r e 算法，本文中对此算法进行了改进，作为一个创新点，使用取样 和增量共同提供数据源，提高了执行的效率和准确性。 本文共有五章组成。第一章为绪论，共分为四个小节。其中第一小节介绍本 课题的背景和研究意义，第- - + 节叙述本课题研究领域，即移动数据库和数据挖 掘技术中重要技术和使用方法的发展与应用现状，第三小节介绍了本课题研究的 主要内容和创新点，第四小节介绍了论文的总体结构；本文第二章为研究综述， 共分为两个小节。其中第一小节为移动数据库的关键技术发展，第- d , 节介绍数 据挖掘技术，对这两部分内容的介绍是对其后的研究所做的理论基础学习，是课 题研究的基础；第三章为主要数据模型及算法简介，共分为两个小节。其中第一 小节介绍了本课题的第一个创新点，即c u r e 算法在动态数据广播策略中的应 用，第二小节介绍了本课题的第二个创新点，即应用最邻近算法实现动态数据的 增量分析，对c u r e 算法进行改进；第四章为时间方面应用和设计，共分为两 个小节。其中第一小节描述了应用系统实现的分析，对数据的格式和系统的功能 进行概括，第二小节详细说明了一下应用系统的实现流程、数据对象和操作对象， 展示了实现的应用系统的界面样式。第五章为总结，共分为两个小节。其中第一 1 0 第一章绪论 小节对本论文中课题研究的内容进行了总结，并计划出下一步的研究工作，第二 小节介绍了对移动数据库应用前景的展望，描述了移动数据库在各个领域内的广 阔发展前景。 第一章移动数据库及数据挖掘的关键技术 第二章移动数据库及数据挖掘的关键技术 21 移动数据库的关键技术发展 211移动计算环境体系结构 l 移动训算环境的典型体系结构 移动计算环境的典型体系结构如图2 - 1 其中，固定的网络部分构成连接固 定节点的骨t ，它是由多个同定主机服务器( f i x e dh o s l ，简称f h ) 和移动服 务支持节点( m o b i l e s e r v e rs t a t i o n ，简称m s s ) 组成，每个m s s 负责建立个 无线网络单元，无线单元内的移动设备( m o b i l eu n i t ，简称m u ) 或移动计算 机( m o b i l ec o m p u t e r ，又叫移动客户机，m o b i l ec l i e n t ，简称m c ) 与m s s 之 间是通过无线网络连接的。i 。 自，自r 自自 t ，w 图2 - 1 移动计算环境的典型结构 现在使用的无线通信方式有卫星通信系统、蜂窝系统、微波技术、无线局 域网、蓝牙、无线保真( w i r e l e s sf i d e l i t y ，w i f i ) 、红外线等。采用不同的尤 线通信技术。无线单元所能覆盖的范围和数据传输率不同。如卫星通信系统的 个单元直径可以超过4 0 0 英里；蜂窝系统发射器的信号覆盖范围直径为几英 扣 第二章移动数据库及数据挖掘的关键技术 里，最大数据传输率为几十k b p s ：微波通信距离一般在5 0 公里；无线局域网、 蓝牙、w i f i 、红外线同属短距离通信，通常传输距离在几十米以内，数据传输 率在2 1 0 m b p s 。它们普遍具有低成本和低功耗的特点，而且随着便携式消费电 器和通信设备的普及，无线网络正在不断向无线网络单元的小型化发展。 2 移动计算系统体系结构模型 在传统的分布式计算环境中，基本的体系结构是c l i e n t s e r v e r ( c s ) 结构， 这种结构要求客户端与服务器端必须是通过有线网络连接，而且这种连接是固 定的，不能够有断连，它的优点是稳定，而且带宽较高。但是在移动计算环境 中，频繁的断连是不可避免的，因此这种c s 结构已经不再适用。为了适应移 动计算环境的需要，c m u 研究小组提出了扩展的c l i e n t s e r v e r 体系结构1 1 3 l 。移 动客户机不仅有客户机自身的代码，而且还保存服务器代码，在发生断连时， 服务器代码就能够在客户机端模拟服务器的功能，保证客户机在断连期问能够 继续工作；同时，由于客户机的资源相对有限( 如计算能力、存储容量等) ，服 务器中也有客户机代码，可以帮助客户机运行比较复杂的计算。由于这样的结 构是对有线网络系统的体系结构的改进，必然带有在固定网络中很容易处理， 但在移动环境中却影响很大的缺点，比如带宽耗费严重、网络负载不均衡、容 错能力差。 我们可以发现移动计算环境中移动客户机和固定服务器之间的信息交换要 通过m s s ，在m s s 上设置一个软件作为代理( a g e n t ) ，这就是c l i e n t a g e n t s e r v e r 体系结构，此代理为m s s 所覆盖的无线单元内所有的移动客户机服务。这种结 构相对减少了无线连接条件下有限带宽和弱可靠性对访问效率的影响。a g e n t 的接口可以分为c l i e n t a g e n t 和a g e n t s e r v e r 两部分，它们可以采用不同的通信 协议，具有良好的兼容性。 根据不同的应用类型和移动设备的资源，a g e n t 可以有不同的功能，总体 来说，a g e n t 最基本的功能就是在移动客户机和a g e n t 之间支持消息和队列通 信机制。另外，a g e n t 也具有如下功能： ( 1 ) a g e n t 可以缓存固定服务器中的部分数据为客户机服务，减少客户机请 求的延时并减轻服务器的负担。 ( 2 ) a g e n t 可以完成对客户机而言相对复杂的任务，客户机可以把任务转交 到a g e n t 到，在固定服务器端执行，最后把结果传送给客户机。 ( 3 ) a g e n t 可以在把数据传送给服务器之前帮助服务器执行如数据压缩、数 据校验等任务 。 ( 4 ) a g e n t 可以负责收集和监控客户机的各种状态信息，如移动客户机缓存 的数据、当前的位置、是否断连等。 1 3 第二章移动数据库及数据挖掘的关键技术 但是，固定a g e n t 也存在缺点：它只能优化从固定网络到移动客户机的数 据传送，而且在断连的情况下客户机不能继续工作。 移动a g e n t 体系结构是一个可以在异构网络主机之间自主迁移和独立运行 的计算机程序。区别于前几种系统结构的最大特点就是动态性。为完成特定的 任务，移动a g e n t 会寻找合适的计算资源、信息资源或软件资源，利用与这些 资源同处于一台主机或子网的优势，处理或使用这些资源，代表用户完成特定 的任务，计算结束后把结果传回给发送节点或其他指定的节点。移动a g e n t 必 须满足位置透明性、可靠性、高效性、异步性和自适应性。 移动a g e n t 结构具有如下的优点： ( 1 ) 移动性能：移动a g e n t 可以在异构网络和分布式计算机环境中自主、自 动地迁移，携带信息或寻找适当的信息资源，进行就地的信息处理，代理用户完 成信息传递、网页查询、数据和知识发现、信息变换等多种任务。 ( 2 ) 异构和异步性能：移动a g e n t 可以支持异构计算机软件、硬件环境，能 进行异步通讯和计算，即一旦移动a g e n t 从客户端传输到另一台主机上，这台 机器就可以和网络断开连接，直到回收a g e n t 或再次发送a g e n t 。 ( 3 ) 降低网络通讯费用：传送大量的原始信息不但费时还容易阻塞网络， 如果将a g e n t 移动到信息存储的地方，进行局部搜索和选择后，将选中的信息 通过网络传送给用户，会大大减少远程计算机网络的连接费用，节省宝贵的无 线网络带宽。 ( 4 ) 分布和并行性：移动a g e n t 提供了一个独特的分布计算体系结构，为完 成某项任务，用户可以创建多个a g e n t ，将它们 同时在相同或不同的节点上运 行，可将单一节点的负荷分散到网络的多个节点上，以维持最优配置，优化网 络性能，使小系统具有处理大规模、复杂问题的能力。 ( 5 ) 智能化路由：移动a g e n t 具有根据目标、网络通讯能力和服务器负载等 因素，动态地规划下一步操作的能力。智