（计算机应用技术专业论文）公安数据分析系统的设计和实现.pdfVIP

摘要 公安领域的信息系统建设经过了十余年的发展已经初具规模。随着信息化建设的不断深 入，我们对信息系统发挥的作用提出了更高的要求，于是决策支持提上了议事日程，而传统 的事务型处理系统并不能很好地为我们解决这类闯题。 本文详细阐述了公安数据分析领域应用数据挖掘技术的方法，拓展了该技术的使用范 围，同时提高了刑事犯罪分析领域的水平，在一定程度上实现了应用计算机技术分析数据和 辅助破案，促进了该领域的信息化进程。在挖掘了人量数据后，本文得出了有一定参考价值 的分析结论，为该领域有效应用数据挖掘技术进行研究提供了一个方向。该课题在一定的程 度上获得了成功，主要包括以下几方面： ( 1 ) 成功地进行了关联挖掘。在一定支持度、置信度和有趣度基础上，采用a 研o r j 算法进 行挖掘，得出频繁项集，从而导出关联规则。得出有用的结论； ( 2 ) 成功地建了一棵犯罪行为分析决策树，得出相应判定规则： ( 3 ) 成功地对案件信息作了串并案分析，减轻了手工劳动的强度，提高了串并寨的准确性 和速度： ( 4 ) 提出了建立用于o l a p 分析的犯罪分析数据库的方法： ( 5 ) 提出了一种新颖的聚类算法b f s n 。与同类算法相比该算法具有实现简单，复杂度 低，容易设定最佳参数等优点。实验证明，在聚类正确率相近的情况下，该算法的效率比较 高，而且还能揭示同类对象之间的相异程度； ( 6 ) 提出了将数据挖掘和o l a p 分析应用于犯罪分析的方法和模式； ( 7 ) 得到了一些关于刑事案件方面的结论这些知识对于指导决策有相当重要的意义。 数据仓库和数据挖掘技术提出、形成时间不长，在国内得到具体应用不过数年目前成 功的例子不多，且基本局限在金融、保险、商业等领域，而在公安数据分析领域，更是鲜见 有效应用。本文抛砖引玉，在该领域作了初步探索，相信这是公安司法领域所迫切需要的， 具有很人的应用、借鉴和参考价值。 关键词：数据挖掘犯罪分析关联分类聚类 a b s t r a c t t h ei n f o r m a t i o ns y s t e mf o rp u b l i cs e c u r i t yd e v e l o p sq u i c k l yi nr e c e n td e c a d e s w i t ht h e d e v e l o p m e n to ft h ei n f o r m a t i o ns y s t e m ，w ea l s op u tf o r w a r dh i g h e rd e m a n do ni t w ee x p e c tt h e i n f o r m a t i o ns y s t e mc a nh e l pa st om a k ed e c i s i o n s b u ta ut h et r a d i t i o n a lo n - l i n et r a n s a c t i o n p r o c e s s i n gs y s t e mc a l l t t h i sp a p e ri n t r o d u c e sa na p p l i c a t i o no f d a t am i n i n gt e c h n i q u eo np u b l i cs e c u r i t yd a t aa n a l y s i s i tg i v e sam e t h o dt oc r a c kc r i m i n a lc a s e sa n da n a l y z ec r i m i n a ld a t ab yc o m p u t e ra i d e d t h ep a p e r a l s od r a w ss o m ew o r t h f u lc o n c l u s i o n so f c r i m i n a la n a l y s i s ，o u rc o n t r i b u t i o n sa r e ： ( 1 ) w es u c c e e di nd a t a m i n i n ga s s o c i a t i o nr u l e s b a s e do nt h ep a r a m e t e r sl l k e s u p p o r t ， c o n f i d e n c em a di n t e r e s t i n g , w ed a t a m i n et h ef r e q u e n ti t e m s e t sa n da s s o c i a t i o nr u l e sb ya p r i o r i a l g o r i t h m ( 2 ) w es u c c e e di nb u i l d i n gad e c i s i o nt r e ef o rc r i m i n a la n a l y s i s ( 3 ) w es u c c e e di nc r a c k i n gc r i m i n a lc a s e sa n da n a l y z i n gc r i m i n a ld a t ab yc o m p u t e ra i d e d o ) w es u c c e e di np r o p o s i n gam e t h o dt ob u i l dc r i m i n a la n a l y s i sd a t a b a s e sf o ro l a e ( 5 ) w ep r e s e n tan o v e l ，s i m p l ea n de f f e c t i v ec l u s t e r i n ga l g o r i t h mn a m e db f s n c o m p a r e d w i t ho t h e ra l g o r i t h m s ，t h eb f s na l g o r i t h mi se a s i e rt or e a l i z ew i t h o u tc o m p l i c a t e dc a l c u l a t i o n i t c a nb ed e f i n e dt h eb e s tp a r a m e t e r sw i t h o u td i f f i c u l t y t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h e b f s na l g o r i t h mi sm o r ee f f e c t i v et h a ns o m eo fo t h e r sa ts a m ec l u s t e r i n gp r e c i s e n e s sa n di tc a l l a l s or e v e a ld i s s i m i l a r i t yd e g r e eb e t w e e nt h es a m ec l u s t e r so b j e c t s ( 6 ) w ep r e s e n tam e t h o dt oa p p l yt h ed a t a m i n i n gt e c h n i q u ea n dt h eo l a pt e c h n i q u et op u b l i c s e c u r i t yd a t aa n a l y s i s w et h i n ki ti sv e r yu s e f u lt ot h ed o m a i no f p u b l i cs e c u r i t y ( 7 ) w es u c c e e di nd r a w i n gs o m ew o r t h f u lc o n c l u s i o n so f c r i m i n a la n a l y s i s t h ek n o w l e d g ei s q u i t eu s e f u l t h et h e o r i e so fd a t aw a r e h o u s ea n dd a t a m i n i n ga r ep r o p o s e db e f o r eaf e wy e a r s t h e ya r e a p p l i e di no u rn a t i o no n l yi na b o u to n ed e c a d e t h e r ea r eo n l yaf e ws u c c e s s f u lc a s e sa b o u t f i n a n c e ，i n s u r a n c e ，b u s i n e s s ，e t c b u tt h e r ea r ef e ws u c c e s s f u lc a s e sj b o u tp u b l i cs e c u r i t yd a t a a n a l y s i s w ec o n s i d e rt h a tw h a tw eh a v ed o n ei ss i g n i f i c a n tf o rp u b l i cs e c u r i t yd o m a i n k e yw o r d s ：d a t amn i n g ，c r i m ea n a l y s i s ，a s s o c i a t i o n ，c l a s s i f i c a t i o n ，c l u s t e r i n g l i 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。 尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过 的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用过的材料。与我 一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 研究生签名：日 期： 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复印 件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质 论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包括 刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东南大学研究生院办理。 研究生签名：导师签名： 日 期： 东南大学硕士学位论文 第一章绪言 1 1 课题背景 数据挖掘就是应用一系列技术从大型数据库或数据仓库的数据中提取人们感兴趣的信息和知 识，这些信息和知识是隐含的、事先未知的、潜在有用的和不一般的，提取的知识表示为概念 ( c o n c e p t s ) 、规则( r u l e s ) 、规律( r e g u l a r i t i e s ) 、模式( p a t t e m s ) 等形式j l 一。此方法的提出使人 们有能力最终认识数据的真正价值，获取数据库中蕴涵着的规则、规律、论断之类的高层次的信息 和知识。数据挖掘的结果是概念化的知识，这些知识源于数据但高于数据。数据挖掘与传统的数 据分析( 如查询、报表和联机事务处理) 的本质区别是前者是在没有明确假设的前提下挖掘信息并 发现知识，通过挖掘所得到的信息应具有先前未知、有效和可实用等三个特征。现在数据挖掘已经 被认为是数据研究中个极富应用前景的新领域，自1 9 9 5 年第一届知识发现和数据挖掘国际会议 在加拿大召开以来，数据挖掘技术已成为机器学习、数据库系统、人工智能等领域内热门的研究方 向。数据挖掘的方法主要包括关联分析、分类和预测、聚类分析、孤立点分析和演变分析等。 研究知识发现和数据挖掘技术的重大意义现在已经被人们广泛认识，并且被列为数据库研究领 域中最重要的课题之。例如美国政府开发s e q u o i a 2 0 0 0 项目作为大规模数据库中先进的数据分析 上具。许多商业公司也充分认识到深层次地分析本公司业务数据库中的数据能够带来更多的商业机 会，例如银行和零售商店通过分析他们的业务数据，能够进一步掌握和了解顾客的信誉、习惯和消 费心理，从而相应地调整他们的市场策略，以获取更大的利润。例如有个应用在行销领域的例子”1 ： 经由记录客户的消费记录与采购路线，超级市场可以设计出更吸引顾客购买的环境。根据数据挖掘 出来的信息，现在超级市场的厨房用品，是按照女性的视线高度来摆放。根据研究指出：美国妇女 的视线高度是1 5 0 公分左右，男性是1 6 3 公分左右，而最舒适的视线角度是视线高度以下1 5 度左 右，所以最好的货品陈列位置是在1 3 0 至1 3 5 公分之间。在商业上，有许多特征是很难理解的，但 若了解到这些信息，就会增加企业的竞争能力。 数据挖掘技术还引起了学术界和工业界的广泛关注，吸b i 了众多的研究人员和商业机构参与研 究，一些国际上著名的工业研究实验室，例如i 伽a l m a d e n 和g t e 等众多的学术单位也都在这个领 域开展了各种各样的研究计划。一批数据挖掘系统如q u e s t 、k d w 、e x o l o r a 、i m a c s 、d b m i n e r 等被 开发出来，并在商业、经济、金融、管理等领域都取得了一定的应用性成果。这些系统基本上代表 了自2 0 世纪8 0 年代以来数据挖掘技术的发展，采用的方法综合了数据库、专家系统、模式识别、 机器学习、统计学、科学发现和数据分析等多个领域的研究成果。但总的来说，这些系统还基本停 留在实验阶段，在适用性、系统效率方面还不尽人意。 与国外相比，国内对数据挖掘和知识发现的研究稍晚，没有形成整体力量。1 9 9 3 年国家自然科 东南大学硕士学位论文 学基金首次支持对该领域的应用研究，目前，国内许多科研单位和高等院校包括清华大学和中科院 计算研究所等竟相开展数据挖掘和知识发现的基础理论及其应用研究，每年都有许多高质量的论文 发表。 随着信息化的发展，国内许多单位包括公安部门都建立了相当规模的信息系统，但绝大多数单 位对信息系统的使用仅仅停留在查询、更新、统计等初级应用上，缺乏智能化的分析功能。可以说 其事务性功能已经基本完善，但分析功能还相当欠缺，许多关联性的规律趋势等隐藏在大量业务数 据内，尚有待挖掘和提取。例如：可以对违法人员数据库作关联分析，在一定的支持度和置信度的 基础上发现犯罪行为如吸毒与抢劫的关系；或进行分类，构造犯罪分析决策树发现具有某些属性 的违法人员容易犯的某种罪行：或对案件库聚类，进行串并案分析，为破案提供帮助：还可以进行 联机分析处理( 0 l a p ) ，使有关部门能作出更灵活迅速的决策。 1 2 研究目标和内容 数据挖掘技术提出、形成时间不长，在国内得到具体应用不过数年，目前成功的例子不多，且 基本局限在金融、保险、商业等领域，而在公安数据分析领域。更是鲜见有效应用。目前国外企业 界把数据挖掘应用在许多领域，包括行销、财务、银行、制造、通讯等。在国外数据挖掘尽管应用 比较广泛，但应用于犯罪行为分析、协助破案等也不是很多，当然成功的例子也有，如：美国夏洛 特卡罗莱纳警察局用s p s s 软件进行了大量数据分析来证明和分析与住宅建筑工地的器具盗窃以 及非商业区停车场的汽车盗窃相关联的多种因素，最后成功地解决了这一问题。但从总体来说，不 管是国内的还是国外的，将数据挖掘应用于犯罪行为分析、协助破案等很少，从我们的研究成果来 看，在这领域的应用研究将有很好的前景。 公安信息领域经过十几年的发展，获得了长足的进步，到目前为止在公安的许多业务领域如户 政、交管、外事、刑侦等已逐渐积累了大量数据。例如全国人口总数达1 2 g ，仅以基本信息每人 1 0 0 0 字节测算，数据库容量也需1 2 0 0 g ，如果包括各种复杂信息( 甚至图象) 。数据库将更为可观。 如何有效管理和利用这些数据信息，为各项管理工作服务，如分析违法犯罪活动特点、犯罪行为、 案件调查、各种人口调查、交通流量测算、警力分配甚至突发事件处理等都是全新而有重大意义 的课题。数据仓库、数据挖掘和联机分析处理技术为解决这些问题提供了研究方向，结合公安信息 系统的特点深入研究这些技术，就是我们进行研究和写作本文的目的。 本课题应用数据挖掘等技术，在拟定的算法下对大量的犯罪记录进行分析，从而发现犯罪行为 的规律、趋势了解不同犯罪行为之间的关联，以及何种状态会诱发何种犯罪行为，或进行串并案 分析协助破案等等。相信这是公安司法部门所迫切需要的，具备很大的应用、借鉴和参考价值具 有相当重要的现实意义。 2 东南人学硕士学位论文 同时，在研究过程中，我们提出了一种基于广度优先邻居搜索的聚类方法，该算法具有几个特 点：( 1 ) 算法简单，实现容易，避免了复杂计算，时间复杂度低，聚类结果精确；( 2 ) 聚类过程中能够 发现同类对象之间的相异程度，而这一点许多算法达不到：( 3 ) 需要输入的两个参数基本上可以估算； ( 4 ) 能够发现孤立点，发现任意形状的聚类；( 5 ) 对输入数据的顺序基本不敏感。 应用研究的主要内容包括挖掘分析乖i o l a p 分析，包括： 关联挖掘：在一定支持度、置信度和有趣度基础上，采用a p r i o r i 算法或改进算法进行挖掘，得 出频繁项集从而导出关联规则，得出类似：“犯罪行为吸毒导致抢劫”等关联规则。 分类挖掘：采用i d 3 算法对犯罪行为数据进行决策树分析，画出犯罪行为分析决策树，得出判定 规则，如：“无工作，年龄4 3 0 ，a 类地区容易涉嫌抢劫案件，而且该种案件占了所有案件的5 0 ” 等判定规则。 聚类分析；采用我们提出的基于广度优先邻居搜索的聚类算法，对案件信息进行聚类分析，作串 并案，辅助破案。 对案件信息和违法犯罪人员信息作0 l a p 分析。 1 3 论文框架 论文的章节安排如下： 第一章绪言 第二章某市公安现有系统简介 第三章理论基础与系统框架 第四章关联分析 第五章分类分析 第六章聚类分析 第七章o l a p 分析 最后的结论对整篇文章做了总结和概括。 东南大学硕士学位论文 第二章某市公安现有系统简介 某市公安系统在“向科技要警力”、“科技强警”的1 7 1 标的指引下，十几年来信息系统建设取得 了长足的发展。由于其自身的行业性质和工作特点，和金融、财税等行业的信息系统建设紧紧围绕 企业、帐目等主题有所不同，公安信息系统所涉及的范围极其广泛，如居民户籍、机动和非机动车 辆、驾驶员、交通事故、出入境管理、刑事案件、犯罪分子、指纹档案、在押犯人、消防信息、治 安要情等等。十几年来，信息系统建设从无到有，从小规模到大规模，从粗糙到精细，甚至有一些 应用已经开始完全替代手工劳动。 2 1 网络架构 与互联网没有中心的特点不同，全国公安信息网是一个以公安部为中心节点的特大的计算机网 络。该网络与互联网及其它网络没有任何物理联系。公安部负责连接全国所有的省、自治区和真辖 市，省一级负责连接本省所有的地市。地市级负责连接本市所有的县( 市) 区，县级负责连接本县 所有的派出所。在这公安大网内访问有点类似于行政上的访问：如宁波想访问杭州，数据需要通过 浙江省公安厅路由：如宁波想访问南京，数据需依次通过浙江省公安厅、公安部和江苏省公安厅路 由。显然，这种网络架构与互联网的多条路由中选一条最佳路由的原则是不一致的( 事实上，宁波 到南京也就只有以上的一条路由，冗余路由也走的是相同的线路) ，但这种架构与各级公安机关的 职责相对应，更易于管理。 图2 1 某市公安局现有信息系统网络架构 经过几年的不断建设，该市公安局计算机网络也不断更新换代，从最早的i o m 局域网到后来 的百兆千兆局域网，广域网发展为d d n 、帧中继、i s d n 、光纤网等等。现在该市公安局通过4 m 光纤往上联入省公安厅，往下通过1 0 m 或6 m 光纤联接1 6 个县( 市) 区、边防支队、消防支趴等 4 东南大学硕士学位论文 等再通过他们联入近2 0 0 个派出所。图2 1 是该市公安局现有信息系统网络架构。主交换机是两 台c i s c 0 6 5 0 9 ，楼层交换机是c i s c 0 3 5 4 8 ，路由器是c i s c 0 3 6 4 0 和c i s c 0 7 5 0 0 ，拨号服务器有两种， 一种是i s d n 拨号服务器，是在c i s c o 加插i s d n 模块；另一种普通p s t n 的拨号服务器，包括 3 c o m l 5 0 0 、n e t s e r v e r 等多种型号。 广域网是采用复用技术三网台一的，即数据、图像和普通电话，其中数据指一般的h t t p 、邱 流量，图像主要用于电视电话会议。考虑到安全因素，该市公安局网络配置了防火墙，同时在交换 机上作了虚拟网，咀控制“广播风暴”和增强安全性，路由器上还配置了a c c e s s l i s t 限制地址及端 口访问加以安全控制。逐步停用普通p s t n 的拨号服务器，并在所有i s d n 拨号服务器增加了电话 号码识别，大大增加了远程接入的安全性。 2 2 信息系统 在公安部和省公安厅的统一领导下，经过多年的建设，该市公安局信息系统建设取得了显著的 发展，所采用的软硬件技术也随着整个计算机技术的发展逐步提高，早期一般为单用户的微机和桌 面数据库( 如d b a s e 、f o x p r o 等) ，现在绝大部分系统已经升级换代为网络操作系统( w i n d o w s n t ， u n i x 等) 和大型数据库( o r a c l e ，s q ls g r v c r 等) ，基于w 曲的浏览器服务器模式的系统和基于 客户机服务器模式的系统在各种应用系统中都得到充分的应用。已经建成并在使用的信息系统主 要有居民户籍、机动和非机动车辆、驾驶员、交通事故、出入境管理、刑事案件、犯罪分子、指纹 档案、在押犯人、消防信息、治安要情、旅馆管理等等。 公安信息系统有几个特点： ( 1 ) 数据量非常大。例如全国人1 ：3 总数达1 2 g 。仅以基本信息每人1 0 0 0 字节测算，数据库容量 也需1 2 0 0 g ，如果包括各种复杂信息( 甚至图象) ，数据库将更为可观。 ( 2 ) 信息系统之间相对独立。例如有些系统是我们独立开发，而有些系统是省公安厅推广- 还有 一些是公安部推广因此各系统间相对独立。这有优点当然更有缺点，优点是一个系统崩溃不会影 响其它系统，保证工作不受较大影响：缺点是不能充分利用其它可以利用的资源，如暂住人口登记、 出国人员登记可以直接与批捕在逃人员比对，当然我们也为改进这种状况作了些工作，但由于开发 单位不同、推广单位不一致，所以从总体来讲系统之间还是比较独立。 东南大学硕士学位论文 系统名称业务领域软件平台业务数据总量规模 数据更新量规模 ( 记录数) ( 记录数天) 常住人口户政 0 r a c l e5 ，0 0 0 ，0 0 0 l ，0 0 0 暂住人口 户政s a ls e r v e r4 0 0 ，0 6 0 3 0 0 工作对蒙户政s q ls e r v e r8 0 ，0 0 0 5 0 - 1 0 0 流动人口治安 0 r a c l e1 ，5 0 0 0 0 05 ，0 0 0 机动车辆交通 o r a c l e2 0 0 0 0 0 1 0 0 2 0 0 非机动车辆 交通o r a c l e 2 0 0 0 ，0 0 03 0 0 机动车驾驶员交通 o r a c l e2 0 0 。0 0 01 0 0 违法犯罪人员刑侦s q ls e r v e r 1 2 0 。0 0 0 1 0 0 案件瓷料刑侦s q ls e r v e r 1 7 0 ，0 0 01 0 0 2 0 0 指纹资料刑侦自定义文件格式 5 0 ，0 0 0 1 0 0 在押犯看守 0 r a c l e1 0 ，0 0 0 2 0 收容犯看守 o r a c l e2 ，0 0 0 1 0 外国人来华外事 s q ls e r v e r4 0 ，0 0 0 1 0 2 0 因私出境外事s q ls e r v e r 1 0 0 0 0 01 0 2 0 治安要情指挥中心 n o t , e s1 0 0 ，0 0 02 0 0 消防信息消防s q ls e r v e r 2 0 ，0 0 0 1 0 2 0 表2 1 某市公安局公安业务信息系统数据调查表 ( 3 ) 有相当的信息内容空缺。例如在逃人员库，有相当多的信息是没有，或者说是根本没法获得， 有些信息只有一张照片，考虑到一线民警办案条件的辛苦以及案件的错综复杂，信息的空缺也是必 须面对的现实。 ( 4 ) 信息更新快。所有信息必须当天录入，一旦延误，使得该抓的逃犯没抓到，该破的寰件没破 掉，后果将是非常严重的。 表2 1 列出了目前该市公安系统在用的各种业务信息系统的业务领域、软硬件平台、数据量规 模等的信息，其中的包括更新数据的期限和规模。实际应用系统远远不止表中所列，为保密起见和 突出重点，选取一些规模较大、保密要求较低的系统列出。 这些系统涉及面非常广泛，系统与系统之间相对独立，因此想将它们综合起来建设数据仓库然 后作数据挖掘和o l a p 分析有相当的困难。在以后几章中，我们将选取其中有代表性质、保密要求 较低的数据库作数据挖掘和分析。 6 东南大学硕士学位论文 第三章理论基础与系统框架 3 1 数据挖掘技术 数据挖掘作为决策支持新技术在近十年来得到迅速发展。作为数据挖掘对象的数据仓库的产生 和发展为数据挖掘技术开辟了新的战场，同时也提出了新的要求和挑战。数据仓库和数据挖掘是结 合起来发展的。 3 1 1 数据挖掘概念 对于数据挖掘( 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 9 9 5 年在加拿大召开了第一届知识发现和数据挖掘国际学术会议。在这次会议上，对于数据 挖掘和数据库中的知识发现的概念进行了描述。数据库中的知识发现被认为是从数据中发现有用知 识的整个过程，而数据挖掘被认为是知识发现过程中一个特定的步骤。该会议未对数据挖掘作出确 切的字面定义，但对知识发现作出了确切的字面定义，如下： “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 i st h en o n - t r i v i a lp r o c e s so fi d e n t i f y i n gv a l i d , n o v e l , p o t e n t i a l u s e f u l a n d u l t i m a t e l yu n d e r s t a n d a b l e p a t t e r n 加d a t a ” 而m e t ag r o u p 是这样定义数据挖掘的； “d a t am i n i n gi st h ea p p l i c a t i o no f a r t i f i c i a li n t e l l i g e n c e 似9t e c h n i q u e s ( n e u r a ln e t w o r k f u z z yl o g i c ， g e n e t i ca l g o r i t h m s ，e t c ) t ol a r g e q u a n t i t i e so fd a t a , t od i s c o v e r y h i d d e nt r e n d s ，p a t t e r n s , a n d r e l a t i o n s h i p s ，” 因此可以得出数据挖掘的一般定义：数据挖掘就是应用一系列技术从大型数据库或数据仓库的 数据中提取人们感兴趣的信息和知识，这些信息和知识是隐含的、事先未知的、潜在有用的和不一 般的，提取的知识表示为概念( c o n c e p t s ) 、规则( r u l e s ) 、规律( r e g u l a r i t i e s ) 、模式( p a t t e r n s ) 等形式。 一般情况下，数据挖掘的对象是数据库。而更广义的说法是，数据挖掘意味着在一些事实和观 察数据的集合中寻找模式，所以它对象不仅是数据库，也可以是文件系统或其它任何组织在一起的 数据集合，例如w w w 信息资源，最新的对象是数据仓库。 3 1 2 数据挖掘过程 7 东南大学硕士学位论文 从研究者的主观愿望来说，希望数据挖掘过程最好全自动化。但从目前的技术发展水平来看， 在数据挖掘过程中。适当介入一些人工干预、引导或限制，可以提高数据挖掘的有效性和有用性。 因此，数据挖掘至少在目前应看成是一个人机交互过程，图3 1 是数据挖掘的一般过程删。数据挖 掘一般先由人提出目标，例如优化销售策略。一经提出目标，则可选择有关的数据，例如对优化销 售策略这一目标可以选择与销售有关的记录。这一步数据选择或数据聚焦( d a t as e l e c t i o n 或d a t a f o c u s i n g ) 。数据经过选择后，还要作下列预处理： 图3 1 数据挖掘的一般过程 ( 1 ) 清除重复的、不完全的、违反语义约束的数据； ( 2 ) 模式的集成或修改。如果数据来自不同的数据源，数据及其元数据要进行集成。有些与挖掘 无关的属性可以删去。元组数如果太多可以采样，以节省处理开销。有些数值域可以分成几个等级， 例如年龄段可以分为2 0 以下、2 0 - 4 0 、4 0 6 0 、6 0 以上等，以简化处理。有时，还要增加一些导出 属性，例如研究一个地区发案率变化的规律，可在统计发案率记录中生成一个与去年同期发案率差 值的属性。在这一步。如果由人提供一些提示，可以更有效地处理。 数据模样( d a t ap a t t e m ) 的发现是数据挖掘的关键一步。数据库中蕴涵的规律、规则和特征表 现在数据的某种模样上。发现数据模样有多种算法，算法昀选择可以人机交互进行。数据模样仅 仅说明数据中存在某种规律，规则或特征，它的含义需要解释作用需要评价。这是数据挖掘的晟 后一步。在这一步中。人的作用特别明显，因为评价一个知识的价值，既有客观因素，也有主观因 素。而主观因素也许更为重要。 需要说明的是，一般需要6 0 的时间用在数据准备上，这说明了数据挖掘对数据有严格的要求， 而后挖掘工作仅占总工作量的1 0 。 3 1 3 数据挖掘方法 对于不同的数据挖掘目标，人们期望不同的数据模样，从而采用不同的数据挖掘方法。常用的 数据挖掘方法大致可分为三类；联系分析、预测和聚类。 ( 1 ) 联系分析 8 东南大学硕士学位论文 即发现数据间的联系。例如在一笔交易中，顾客如果买了甲商品，一般都要买乙商品，这就是 一种联系。这是同一交易内的联系，称为关联规则( a s s o c i a t i o nr u l e ) 。还有一种联系发生在不同交 易的数据之间，例如一个顾客买了甲商品，一般会接着买乙商品、丙商品。这种联系称为时间 序列( t i m es e q u e n c e ) 。 ( 2 ) 预测( p r e d i c t i o n ) 根据给定的数据模样，预测其结果。例如，模式识别、诊断、客户信用评估、利润预测等属于 这一类。常用的方法有分类( c l a s s i f i c a t i o n ) 和回归分析( r e g r e s s i o na n a l y s i s ) ，例如根据客户的特 点及其过去信用的记录，用分类的方法预测客户信用的类别。 ( 3 ) 聚类( c l u s t e r i n g ) 聚类是按数据的相似性和差异性，将数据划分为若干子集，子集还可再划分为若干子子集。聚 类和分类不同，分类的类别是按应用的要求事先给定的。根据表示事务特征的数据，可以识别其类 别。而聚类的类别不是人为指定的，而是分析数据的结果。通过比较数据的相似性和差异性，发现 其特征及分布，从而抽象出聚类的规律。例如对产品进行聚类分析，可以找出影响产品质量的主要 原因及应采取的对策。 以后备章将详细介绍关联挖掘、决策树分类和聚类分析。 3 2 联机分析处理技术 3 2 1o l a p 的定义和特征 o l a p 即为联机分析处理( o n - l i n e a n a l y t i c a lp r o c e s s i n g ) ，它是一种软件技术，它能使分析人 员迅速、一致、交互、全面地从各个方面观察信息，以达到深入理解数据的目的。这些信息都是从 原始数据转换过来豹，它们以用户容易理解的方式反映对应企业或部门的真实情况。 o l a p 大部分策略都是将关系型的或普通的数据进行多维数据存储，以便于进行分析，从而达 到联机分析处理的目的。这种多维数据库也被看作一个超立方体，沿着各个维的方向存储数据，它 允许用户沿事物的轴线方便地分析数据，分析要求从统计数据中得到一个大致的范围。在实际应用 中，o l a p 常常包括对数据的相互查询，这项活动发生在通过多种途径的一系列分析之后，如对底 层细节的进一步挖掘。用户对这种多维数据模型的操作比对其他数据模型的操作要容易和直观。例 如，用户可以在模型中切片、切块以及绕一定的轴线旋转等。 1 9 9 3 年，e e c o d d 在“p r o v i d i n g o l a p t o u s e r a n a l y s i s ”提出了以下的有关o l a p 的1 2 条准 则，作为评价o l a p 产品的标准：( i ) 多维概念视图；( 2 ) 透明性；( 3 ) 存取能力；( 4 ) 稳定的报表性能： ( 5 ) 客户机，服务器体系结构；( 6 ) 维的等同性；( 7 ) 动态稀疏矩阵处理：( 8 ) 支持多用户；( 9 ) 非限定的跨 维操作 a 直接数据操纵；o d 柔性报表；0 9 维与聚集层次不受限。 o l a p 作为一种数据分析技术，它具有以下的功能特征： 9 东南大学硕士学位论文 ( 1 ) 给出数据仓库中数据的多维逻辑视图其视图应独立于数据存储的具体形式。 ( 2 ) 一般应包含交互式查询和对数据的分析。交互式查询一般有多种方式，包括下钻较低层的详 细数据或上卷较高层的概括性和聚集数据。 ( 3 ) 提供分析的建模功能，包括可以产生比率、变量等的计算引擎，有关的度量或跨多维的数据。 ( 4 ) 生成概括数据、聚集和层次，并在每一维的交叉点上对聚集和概括级别进行审计。 ( 5 ) 支持功能模型以进行预测、趋势分析和统计分析。 ( 6 ) 检索并显示二维或三维表格、图表和图形中的数据，并且应能容易地变换基准轴。因为用户 需要从不同的角度分析数据，并且在分析个侧面的数据时产生的问题可能需要在另一个侧面检 验。 ( 7 ) 快速响应查询，以避免分析过程被中断，或查询的信息是过时的。 ( 8 ) 具有多维数据存储引擎，按阵列存储数据，这些阵列是各应用维的逻辑表示。 3 2 2o l a p 与o l t p 的比较 联机分析处理是决策人员和高层管理人员对数据仓库进行信息分析处理。它处理的数据可能包 含以地区、类型或渠道分类的销售数据。一个典型的o l a p 查询可能要访问一个多年的销售数据库， 以便找到每一个地区的每一种产品的销售情况。当得到这些数据后分析人员可能会进一步地细化 查询，在以地区、产品分类的情况下查询每一个销售渠道的销售量。最后，分析人员可能会针对每 个销售渠道进行年与年或季度与季度的比较。整个过程必须被联机执行并要有快速的响应时间 以便分析过程不受外界干扰。 因此，联机分析处理具有以下特征：( 1 ) 可以存取大量的数据，比如几年的销售数据，分析各个 商业元素类型之间的关系，如销售、产品、地区、渠道：( 2 ) 要包含聚集的数据，铡如销售量、预算 金额等；( 3 ) 按层次对比不同时间周期的聚集数据，如月、季度或年；“) 以不同的方式来表现数据， 如以地区，或每一地区内按不同的销售渠道等来表现；( 5 ) 要包含数据元素之间的复杂计算，如在某 地区的每一销售渠道的期望利润与销售收入之间的分析；( 6 ) 能够快速地响应用户的查询，以便用 户的分析思考过程不受系统的影响。 联机事务处理( o n - l i n et r a n s a c t i o np r o c e s s i n g ) 是操作人员和低层管理人员利用计算机网络对 数据库中的数据进行查询、增加、删除、修改等操作，以完成事务处理工作。o l t p 以快速事务响 应和频繁的数据修改为特征用户利用数据库快速地处理具体业务。o l t p 应用时有频繁的写操作， 所以数据库要提供数据锁、事务日志等机制。与o l a p 不同，o l t p 包含大量相对简单的事务，对 这些事务通常只是需要获取或更新其中的一小部分数据( 通常小于1 0 0 字节) ，且这些表之间的关 系通常是很简单的。 1 0 东南人学硕士学位论文 以下是o l a p 与o l t p 的对比 0 l a p0 l t p 面向决第人员，支持管理需要面向操作人员，支持日常操作 导出的，综合的，历史的数据原始的，细节的，当前的数据 面向分析，分析驱动面向应用事务驱动 不可更新，但周期性刷新经常更新 次性处理的数据蠹大一次性处理的数据董小 响应时间合理响应时间要求高 用户数量相对较少用户数量大 表3 10 l a p 与0 l 3 p 的对比表 3 。2 3 多维0 l a p 与关系0 l a p 多维o l a p 和关系o l a p 是o l a p 的两种具体的形式。多维o l a p ( m o l a p ，m u l t i - d i m e n s i o n o l a p ) 是基于多维数据库存储方式建立的o l a p ，采用新的存储结构，从物理层实现起，所以又 称为物理o l a p ：关系o l a p ( r o l a p ，r e l a t i o no l a p ) 是基于关系数据库存储方式建立的o l a p ， 主要通过一些软件工具或中间软件实现，物理层仍采用关系数据库的存储结构，所以又称为虚拟 o l a p 。r o l a p 在节省空间、灵活性、与关系数据库保持致等方面有明显的优势；m o l a p 则在 性能和管理的简便性等方面有其优点。如采用二级访问结构，减少空白单元，存储空间也是很节省 的。 在多维数据库( m d d b ) 中二维数据很容易理解，当维数扩展到三维甚至更多维时，多维数据 库将形成类似于超立方体一样的结构。实际上，多维数据库是由许多经压缩的，类似与数组的对象 构成，这种对象通常带有高度压缩的索引及指针结构。每个对象由聚集成组的单元块组成，每个单 元块按类似于多维数组的结构存储，并通过指针直接偏移计算进行存取。由于索引只需一个较小的 数来标识单元块，因此多维数据库的索引一般较小，只占数据空间的- 4 , 部分，正因为它们如此之 小，| 三【至于可以很容易地将整个索引装进内存，这将极大地提高性能。在实际分析过程中，可能需 要把任一维与其它维进行组合，因而需要能够旋转数据立方体及切片的视图，即以多维方式显示数 据。在多维数据库中，并非维间的每种组合都会产生具体的值，实际上，许多组合没有具体值，是 空的或是零。另外，许多值重复存储，如一年中的价格可能一直不变。因此多维数据库必须具有高 效的稀疏数据处理能力，能略过零元、缺失和重复数据。 而在关系数据库中没有数组的概念，因此多维数据必须被映像成平面型的关系表中的行。这必 须通过一个能够平衡性能、具有存储效率和可维护性的方案来完成。具有代表性的是非标准化的星 型模式的设计，它将基本的信息存储在一个单独的事实表中，而有关维的支持信息则存储在其它表 中。这些基本数据将被复制到一系列专门为多维存取应用而设计的表中。预处理的结果一般被存放 在大量的综合汇总表中，这些综合的汇总表分别有不同的聚集及组合。它们每个都需要关键字来标 东南大学硕士学位论文 识，并且通过索引来获得高效的访问。而这些关键字在某些时候可以使用人们可读的描述符号，但 通常它们更多地使用严格的二进制整数键。后者对于存储和数据检索更有效，但当和描述符表联接 时需要将这些二进制键和现实世界的描述符关联起来，这将给每个检索操作增加额外处理。 以下两表分别是r o l a p 和m o l a p 中的数据表示： 被盗机动车型被盗地区数量 桑塔纳 a 市 1 5 柳州五菱 a 市1 3 嘉陵摩托 a 市7 3 桑塔纳b 市8 柳州五菱 b 市1 2 嘉陵摩托 b 市3 5 桑塔纳 c 市4 柳州五菱 c 市7 嘉陵摩托c 市3 1 表3 2r o l a p 中的数据表示 被盗机动车型 a 市 b 市c 市i 桑塔纳1 584 柳州五菱 1 31 2 7 嘉陵摩托 7 33 53 1 j 表3 3m o l a p 中的数据表示 可以看出，多维数据库采用了多维矩阵的组织方式，比关系表更清晰，占用的存储空问也更小， 如果要进行统计，也不用扫描整个表。只需对特定的维( 本例中为行或列) 求和即可，高速的综合 速度正是多维数据库的优势体现。多维立方体结构还可以进行旋转、切片、下钻和上卷等操作，当 然，如果维数过多，人们的想象将受到限制。 3 3o l a p 与数据挖掘 数据挖掘是一种决策支持过程，它从大量的数据中提取隐含的、潜在的、以前未知的有用信息 或模式，它主要基于人工智能、机器学习、统计学及数据库技术。数据挖掘通过分析大量的骧始数 据，作出归纳性的推理。挖掘出潜在的模式并预测客户的行为，帮助公司的决策者调接市场