（计算机应用技术专业论文）电子商务环境中分布式数据挖掘的研究.pdf

武汉理工大学博士学位论文 摘要 现代新兴商业模式的电子商务的蓬勃发展，使得i n t e r n e t 上的资源和服务 更加丰富多彩，这些丰富的资源和服务每天都会产生许多新的、蕴涵着大量 重要信息的海量数据，这些数据往往是异构的、不确定性的和非结构化的， 其复杂程度已远远超出了人类目前己有的分析和理解能力。因此，研究有效 利用这些复杂资源的新技术，数据挖掘具有重要的现实意义。就信息处理而 言，数据挖掘是致力于数据分析和理解数据内部蕴藏知识的技术，它成为未来 信息技术应用的重要目标之一。 本文在对分布式数据挖掘、w e b 服务及a g e n t 相关技术进行了分析的基础 上，为解决电子商务环境中分布式数据挖掘的核心问题，从关键算法和架构 两个方面进行了深入研究。 针对七最近邻搜索算法存在的问题，提出了电子商务环境中一种自适应的 基于p 2 p 的k 最近邻搜索算法p 2 p a k n n s 。探讨了度量空间、相似性查询和 g h t * 规则，自定义了高维数据的相似度函数h d s f ( x ，l ，) ，论述了g i r l * 中 插入算法及范围查找算法和搜索算法。在此基础上，具体给出了p 2 p a k n n s 算 法的实现方法，并通过实验，验证了其正确性。 同时本文对d e n c l u e 算法进行了研究，为使其适合电子商务环境、解决 其存在问题，结合p 2 p a k n n s 算法的优点，提出了电子商务环境中基于距离 和密度的无监督聚类算法k n d c 。论述了模糊簇的划分及参数k ，讨论了参数 o r 和善的设置，给出了k n d c 算法的具体实现方法，并予以验证。 本文还针对电子商务环境中分布式数据挖掘的关联规则，在研究a p 由r i 关联规则算法、多重最小支持度a p r i o r i 算法、相关支持度a p r i o r i 算法r s a a 、 平均项目集合分割法的基础上，改进了阈值的制定方法；为提高挖掘有价值 的稀有数据的效率和精确度，根据r s a a 和基于无向项集图算法b o u i g a 提 出了r s 从b o u i g a 算法，分析了其正确性。 在此基础上，结合业界和学术界对w e b 服务和移动a g e n t 的研究成果，将 w e b 服务和a g e n t 最新技术引入了电子商务环境中分布式数据挖掘，提出了电 子商务环境下基于w e b 服务和移动a g e n t 技术的数据挖掘架构b w a d m ，并 武汉理工大学博士学位论文 论述了组合服务规范与组合服务的执行，具体阐述了此架构的数据预处理组 件、算法管理组件、控制中心组件、算法库组件和模型表示组件。 最后建立了b w a d m 原型，结合w e b 服务技术，给出了基于w e b 服务的 数据挖掘系统逻辑结构，设计并实现了该系统，验证了b w a d m 的合理性和 上述算法在效率、精确度等方面的优越性。 关键词：k 最近邻，模糊簇，阈值，稀有数据，架构 武汉理工大学博士学位论文 a b s t r a c t t h ee x p l o s i v eg r o w t ho fe l e c t r o n i cc o m m e r c em a k e st h er e s o u r c e sa n ds e r v i c e s m o r ep l e n t i f u lw i t hc u r r e n t 丘佗一n c wb u s i n e s so ni n t e r n e t e v e r y d a yt h e s er i c h r e s o u r c e sa n ds e r v i c e s g e n e r a t e v o l u m e so f h e t e r o g e n e o u s ， u n c e r t a i n , a n d u n s t r u c t u r e dd a t aw h i c hs oc o m p l e x i t yt h a tf a rb e y o n dh u m a n sc u r r e n tc a p a c i t yt o i n t e r p r e t i n ga n dd i g e s t i n gt h e m h e n c e ，i ti sp r a c t i c a li m p o r t a n tt od e v e l o ps o m e n e wt e c h n i q u e sf o rm a k i n gu s eo ft h e s ev a l u a b l ec o m p l e x i t yr e s o u r c e ss u f f i c i e n c y d a t am i n i n gi sat e c h n i q u et h a ta i m st oa n a l y z ea n du n d e r s t a n dl a r g es o n l - c ed a t aa n d r e v e a lk n o w l e d g eh i d d e ni nt h ed a t a i th a sb e e nv i e w e da sa l li m p o r t a n te v o l u t i o ni n i n f o r m a t i o np r o c e s s i n g k e ya l g o r i t h m sa n da r c h i t e c t u r ea r er e s e a r c h e dt os o l v et h ec o r ep r o b l e m so f d i s t r i b u t e dd a t am i n i n gi ne l e c t r o n i cc o n l m e r c ee n v i r o n m e n ta f t e rd i s t r i b u t e dd a t a m i n i n g , w c bs e r v i c e sa n da g e n tt e c h n o l o g ya r ca n a l y z e da n ds u m m e d 叩i nt h e p a p e r f i r s t l y , a na d a p t i v ed i s t r i b u t e da l g o r i t h mc a l l e dp 2 p a k n n sf o rp 2 pk - n e a r e s t n e i g h h e rs e a r c hi nh i g hd i m e n s i o n si sp r o p o s e dt os o l v et h es h o r t c o m i n g so fk n - si n e l e c t r o n i cc o m m e r c ee n v i r o n m e n t m e t r i cs p a c e ，s i m i l a r i t yq u e r i e sa n dp r i n c i p l e s o fg h t a r cd i s c u s s e d s i m i l a r i t ym e a s u r ef u n c t i o nh d s f ( x ，ni sg i v e i n s e r t ， r a n g ef i n da n ds e a r c ha l g o r i t h m si ng h t + a r c d i s c u s s e d t h ed e t a i l e dp 2 p a k n n s a l g o r i t h mi sg i v e na n dd i s c u s s e dw i t he x p e r i m e n t s e c o n d l y ，d e n c l u ei sa n a l y z e d i no r d e rt os o l v ei t ss h o r t c o m i n g sa n db e a p p l i e di n e l e c t r o n i cc o m m e r c ee n v i r o n m e n t ，an e wc l u s t e r i n ga l g o r i t h mo f d i s t r i b u t e dd a t am i n i n gb a s e do np 2 p a k n n sa n dd e n c l u ec a l l e dk n d ci s p r o p o s e df o re l e c t r o n i cc o m m e r c ee n v i r o n m e n t f u z z yc l u s t e r sd i v i s i o n ，p a r a m e t e r k p a r a m e t e r da n d 亭a r ed i s c u s s e d , t h ed e t a i l e da l g o r i t h mi sg i v e na n dd i s c u s s e d w i t he x p e r i m e n t t h i r d l y ，t h e s ea s s o c i a t i o nr u l e sa l g o r i t h m so fd a t am i n i n ga r ei n t r o d u c e dd e t a i l e d l y ， t h e ya r ea p r i o r ia l g o r i t h m ，r e l a t i v es u p p o r ta p r i o da l g o r i t h m , m e a ni t e m s e td i v i d e m 武汉理工大学博士学位论文 m e t h o d ，t h em e t h o do ft h r e s h o l d ss e t t i n g si si m p r o v e d r s a a - b o u i g aa l g o r i t h m i sp r o p o s e dt oi m p r o v et h ep r e c i s i o na n de f f i c i e n c yo fv a l u a b l er a r ed a t am i n i n g a c c o r d i n gt ob o u i g a a n dr s a aa l g o r i t h m t h e n ，a f t e rr e v i e w i n gf o r m e rr e s e a r c h ，w ec o m b i n et h es o l u t i o no fi n d u s t r ya n d a c a d e m y ，an e wa r c h i t e c t u r ec a l l e d b w a d mb a s e do nt h er e s e a r c h e sa b o v ei s p r o p o s e d , i ti sad i s t r i b u t e dd a t am i n i n gs y s t e mb a s e do nw e b s e r v i c e sa n da g e n ti n e l e c l r o n i cc o m n i l e r c oe n v i r o n m e n t w e bs e r v i c ec o m p o s i t i o nr u l e sa n de x e c u t i o no f w e bs e r v i c ec o m p o s i t i o na r ed i s c u s s e d t h e s em o d u l e sa r ei n t r o d u c e dd e t a i l e d l yi n e l e c t r o n i cc o m m e r c ee n v i r o n m e n t ；t h e r ea r ea l g o r i t h mm a n a g e m e n tm o d u l e ，c o n t r o l c e n t e rm o d u l e ，a l g o r i t h md a t a b a s em o d u l ea n dm o d e lr e p r e s e n t a t i o nm o d u l e l a s t l y , ap r o t o t y p es y s t e mo fd i s t r i b u t e dd a t am i n i n gi sg i v e ni n e l e c t r o n i c c o m m e r c e t h el o g i cs t r u c t u r eo fd a t am i n i n gs y s t e mb a s e do nw e bs e r v i c e si s p r o p o s e da c c o r d i n gt ow e bs e r v i c e st e c h n o l o g y ；t h ep r o j e c to f d a t am i n i n gb a s e d o nw e bs e r v i c e si sd e s i g n e da n di m p l e m e n t e d t h e s ep r o v et h er e a s o n a b l e n e s so f b w a d ma n da b o v et h e s ea l g o r i t h m sa r em o r ee f f i c a c i o u sa n dp r e c i s et h a n c u r r e n ta l g o r i t h m s k e yw o r d s ：k - n e a r e s tn e i g h b o r , f u z z yo u s t e r s ，t h r e s h o l d ，r a r ed a t a ，a r c h i t e c t u r e i v 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得武汉理工大学或其它教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 关于论文使用授权的说明 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即学校有权 保留、送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部 或部分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 日期：刎 f 武汉理工大学博士学位论文 1 1 研究背景及意义 第1 章绪论 当今时代是网络化、信息化的时代，i n t e r a c t 在全球迅速扩张，并且逐渐渗 透到社会的各个领域。人们利用它可以方便地收发邮件、浏览网页、聊天、下 载软件、购买商品等等。针对i n t e r n e t 上涌现出的这些商机，许多企业纷纷把自 己的业务转移至l j i n t e m e t 上，建立自己的网站，实现各种商业活动，这便是电子 商务。 电子商务让企业和客户通过网络交互，取代了传统的面对面的交互方式。 由于i n t e r a c t 的普及与便利，电子商务企业要面对的客户群是巨大而复杂的，市 场也变得更大、更复杂。这个时候，一方面企业比以往更加期望能够对用户和 市场进行把握，而电子商务企业对市场和客户的知识往往是非常缺乏的；另一 方面，电子商务在运转的过程中又积累了大量有关用户本身和用户商务行为的 数据，电子商务企业面临数据丰富、知识贫乏的尴尬。 数据挖掘，也称知识发现，被描述为从数据中抽取出隐含的、具有潜在用 途的、人类可理解的模式。数据挖掘通过发现有用的新规律和新概念，提高了 数据拥有者对大量原始数据的深层次理解、认识和应用。数据挖掘技术是目前 国际上数据库和信息决策领域最前沿的研究方向之一，引起了学术界和工业界 的广泛关注【1 1 。数据挖掘是一个多学科交叉的新兴研究领域，在这个新兴领域中， 汇集了来自机器学习、模式识别、数据库、统计学、人工智能以及管理信息系 统等各学科的成果i 删。多元化的投入，使得这一学科得以蓬勃发展，而且已初 具规模。除学术上的需要外，极大的商业应用前景更是推动数据挖掘研究不断 深入的关键因素i z j 。 将数据挖掘技术应用于电子商务，对这些数据进行挖掘，就可以找出这些 有价值的“知识”。企业用户可以根据这些“知识”，把握客户动态，追踪市场 变化，做出正确的针对性的决策，比如改进网站、向各类用户推出个性化的页 面，或者向高流失客户群提供优惠政策进行挽留等等。因此，发掘电子商务系 统积累的大量数据，将使企业能够及时应对市场变化、占领市场的制高点，在 武汉理工大学博士学位论文 电子商务平台上进行数据挖掘就成为一个研究热点p j 。 电子商务是基于i n t e r n e t i n t r a n e t 或局域网、广域网，包括了从销售、市场到 商业信息管理的全过程。在电子环境中，许多大型数据库都是以分布的形式存 在的。随着w w w 应用的日趋普及，i n t e r n e t 已成为当今世界最大的分布数据源， i n t e r n e t 中的数据正以几何级数增长，而且i n t e r a c t 本身就是一个巨大的分布式系 统。如何应用计算机网络中的庞大数据资源，发现和获取其中有价值的知识， 已经成为人们必须正视的问题。而分布式数据挖掘是在电子商务环境中发现和 获取有用知识的最佳方法之一。分布式数据挖掘为从“数据海洋”中开采有用 的知识提供了有效途径，它将在金融投资、电信、市场营销、气象和灾难预报、 科学决策、i n t e r n e t 信息浏览等方面发挥巨大作用，具有广阔的应用前景i 硎。 1 2 国内外研究现状与分析 1 2 1 研究现状简述 随着通信和计算机网络技术的飞速发展以及i n t e m e t 的普及，使得商业空间 发展到全球规模成为可能，电子商务就是为了适应这种以全球为市场的变化而 发展起来的一种商业模型。但是在电子商务系统中，通常面临着以下问题1 4 j ：( 1 ) 随着互联网的普及和电子商务的发展，电子商务系统在为用户提供越来越多选 择的同时，其结构也变得更加复杂，用户如何才能不会迷失在大量的商品信息 空间中，顺利找到自己需要的商品? ( 2 ) 商家如何投其所好，为用户实现主动 推荐，提供个性化服务? ( 3 ) 企业如何根据用户的访问规律，快速调整企业的 经营管理策略，留住老客户，挖掘潜在客户，寻找新的商机? ( 4 ) 企业如何适 应市场的变化，并进一步优化网站组织结构和服务方式，以提高网站的效率? 电子商务网站的后台数据库中丰富的数据资源包含了对市场分析及预测非常有 益的潜在信息，如何进行充分的挖掘和利用意义重大。由此，电子商务数据挖 掘应运而生，前景广阔【1 1 将数据挖掘技术与电子商务结合起来，进行电子商务方面的数据挖掘，可 以帮助人们更有效地从电子商务网站数据中获取有用的信息。然而电子商务环 境下的数据挖掘与传统的数据挖掘相比有很多不同之处，电子商务下的数据挖 掘的对象是大量异构的、分布的、半结构化的数据，其自身的特殊性决定了在 数据挖掘之前必须进行数据预处理1 4 j 。研究电子商务环境下的数据挖掘技术，并 2 武汉理工大学博士学位论文 将它用于商业站点的开发，对发现电子商务智能性、提高站点实施的促销效果 等决策具有实际的意义1 2 】。分析互联网背后的用户行为，获取用户的行为模式， 进而调整页面的结构设计，推荐用户最可能感兴趣的商品，预测用户的行为， 为用户提供更好的服务，给商业站点带来利润。对于一个电子商务公司每天搜 集和处理的大量数据，利用数据挖掘技术可以帮助他们高度自动化地分析数据， 做出归纳性推理，从中挖掘出潜在的模式，并预测未来，帮助企业决策者调整 市场策略，减少风险，做出正确决策，从而给公司带来巨大的利润。 在电子商务中使用数据挖掘技术可以发现隐藏知识，提高企业竞争力。越 来越多的企业使用数据挖掘来加强电子商务系统的智能，许多企业都在其具体 的应用中使用数据挖掘技术。目前，以电子商务应用为背景的数据挖掘和知识 发现的研究，主要是根据商业中对条码机数据的分析，发现顾客购物规律，采 用的数据主要是w e b 日志。通过对大量事务数据的挖掘以产生有益于买卖双方 的概要信息、客户分析和事务规则，这在电子商务中变得日益重要i 删。例如， 客户的购物行为模式源自客户分析而被用作引导个性化市场、发展新客户、发 掘商机和探测商业诈骗行为；事务规则被用来解释销售陡然升降的内因、分析 商业走势等等。利用数据挖掘技术建立电子商务推荐系统，公司通过分析大量 的交易记录，可以预测用户未来的购买需要，向用户推荐其可能感兴趣的商品。 实际上，电子商务推荐系统能够直接与用户交互，模拟商品销售人员向用户提 供商品推荐，帮助用户找到所需商品，从而顺利完成购买过程。从用户角度来 看，通过对收集到的用户的访问行为、访问频度、访问内容等浏览信息进行挖 掘，提取用户的特征，获取用户访问w e b 的模式，为用户实现主动推荐，提供 个性化服务；从企业角度来看，企业希望能够获取用户的访问规律，以帮助企 业确定顾客消费的生命周期，针对不同的产品制定相应的营销策略、进一步优 化网站的组织结构和服务方式，以提高网站的效率在日趋激烈的竞争环境下， 电子商务推荐系统能够实现个性化服务，从而有效保留用户，防止用户流失， 提高系统的销售。推荐系统在电子商务系统中具有良好的发展和应用前景，逐 步成为电子商务信息技术的一个重要研究内容，得到越来越多研究者的关注， 为电子商务建立以数据挖掘为核心的客户关系管理系统，挖掘电子商务系统积 累的大量数据，将使企业能够及时应对市场变化，占领市场的制高点阳。 在电子商务中，数据挖掘的方法虽然多种，但主要是三种，即协同过滤、 聚类分析、关联规则m 。协同过滤技术主要采用最近邻技术，利用客户的历史 3 武汉理工大学博士学位论文 喜好信息计算客户之间的距离，目标客户对特定商品的喜好程度由其最近邻居 对商品评价的加权平均值来计算。k 最近邻法( k n n ) 是一个理论上比较成熟 的方法，在电子商务数据挖掘中有广泛的用途。k n n 查询是多媒体数据库管理 系统中最具代表性的查询方式之一，它将七个与查询点最接近的对象作为查询结 果返回【6 8 1 ，它是向量空间模型中最好的文本分类算法之一【叫。数据分类技术是 一种强有力的分析手段，它旨在生成一个分类函数或分类模型，由该模型把数 据库中的数据项映射到某一给定类别中。现有的数据分类算法大体可以划分为 两大类：积极学习方法与消极学习方法。由于消极方法使用很多不同的局部线 性函数来形成对目标函数隐含的全局逼近，具有比积极方法更丰富的假设空间。 其中消极学习型中应用最广泛的是七最近邻法1 7 州。k n n 的优点是易于快速实现， 分类效果好。同时它也存在一些限制，比如存储训练例子的数量问题、相似性 度量问题等1 “j 。 聚类是电子商务数据挖掘中一门非常有用的技术，可以用于从大量数据中 寻找隐含的数据分布和模式。通过聚类，将数据划分为若干类，然后在每一类 中寻找模式和各种潜在的有用信息【7 l 】。聚类分析可以帮助市场人员发现顾客群 中所存在的不同特征的组群，并可以利用购买模式来描述这些具有不同特征的 顾客组群。最近邻( k n n ) 算法可以快速进行聚类并且能有效处理噪声点，但当 数据密度和聚类间的距离不均匀时聚类质量较差【诩。在电子商务数据挖掘的常 用聚类算法中，d e n c l u e 是一种优良的算法。它能够识别各种复杂形状的聚 类，能有效排除噪声干扰，并且聚类结果不受输入顺序的影响。但是其参数 需要人工来确定，需要大量的内存，同时影响精度和效率1 7 ”。 关联规则挖掘是电子商务数据挖掘中最活跃的研究方法之一。最早是由 a g r a w a l 等人提出的。最初提出的动机是针对购物篮分析问题提出的，其目的是 为了发现交易数据库中不同商品之间的联系规则，这些规则刻画了顾客购买行 为模式，可以用来指导商家科学地安排进货、库存以及货架设计等。之后诸多 的研究人员对关联规则的挖掘问题进行了大量的研究，他们的工作涉及到关联 规则的挖掘理论的探索、原有的算法的改进和新算法的设计、并行关联规则挖 掘以及数量关联规则挖掘等问题。在提高挖掘规则算法的效率、适应性、可用 性以及应用推广等方面，许多学者进行了不懈的努力f ”。 目前，国外对于数据挖掘的研究重点逐渐从发现方法转向系统应用，注重 多种发现策略和技术的集成，以及多种学科之间的相互渗透。当前，世界上比 4 武汉理工大学博士学位论文 较有影响的典型数据挖掘系统有c o v e rs t o r y ，e x p l o r a ，k n o w l e d g ed i s c o v e r y w o r k b e n c h ，d bm i n e r ，q u e s t 等1 8 2 】。在应用方面包括：k d d 商业软件工具不 断产生和完善，注重建立解决问题的整体系统，而不是孤立的过程。用户主要 集中在大型银行、保险公司、电信公司和销售业。国外很多计算机公司非常注 重数据挖掘的开发应用，比如m m 和微软成立了相应的研究中心进行这方面的工 作i 。此外，一些公司的相关软件也开始在国内销售，如i b m 公司的i n t e l l i g e n t m i n e r ，s a s 公司的e n t e r p r i s em i n e r 。 国内从事数据挖掘研究的人员主要在大学，也有研究所和公司在从事这方 面的研究，这些工作一般集中于学习算法和有关数据挖掘理论方面的研究【l 】o 例 如，复旦大学、南京大学、西安交通大学、东南大学、国防科大等单位已经在 挖掘算法效率改进等方面做了不少的工作。在具体应用方面，中科院计算所智 能处理开放实验室的史忠植等人设计了一个数据挖掘工具m s m i n e r ，使用决策树 算法为广东地税提供纳税人异常情况检测，复旦德门公司开发的“天眼”数据 挖掘工具集d m i n e r 集成了多种数据挖掘算法，取得了较好的挖掘效果【3 】。目前， 国内外对电子商务环境下的分布式数据挖掘研究集中在理论研究和应用研究两 个方面，国外在发现用户兴趣模式的理论体系研究和个性化服务方面都取得了 较大的进展。与国外相比，国内的分布式数据挖掘起步较晚，这一领域正处在 研究开发阶段，应用和产品还相对滞后，但是在理论和应用研究上有很多成果。 这些研究的重点在局部挖掘算法的设计、分析和改进，较少对数据挖掘系统自 身的构建、开发模式进行系统论述1 9 1 。电子商务环境下的分布式数据挖掘系统是 一个有机的整体，各个部分有着密切的联系，这一新兴领域不但有很好的研究 和应用前景，而且有很好的商业机会1 1 0 l 。因而，有必要根据当前数据存储、应 用环境的特点，构建一个实用的分布式数据挖掘原型系统，以指导今后设计实 际的分布式数据挖掘工具，以及支持在此基础上的渐进开发。 1 2 2 研究现状分析 在电子商务环境中，数据挖掘有广泛的应用；同时电子商务数据挖掘是数 据挖掘的一个新的重要应用领域。比如各大电子商务系统积极应用电子商务推 荐系统、搜索引擎等，都不同程度地应用了数据挖掘技术。但是随着 i n t e r n e t i n t r a n e t 的迅速普及，电子商务逐渐由传统的b 届结构向分布式多层次的 计算模式发展，其数据主要是以分布的形式存在，具有稀疏性、异构性、高维 5 武汉理工大学博士学位论文 性等特征，而且它需要在不同场合和不同时刻为各类用户提供不同类型的挖掘 功能。因此，电子商务环境中数据挖掘体系及算法面临一系列挑战，主要包括： 1 、分布性、实时性和可扩展性问题。目前大部分数据挖掘工具主要在单机 上w e b 运行，网络功能很弱，不能对异构环境下的数据库进行操作。数据挖掘算 法和模式主要采用集中式，即使数据是分布存储的情况下也要求首先把数据重 新收集集中起来，这就要求有高速的通信网络，并且会导致响应的时间变长、 数据的私有性和安全性遭到破坏。由于电子商务中数据的私有性、保密性、异 构性和系统的不兼容性，无法把所有的数据都集中到一个平台上。需要研究一 种新的分布式数据挖掘架构来解决此问题。 2 、数据的数量和维数问题。在实际应用中，电子商务系统的交易数据库包 含的商品数量是非常巨大的，交易数据库中的客户数量也非常巨大，数据结构 也因此显得非常复杂，如何进行探索、选择分析变量、处理高维数据等，成为 迫切需要解决的问题。k 最近邻搜索( k n l 如) 算法在高维数据的处理方面有很重 要的应用，但是存在不适合分布式环境、性能较低等问题。 3 、稀疏性问题。在电子商务系统中，由于数据具有稀疏性，每个用户涉及 的信息量相当有限。比如，在一些大的系统如亚马逊电子商务网站中，用户最 多不过就评估了上百万本书的1 2 ，造成数据相当稀疏。但是传统的关联规 则算法用少量的用户信息难以找到相似用户集，导致挖掘的效果大大降低。 4 、精确性问题。通过寻找目标数据的若干相近信息来产生数据项目集，在 数量较大的情况下，挖掘出的可信度随之降低。传统的聚类算法和关联规则算 法都存在这方面的问题。 5 、效率更好的数据挖掘的关键算法研究。传统k 最近邻搜索( q n s ) 算法在 电子商务领域有很重要的应用，但其可扩展性比较差，性能会随着数据量的增 大而线形地减弱，也不适合分布式环境，因此需要研究一种新的算法，提高i n n s 的性能，同时适合电子商务环境的需要。质量高的聚类算法能够有效分割用户 群，传统的聚类方法需要构建一个使得优化函数接近最优的对数据的k 个划分。 通常优化的标准是使得每一个点到簇中心点的欧几里德距离之和最小，无法解 决协同过滤技术所面临的数据稀缺性问题。因此，适合电子商务数据挖掘应用 的聚类算法的性能有待提高。传统的关联规则不能效地处理稀有数据，同时阈 值的制定由用户决定，降低了挖掘的精确度。 6 、新型电子商务环境中分布式数据挖掘架构研究。当前大部分电子商务挖 6 武汉理工大学博士学位论文 掘系统的挖掘引擎均是基于封闭体系设计的，难以动态有效地管理和维护多个 挖掘算法，挖掘结果格式的封闭，许多数据挖掘引擎提供的挖掘结果无法为其 他应用系统使用。因此，需要研究新型电子商务环境中分布式数据挖掘架构， 以有效集成多种挖掘工具，收集多种类型的数据，提供多种挖掘模型，使得不 同的挖掘工具组合使用、互补长短，满足不同类型的挖掘需求。 1 3 本文主要研究内容 本论文的主要工作是根据国内外在电子商务环境下分布式数据挖掘技术研 究现状及其最新发展动态，针对目前电子商务中数据挖掘的实际应用，为解决 电子商务环境中数据挖掘的分布性、实时性和可扩展性问题、数据的数量和维 数问题、稀疏性问题、精确性问题等，具体从以下几个方面进行研究： 1 、研究电子商务环境下分布式数据挖掘相关技术，将w e b 服务技术和a g e n t 技术引入电子商务数据挖掘中，提出电子商务环境下基- y - w e b n 务和动态a g e n t 的分布式数据挖掘架构( b 、眦d m ) 。试图解决电子商务环境中数据的分布性、 异构性、不确定、非结构化和海量性等问题。 2 、研究基于p 2 p 的k 最近邻自适应搜索算法。目前由于k n n 可扩展性比较 差，其性能会随着数据量的增大而线性地减弱，针对此问题，研究一种在p 2 p 环 境中自适应的分布式k 最近邻搜索算法( p 2 p a k n n s ) 。p 2 p a k n n s 采用适用于高 维数据的相似度函数h d s f c x ，n ，以避免欧氏等传统的距离函数在高维空间中 的缺点；采用传统的超球数据分割的方法自适应地确定超球的大小，以有效缩 小搜索范围，提高效率。 3 、研究基于距离和密度的无监督聚类算法( k n d c ) 。在常用聚类算法中， d e n c l u e 是一种优良的算法，该算法能够识别各种复杂形状的聚类，能有效排 除噪声干扰，并且聚类结果不受输入顺序的影响。但是该算法需要输入邻域半 径及密度阈值等参数，而邻域半径需要经过复杂的计算并通过人工观察图形来 确定，所以很难找到合适的参数值。k 最近邻自适应搜索算法在模式识别、机器 学习、数据挖掘、多媒体数据库、时间序列分析等中有很大的用途，该方法对 密度估计和分类等很有效。因此综合k 最近邻自适应搜索算法和d e n c l u e 算法， 研究一种新的算法，无监督地确定参数和节省主存是很必要的。 4 、研究电子商务环境下分布式数据挖掘的关联规则相关技术问题。分析 7 武汉理工大学博士学位论文 a 州蜊关联规则算法、多重最小支持度a p r i o r i 算法、相关支持度a p f i o f i 算法、平 均项目集合分割法。在基于无向项集图算法的基础上，结合相关支持度a p r i o f i 算法，研究一种发现有价值的稀有数据的有效算法。为改进相关支持度a p r i o r i 算法制定阈值的无根据问题，研究一个新的阈值制定方法。 1 4 本文主要研究成果 通过研究，本文取得了如下的研究成果及创新： 1 、提出了电子商务环境下基于w e b 服务和移动a g e n t 的数据挖掘架构 ( b w a d m ) 。利用w e b 服务技术和a g e n t 技术，将数据挖掘技术应用到电子商 务环境中，解决了电子商务环境中数据的分布性、异构性、不确定、非结构化 和海量性等问题。实现了算法库的动态管理和算法库的分布式部署，达到按需 定制挖掘服务和可集成性。 2 、提出了基于p 2 p 的k 最近邻自适应搜索算法( p 2 p a k n n s ) 。提出了一 个新的相似性度量函数h d s f ( x ，n ，该函数可以较好地克服欧氏距离函数在高 维空间的缺点。p 2 p a k n n s 算法首先将所有高维数据插入到一棵g h t * 树中， 然后预测一个比较小的查询范围，再采用相似性度量函数h d s f ( x ，y 1 来查询当 前数据对象的k 个最近邻居。通过该算法的研究，解决了k n n s 的不足，增强了 对高维数据的处理能力，提高了对海量数据处理的效率和精确度。 3 、提出了基于距离和密度的无监督聚类算法( k n d c ) 。k n d c 算法综合 运用了k 最近邻自适应搜索算法和d e n c l u e 算法来提高聚类的性能和精确度。 首先结合核密度估计方法和七近邻搜索算法，无监督地确定每一个点的窗宽，将 数据集分割成许多模糊簇( f c ) ，然后根据熵的理论确定每一个模糊簇的局部参 数p ，亭) ，最后将每一局部参数映射到全局参数，独立地对每一个f c 进行聚类。 通过该算法的研究，提高了聚类的效率和质量，可以在b w a d m 中有效地分割用 户群，也可以解决协同过滤技术所面临的数据稀缺性等问题，提高了数据挖掘 的效率和精确度。 4 、以相关支持度a p r i o r i 算法( r s a a ) 为基础，提出了一个双重阈值的确 定方法，根据第一个最小支持度与数据库中项目的属性，计算出第二个晟小支 持度。该方法的研究，解决了阈值人工制定的闯题，提高了关联规则的精确度 和效率。同时为解决目前基于无向项集图算法( b o u l g a ) 采用单一支持度，在 8 武汉理工大学博士学位论文 挖掘过程中存在着不能高效地挖掘出有价值的稀有数据的问题，提出了 r s a a - b o u i g a 算法。该算法采用基于无向项集图的思想来发现频繁项集，即 只需要扫描数据库一次，没有联结操作，提高了频繁项集的发现效率。 5 、解决数据挖掘技术在电子商务环境中的应用问题。分布式数据挖掘是数 据挖掘领域的一个新兴研究课题，结合w e b 服务技术的跨平台、统一数据表示 格式以及可实现软组件重用和数据重用等优点，本文提出的电子商务环境中分 布式数据挖掘架构( b w a d m ) ，可实现分布式异构环境下的大容量数据的挖掘， 旨在对异构数据库的数据挖掘进行些有意义的探讨。 6 、解决传统电子商务系统的被动性与效率问题。应用电子商务环境中分布 式数据挖掘的研究成果，可对用户的访问信息进行有效的数据挖掘，得到有关 用户访问行为的知识，这些知识可以发现电子商务中用户的访问模式，在电子 商务中能根据用户的需要自动地推荐给用户可能感兴趣且满意的商品。 1 5 本文的组织结构 本文从两个方面展开。( 1 ) 电子商务环境中分布式数据挖掘的方法研究， 主要研究基于p 2 p 的k 最近邻自适应搜索算法、基于距离和密度的无监督聚类算 法和关联规则有关问题，这些技术是电子商务中数据挖掘方法的关键技术。( 2 ) 电子商务环境中分布式数据挖掘架构的研究。论文共分七章，其余各章具体组 织结构如下。 第2 章分布式数据挖掘、w e b 服务与a g e n t 相关技术。首先介绍了分布式 数据挖掘定义、特点及挖掘策略；其次论述了电子商务环境中数据挖掘的分类 及特点；然后介绍了w e b 服务的基本概念、w e b 服务核心技术、扩展的w e b 服 务协议栈、p 2 p 环境中的w e b 服务、w e b 服务和网格计算；最后论述了移动a g e n t 的定义及特性、移动a g e n t 的体系结构、移动a g e n t 技术应用于电子商务的优势。 第3 章基于p 2 p 的k 最近邻自适应搜索算法的研究。为解决k n n s 存在的 问题、提高算法效率和精确度，提出了p 2 p a k n n s 算法。首先分析了度量空间、 相似性查询和g h t 规则；然后论述了相似度函数h d s f ( x ，n ，研究了插入算 法及范围查找算法和搜索算法；最后给出了p 2 p a k n n s 算法的具体方法，并验 证了其正确性。 第4 章基于距离和密度的无监督聚类算法的研究。首先介绍了聚类相关 9 武汉理工大学博七学位论文 知识，分析了d e n c l u e 算法，论述了其优点与存在的问题。为解决这些问题 及提高算法的效率和精确度，结合p 2 p a k n n s 算法，提出了k n d c 聚类算法。 然后论述了模糊簇的划分、参数七、参数盯和参数亭。最后具体地给出了k n d c 算法的实现方法，并通过实验，验证了其正确性。 第5 章电子商务环境下关联规则算法的研究。在分析a p n o n 关联规则算 法、多重最小支持度a p d o d 算法、相关支持度a p d o f i 算法( r s a a ) 、平均项目 集合分割法基础上，提出了双重阈值的制定方法。为高效地挖掘出有价值的稀 有数据，在基于无向项集图算法( b o u i g a ) 和r s a a 的基础上，提出了 r s a a b o u i g a 算法。 第6 章电子商务环境中分布式数据挖掘架构研究。针对目前分布式数据 挖掘体系结构存在的问题，提出电子商务环境中分布式数据挖掘架构b w a d m 。 给出了b w a d m 相关定义并对其进行了描述，论述了b w a d m 服务组合规范与服 务组合的执行，研究了数据预处理组件、算法管理组件、控制中心组件、算法 库组件和模型表示组件。给出了b w a d m 原型，并设计和实现了该原型系统。最 后介绍了原型系统的运行实例并论述了系统架构的优点。 第7 章全文总结。研究工作总结及进一步的研究工作。 武汉理工大学博士学位论文 第2 章分布式数据挖掘、w e b 服务与a g e n t 相关技术 电子商务环境下，数据一般具有分布性、异构性、稀疏性及复杂性等特征， 当前在此环境下的数据挖掘算法和模式主要采用集中式，并且大部分电子商务 挖掘系统的挖掘引擎是基于封闭体系设计的，不能满足电子商务的发展对数据 挖掘的要求1 8 1 j 。为了在电子商务环境中实现分布式数据挖掘，需要分析和应用 数据集成等技术。这些技术主要包括w e b 服务技术、移动a g e n t 技术等。本章先 概述了分布式数据挖掘，然后简述了电子商务环境与数据挖掘，最后阐述了w e b 服务技术和移动a g e n t 技术。这些是研究电子商务环境中分布式数据挖掘的技术 基础。 2 1 分布式数据挖掘概述 随着数据库和计算机网络技术的广泛应用，许多大型数据库是以分布式存 在。分布式数据挖掘是使用分布式计算从分布式数据库中抽取知识的过程，这 是一个发展非常迅速，而且具有广阔应用前景的研究领域l 删。如何从分布式数 据库中挖掘有价值的知识是一个具有挑战性的研究课题。 分布式数据挖掘可以基于多处理器的并行系统( 紧耦合系统) ，也可以基于 多机分布式系统( 松耦合系统) ；它可以基于结构化数据，也可以基于w e b 网页 等无结构数据。在分布式数据挖掘中，它的分布性包括两个含义，即数据分布 和功能分布。数据分布是指数据是分布存储的；功能分布则是指整个数据挖掘 的处理过程是分布的瞄j 。 为什么面向分布式数据库的数据挖掘研究得到了如此的关注呢? 其主要原 因是 g l ：( 1 ) 数据挖掘的目标是大规模的数据集，在现实环境中，绝大部分的大 型数据库都是以分布式的形式存在的，因此，提出新的分布式数据挖掘系统的 体系结构是非常必要的。( 2 ) 在数据挖掘系统中，经常需要来自不同站点的数 据库中的数据，这就使得数据挖掘系统必须具有分布式挖掘的能力，同时也需 要根据分布式数据挖掘的特点设计出新的分布式数据挖掘算法。( 3 ) 随着互联 网的快速应用普及，