数据挖掘算法在数据完整性恢复中的设计与实现毕业论文.docx

1、数据挖掘算法在数据完整性恢复中的设计与实现毕业论文数据挖掘算法在数据完整性恢复中的设计与实现摘要随着信息技术和市场的发展，数据库系统都在各个方面得到了广泛的应用。保证数据库的完整性成为了数据库技术中的一个重要课题。当数据库遭受攻击时，撤销并重新执行损坏事物是最常用的机制。这种机制要么停止或极大限制了修理期间的数据库服务，使数据库出现不能接受的完整性损失或拒绝对有严格要求的应用程序服务，要么在联机数据清理时会由新的事物引起更严重的损害传播。在这种情况下，一种在保证数据库可用性同时迅速修复数据库完整性的方法显得尤为重要。本文首先论述了挖掘算法的相关理论知识，以及挖掘算法在数据完整性恢复中的可实施性

2、。然后具体阐述了一种算法思想，利用数据挖掘算法在数据库受到攻击后，实时发现损害的传播模式，限制危害进一步传播，并迅速将数据的完整性恢复。本文选用VC+编程环境，对文中提出的算法思想进行模拟，实现了损害传播模式的分析查找，使现在数据库系统的可用性向前进了一大步。关键词：数据挖掘；数据库；数据完整性；损害传播模式THE DESIGN AND IMPLEMENTATIONOF THE MINING ALGORITHMSIN DATA INTEGRITY RECOVERYAbstractWith the development of information technology the forehea

3、d and the market, the database system has been applied in all aspects。To ensure the integrity of the database has become an important topic in database technology. When the database is under an attack, rolling back and re-executing the damaged transactions are the most used mechanisms during system

4、recovery. This kind of mechanism either stops (or greatly restricts) the database service during repair, which causes unacceptable availability loss or denial-of-service for mission critical applications, or may cause serious damage spreading during on-the-fly recovery where many clean data items ar

5、e accidentally corrupted by legitimate new transactions. In this case, one algorithm , which can guarantee database availability and repair database integrity rapidly at the same time, is particularly important. This paper first discusses the theoretical knowledge related to the data mining, and the

6、 actionability of mining algorithms in data integrity restoration. Then I devise a novel algorithm, in which data mining algorithm is adopted to mine frequent damage spreading patterns when the database is under attack. This algorithm will restrict harm to spread, and quickly restore the integrity o

7、f the data. In this article, I chooses VC+ programming environment to imitate the proposed algorithm, and find the damage spreading patterns, and make the availability of database system go a step further.Keywords : data mining; database; data integrity; damage spreading patterns1绪论1.1课题研究背景数据是知识的源泉

8、。但是,拥有大量的数据与拥有许多有用的知识完全是两回事。过去几年中,从数据库中发现知识这一领域发展的很快。广阔的市场和研究利益促使这一领域的飞速发展。计算机技术和数据收集技术的进步使人们可以从更加广泛的范围和几年前不可想象的速度收集和存储信息。收集数据是为了得到信息,然而大量的数据本身并不意味信息。尽管现代的数据库技术使我们很容易存储大量的数据流,但现在还没有一种成熟的技术帮助我们分析、理解并使数据以可理解的信息表示出来。在过去,我们常用的知识获取方法是由知识工程师把专家经验知识经过分析、筛选、比较、综合、再提取出知识和规则。然而,由于知识工程师所拥有知识的有局限性,所以对于获得知识的可信度就

9、应该打个折扣。目前,传统的知识获取技术面对巨型数据仓库无能为力,数据挖掘技术就应运而生1。数据的迅速增加与数据分析方法的滞后之间的矛盾越来越突出,人们希望在对已有的大量数据分析的基础上进行科学研究、商业决策或者企业管理,但是目前所拥有的数据分析工具很难对数据进行深层次的处理,使得人们只能望“数”兴叹。数据挖掘正是为了解决传统分析方法的不足,并针对大规模数据的分析处理而出现的。数据挖掘通过在大量数据的基础上对各种学习算法的训练,得到数据对象间的关系模式,这些模式反映了数据的内在特性,是对数据包含信息的更高层次的抽象。目前,在需要处理大数据量的科研领域中,数据挖掘受到越来越多的关注,同时,在实际问

10、题中,大量成功运用数据挖掘的实例说明了数据挖掘对科学研究具有很大的促进作用。数据挖掘可以帮助人们对大规模数据进行高效的分析处理,以节约时间,将更多的精力投入到更高层的研究中,从而提高科研工作的效率。1.2国内外研究概况1.2.1数据完整性相关事务处理系统（如数据库系统）已经变得越来越复杂，并且对于大多数的网络基础设施是至关重要的，如银行、电子商务、军事作战，场指挥中心等。数据的可用性和完整性对这些基础设施是至关重要的。然而众所周知的，系统漏洞不能完全消除，高明的攻击者可以利用这些漏洞2。数据库系统从攻击中生存下来的话题最近收到相当重视，因为数据库系统在基于Web的服务中起了越来越重要的作用。人

11、们已经看到因为几个原因产生的越来越多的网络攻击的。举例来说，现在更重要的和有价值的信息通过网络处理，而这些信息是在世界范围内都能访问的。此外，即使充分保护的网络服务也不是很难被攻破。在一般情况下，基于网络的联机事务处理系统往往结合了以下组件：Web服务器，数据库和特定的应用程序代码（例如，服务器端的交易程序）。通常情况下，一方面，骨干软件基础设施（例如，Web服务器和数据库）是有经验的开发人员开发的，这些开发人员具有全面的安全知识3。另一方面，面向应用程序的代码的程序员在严格的进度表情况下开发的，而这些程序员往往是由那些缺乏安全培训。数据密集型应用程序（例如，信用卡帐单，网上证券交易）的经验表

12、明，各种攻击能够成功地骗过传统的保护机制，有许多可能的攻击可能导致数据库系统的完整性和可用性受到影响。基于访问控制和完整性约束的认证技术、并发控制、复制和恢复机制是在目前的数据库系统部署的以保证存储的信息和数据的正确性，可用性和完整性主要途径。然而，这些安全技术在处理与数据腐败入侵是非常有限的。例如，访问控制可以被内部攻击者或伪装身份的外部攻击者颠覆。完整性约束不擅长禁止看似合理的但不正确的数据。1.2.2数据挖掘技术发展概况随着计算机硬件和软件的飞速发展，尤其是数据库技术与应用的日益普及，人们面临着快速扩张的数据海洋，如何有效利用这一丰富数据海洋的宝藏为人类服务，业已成为广大信息技术工作者的

13、所重点关注的焦点之一。与日趋成熟的数据管理技术与软件工具相比，人们所依赖的数据分析工具功能，却无法有效地为决策者提供其决策支持所需要的相关知识，从而形成了一种独特的现象“丰富的数据，贫乏的知识”。为有效解决这一问题，自二十世纪80年代开始，数据挖掘技术逐步发展起来，数据挖掘技术的迅速发展，得益于目前全世界所拥有的巨大数据资源以及对将这些数据资源转换为信息和知识资源的巨大需求，对信息和知识的需求来自各行各业，从商业管理、生产控制、市场分析到工程设计、科学探索等。数据挖掘可以视为是数据管理与分析技术的自然进化产物。自上个世纪六十年代开始，数据库及信息技术就逐步从基本的文件处理系统发展为更复杂功能更

14、强大的数据库系统；七十年代的数据库系统的研究与发展，最终导致了关系数据库系统、数据建模工具、索引与数据组织技术的迅速发展，这时用户获得了更方便灵活的数据存取语言和界面；此外在联机事务处理（OLTP: online transaction processing）4手段的出现也极大地推动了关系数据库技术的应用普及，尤其是在大数据量存储、检索和管理的实际应用领域。自上世纪八十年代中期开始，关系数据库技术被普遍采用，新一轮研究与开发新型与强大的数据库系统悄然兴起，并提出了许多先进的数据模型：扩展关系模型、面向对象模型、演绎模型等；以及应用数据库系统:空间数据库、时序数据库、多媒体数据库等；日前异构数据

15、库系统和基于互联网的全球信息系统也已开始出现并在信息工业中开始扮演重要角色5。被收集并存储在众多数据库中且正在快速增长的庞大数据，已远远超过人类的处理和分析理解能力（在不借助功能强大的工具情况下），这样存储在数据库中的数据就成为“数据坟墓”，即这些数据极少被访问，结果许多重要的决策不是基于这些基础数据而是依赖决策者的直觉而制定的，其中的原因很简单，这些决策的制定者没有合适的工具帮助其从数据中抽取出所需的信息知识。而数据挖掘工具可以帮助从大量数据中发现所存在的特定模式规律，从而可以为商业活动、科学探索和医学研究等诸多领域提供所必需的信息知识。数据与信息知识之间的巨大差距迫切需要系统地开发数据挖掘

16、工具，来帮助实现将“数据坟墓”中的数据转化为知识财富。以上内容如图1-1所示。图1-1数据挖掘进化过程示意描述1.3研究内容、目的和意义一旦数据库系统被攻击，数据库系统与当前的安全技术装备就不能继续提供满意的服务，因为一些数据对象的完整性受到了损害。通过撤消和重做简单地识别和修复这些数据对象在很大程度上仍然不能确保数据的完整性，这主要是因为事务处理系统的一个不显眼的特点，即损害传播。假设T1是一个恶意事务，它的写集包含损坏的数据对象。当事务T2、T3和T4（称为传播事务）读取了被T1更新的数据对象。于是，被T2、T3和T4更新的数据对象也将被损害。通过这种方式，损害将传播出去。我们称事务T2、

17、T3和T4都直接或间接受到了T1的影响6。当前的数据库安全技术在处理损害传播方面是非常有限的。在本文中，我们的目标是就以下问题：当一个数据库系统被入侵检测系统确定为受到攻击后，如何能在“损害传播”被阻止的同时，不断提供数据服务呢？我们讨论事务级的攻击，并假设一个延时有限的良好入侵检测系统是实用的。这些攻击在攻击数据库后会留下一份独特的指纹，即损害传播模式。我们在本文提出一种新型数据库防火墙原型，一个挖掘来频繁损害传播模式算法。有了这些特点，数据库防火墙能够执行一个事务过滤策略，动态过滤掉潜在的传播事务，从而，进一步实现数据库系统在不间断提供数据服务的同时，找出数据库中完整性受到损害的数据对象并

18、修复，大大提高了现代数据库系统的可用性。2挖掘算法如何用于完整性恢复我们假定数据库的入侵检测系统是优秀，可以信赖的。因此，当数据库被攻击后，在有限的延迟时间内入侵检测系统能够告知我们数据库遭到攻击,并找到攻击的源头。我们假定攻击的源头是T1。由于我们要实现在数据库不间断数据服务的同时，对数据库的完整性进行修复，因此由此攻击引起的完整性损害将会在一定时间延迟内继续传播下去。假设T1是一个恶意事务，它的写集包含损坏的数据对象。当事务T2、T3和T4（称为传播事务）读取了被T1更新的数据对象。于是，被T2、T3和T4更新的数据对象也将被损害。通过这种方式，损害将传播出去。我们称事务T2、T3和T4都

19、直接或间接受到了T1的影响。像这样的危害传播，都会留下一个特殊的印记，我们称之为损害传播模式。数据库系统为解决完整性损害的问题，会将数据库的所有操作记录下来。也就是说，在操作历史中我们可以看到所有事务的动作，包括恶意事务，因此我们可以在操作历史中找到损害传播模式7。损害传播模式以一种事务序列的形式存在。而我们需要做的就是找到这个传播序列，抑制其在数据库系统中继续传播损害，并修复数据的完整性。我们知道，数据库内数据对象的改变会影响跟它有亲密关系的一些数据对象。而这种联系就为我们用数据挖掘的方法寻找恶意传播序列提供了依据。按照这种联系，我们可以把较为亲密的数据对象聚类在一起，我们称之为岛。明显的，

20、岛内的数据对象之间要远大于岛与岛之间数据对象的影响。其中，存在与岛内的数据对象之间的影响称之为单重跳跃传播模式，存在于岛与岛之间数据对象的影响称之为多重跳跃传播模式。基于这一观察，我们发现，类似的攻击，攻击的历史也有类似的损害传播模式。可以看出，如果确定如此频繁扩散的模式，基于模式的完整性估计可以用于访问策略可以快速和动态地筛选出潜在的损害蔓延跨行动，而数据库系统能够在面对攻击的同时不间断提供数据服务。3数据挖掘的基本原理我们先对数据挖掘的定义进行讲解，然后通过一个故事来了解数据挖掘在我们生活中的应用，在介绍几种数据挖掘的方法任务，最后介绍数据挖掘的流程。3.1数据挖掘的定义数据挖掘就是从大量

21、的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。这些数据可以是结构化的，也可以是半结构化的。发现知识的方法可以是数学的， 也可以是非数学的， 可以是演绎的，也可以是归纳的。发现了的知识可以被用于信息管理、查询优化、决策支持、过程控制等，还可以进行数据自身的维护。数据挖掘的过程是一个“发现”的过程，而不是“发明”的过程。换句话说，数据挖掘所探寻的模式，是一种已有的、只是隐藏在数据中、暂时没有被发现的知识7。数据挖掘（Data Mining）是一个多学科交叉研究领域，它融合了数据库（Database）技术、人工智能（Artific

22、ial Intelligence）、机器学习（Machine Learning）、高性能计算（High-Performance Computing）、知识工程（Knowledge Engineering）、统计学（Statistics）、信息检索（Information Retrieval）、面向对象方法（Object-Oriented Method）以及数据可视化（Data Visualization）等最新技术的研究成果。经过十几年的研究，产生了许多新方法和新概念。尤其是最近几年，大部分基本方法和概念越来越清晰了，它们的研究正逐步向着更深入的地方发展。数据挖掘之所以被大家称为是未来处理信息

23、的中坚技术之一，主要在于它是以一种通过新概念来改变着人们使用数据的方式。在20世纪，数据库技术取得了关键性的胜利而且它已经广泛的应用于我们的生活中。但是，数据库技术作为一种基本的信息存储和管理方式，仍然以联机事务处理为核心应用，缺少对决策、分析、预测等高级功能的支持以及分类、聚类等复杂应用成为必然。面对这一问题，数据挖掘和知识发现使得数据处理的技术进入了一个崭新的高度。它不仅能对以往的数据进行查询，而且能够找出以往数据之间的潜在联系，然后进行更多的分析操作，以便更好地做出理想的决策并预测未来的发展趋势等。通过数据挖掘，我们则可以把有价值的知识、规则和高层次的数据信息从数据库的相关集合中抽取出，

24、从而使大型数据库成为一个可靠的、丰富的源信息然后可以为提取知识提供服务8。特别需重点指出的是，数据挖掘的技术的开发目标就是要面向应用的。它不仅仅只是面对特定数据库的简单调用、查询和检索，而且它还要对这些数据进行宏观、中观乃至微观的分析、推理、统计和综合。知识发现在这里所要表达的不是要求我们发现的是万物而皆准的真理，也不是为了去发现新的数学的公式或者自然科学的定理。我们发现的都是相对而言的知识，是面向特定领域的，而且我们还需确保发现的知识是能够易于被用户理解的。3.2 数据挖掘的有趣故事和关联规则3.2.1数据挖掘的有趣故事数据挖掘的价值是随时随地都能够体现的。也许在我们平时的一些小事上，我们通

25、过数据挖掘就能够获取到事情背后隐藏的信息，然后通过这些信息，我们能够对这件事进行更好的处理。接下来我们看个简单的例子，通过这个例子，我们可以更加形象的了解数据挖掘对我们生活的重要性。在一家超市里，有一个有趣的现象：尿布和啤酒赫然摆在一起出售。但是这个奇怪的举措却使尿布和啤酒的销量双双增加了。这不是一个笑话，而是发生在美国沃尔玛连锁店超市的真实案例，并一直为商家所津津乐道。沃尔玛拥有世界上最大的数据仓库系统，为了能够准确了解顾客在其门店的购买习惯，沃尔玛对其顾客的购物行为进行购物篮分析，想知道顾客经常一起购买的商品有哪些。沃尔玛数据仓库里集中了其各门店的详细原始交易数据。在这些原始交易数据的基础

26、上，沃尔玛利用数据挖掘方法对这些数据进行分析和挖掘。一个意外的发现是：跟尿布一起购买最多的商品竟是啤酒！经过大量实际调查和分析，揭示了一个隐藏在尿布与啤酒背后的美国人的一种行为模式：在美国，一些年轻的父亲下班后经常要到超市去买婴儿尿布，而他们中有30%40%的人同时也为自己买一些啤酒。产生这一现象的原因是：美国的太太们常叮嘱她们的丈夫下班后为小孩买尿布，而丈夫们在买尿布后又随手带回了他们喜欢的啤酒9。按常规思维，尿布与啤酒风马牛不相及，若不是借助数据挖掘技术对大量交易数据进行挖掘分析，沃尔玛是不可能发现数据内在这一有价值的规律的。数据关联是数据库中存在的一类重要的可被发现的知识。若两个或多个变

27、量的取值之间存在某种规律性，就称为关联。关联可分为简单关联、时序关联、因果关联。关联分析的目的是找出数据库中隐藏的关联网。有时并不知道数据库中数据的关联函数，即使知道也是不确定的，因此关联分析生成的规则带有可信度。关联规则挖掘发现大量数据中项集之间有趣的关联或相关联系。Agrawal等于1993年首先提出了挖掘顾客交易数据库中项集间的关联规则问题，以后诸多的研究人员对关联规则的挖掘问题进行了大量的研究。他们的工作包括对原有的算法进行优化，如引入随机采样、并行的思想等，以提高算法挖掘规则的效率；对关联规则的应用进行推广。关联规则挖掘在数据挖掘中是一个重要的课题，最近几年已被业界所广泛研究。3.2

28、.2关联规则挖掘的过程关联规则挖掘过程主要包含两个阶段：第一阶段必须先从资料集合中找出所有的高频项目组(Frequent Item sets)，第二阶段再由这些高频项目组中产生关联规则(Association Rules)。关联规则挖掘的第一阶段必须从原始资料集合中，找出所有高频项目组(Large Item sets)。高频的意思是指某一项目组出现的频率相对于所有记录而言，必须达到某一水平。一项目组出现的频率称为支持度(Support)，以一个包含A与B两个项目的2-itemset为例，我们可以经由公式求得包含A,B项目组的支持度，若支持度大于等于所设定的最小支持度(Minimum Suppo

29、rt)门槛值时，则A,B称为高频项目组。一个满足最小支持度的k-item set，则称为高频k-项目组(Frequent k-item set)，一般表示为Large k或Frequent k。算法并从Large k的项目组中再产生Large k+1，直到无法再找到更长的高频项目组为止。关联规则挖掘的第二阶段是要产生关联规则(Association Rules)。从高频项目组产生关联规则，是利用前一步骤的高频k-项目组来产生规则，在最小信赖度(Minimum Confidence)的条件门槛下，若一规则所求得的信赖度满足最小信赖度，称此规则为关联规则。例如：经由高频k-项目组A,B所产生的规则

30、AB，其信赖度可经由另一公式求得，若信赖度大于等于最小信赖度，则称AB为关联规则。就沃尔马案例而言，使用关联规则挖掘技术，对交易资料库中的纪录进行资料挖掘，首先必须要设定最小支持度与最小信赖度两个门槛值，在此假设最小支持度min_support=5% 且最小信赖度min_confidence=70%。因此符合此该超市需求的关联规则将必须同时满足以上两个条件。若经过挖掘过程所找到的关联规则尿布，啤酒，满足下列条件，将可接受尿布，啤酒的关联规则。用公式可以描述Support(尿布，啤酒)=5%且Confidence(尿布，啤酒)=70%。其中，Support(尿布，啤酒)=5%于此应用范例中的意义

31、为:在所有的交易纪录资料中，至少有5%的交易呈现尿布与啤酒这两项商品被同时购买的交易行为。Confidence(尿布，啤酒)=70%于此应用范例中的意义为:在所有包含尿布的交易纪录资料中，至少有70%的交易会同时购买啤酒。因此，今后若有某消费者出现购买尿布的行为，超市将可推荐该消费者同时购买啤酒。这个商品推荐的行为则是根据尿布，啤酒关联规则，因为就该超市过去的交易纪录而言，支持了“大部份购买尿布的交易，会同时购买啤酒”的消费行为。从上面的介绍还可以看出，关联规则挖掘通常比较适用与记录中的指标取离散值的情况。如果原始数据库中的指标值是取连续的数据，则在关联规则挖掘之前应该进行适当的数据离散化（实

32、际上就是将某个区间的值对应于某个值），数据的离散化是数据挖掘前的重要环节，离散化的过程是否合理将直接影响关联规则的挖掘结果。3.2.3关联规则的分类按照不同情况，关联规则可以进行分类如下：1.基于规则中处理的变量的类别，关联规则可以分为布尔型和数值型。2.基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。3.基于规则中涉及到的数据的维数，关联规则可以分为单维的和多维的。3.2.4关联规则挖掘的相关算法1.Apriori算法：使用候选项集找频繁项集Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。其核心是基于两阶段频集思想的递推算法10。该关联规则在分类上属于单维、单层、布尔关联规则。在这里，所有支持度大于最小支持度的项集称为频繁项集，简称频集。该算法的基本思想是：首先找出所有的频集，这些项集出现的频繁性至少和预定义的最小支持度一样。然后由频集产生强关联规则，这些规则必须满足最小支持度和最小可信度。然后使用第1步找到的频集产生期望的规则，产生只包含集合的项的所有规则，其中每一条规则的右部只有一项，这里采用的是中规则的定义。一旦这些规则被生成，那么只有那些大于用户给定的最小可信度的规则