英语原文共 8 页，剩余内容已隐藏，支付完成后下载完整资料
本科生外文翻译
题 目 数据流分类算法的研究
一种新的数据流分类算法
苏丽
邮箱：sunan971@163.com
西安理工大学
刘红艳
中国西安长庆油田公司
宋振辉
石家庄职业技术学院
邮箱：songzhenhui_sjz@163.com
摘要：关联分类（AC）是基于关联规则的，在静态数据集上显示出超过许多其他分类技术的巨大潜力。同时，当数据流在一个广泛的先进的应用所带来的日益突出时，一个新的挑战被提出。本文介绍和评价一种新的数据流ac-ds关联分类算法，它是基于有损计数估计机制（LC）和界标窗口模型。并且，ac-ds从UCI机器学习库挖掘一些数据集，结果表明该算法是有效的和高效的获得。
关键字：指数-数据流；关联分类；频繁项集
1.介绍
在许多领域，如统计，人工智能，机器学习，和其他学科交叉学科，数据挖掘等，近年来成为一个热点。已经提出并广泛使用的各种数据挖掘技术，是以从大量的复杂数据中找到有用的信息为目的的。由于大量的数据产生，需要解决的数据在一天内是数以百万计，甚至没有限制增长速度的。如何从这些连续的数据流中挖掘有用的信息，正成为我们面临的新挑战。
早期，数据流起源于金融市场。如今，数据流广泛存在于互联网、监控系统、地质、气象、传感器网络等领域。数据流与传统的静态数据流有很大的不同。数据流是无限量的数据，数据连续到达，只能读取一次或几次。因此，需要更新更快的数据流挖掘方法。
数据流挖掘是一种从大量原始数据中找到有价值的信息或知识的技术。与静态数据库挖掘相比，挖掘数据流带来了许多新的挑战。
数据流具有与传统数据库的数据收集模型相比不同的特征。如数据流的连续的生成时间，以及数据流是动态的，并且数据流的到达不能被顺序控制。根据到达顺序，数据流的数据可以被读取和处理。为了提高训练的结果数据的顺序不能改变。
因此，数据流的处理有以下要求：首先，每一个数据元素应该被检查至多一次，因为保持整个流在主存中是不切实际的。其次，数据流中的每个数据元素应该尽可能快地处理。第三，对于挖掘数据流的内存使用情况，即使新的数据元素连续生成，也应该有界。最后，所产生的结果的在线算法应立即可用时，当用户要求进行请求时。
1.1数据流
与传统的数据采集相比，数据流是实时的，连续的，有序的，随时间变化的，无限元组。一个数据流具有以下鲜明特点：A）有序，B）无法重现，C）高速，D）无限，E）高维，F）动态的。
现在让我们描述数据流的概念：
令I={i1，i2，...，im}为一组文字，称为项目。项集是I.An的一个子集套装由m个项目被称为M-项集。让我们假设在一个项集的项目是字典顺序。事务是一个元组，（TID，套装），其中TID是事务的ID。
事务数据流DS={B1，B2，......，BN，...}是块，其中每个块与一个块标识符n相关联的无限序列，N是最新的块BN的识别符。每个数据块Bi由一组以前的，即，铋= [T1，T2，...，Tk的]，其中kgt; 0。因此，数据流的当前长度被定义为CL =| B 1| | B 2| ...| BN|。
项集X的频率表示为freq(X)，是B中支撑X的交易数。X的支集被定义为fre(X)/N，其中N是接收交易数据的总数。X是B中的一个频繁集，如果sup(X)gt;=minSupport，其中minSupport（0 lt;= minSupportlt;=1）是一个用户定义的最小支持阈值。
挖掘数据流的许多算法已经被提出。根据对数据流的处理模型，我们可以研究工作分为三个字段：界标窗口，滑动窗口和阻尼窗。曼梏和Motwani提出单通算法，有损计数，以挖掘频繁项目集，并且该算法是基于公知的Apriori属性。 Yu等提出了一种算法——FDPM，这是从切尔诺夫衍生的，为了通过一个界标窗口近似一套FIs。 Li等人提出了一个单通算法，DSM-FI，为了通过数据流的整个历史挖掘所有的频繁项集。佩德罗多明戈斯和杰夫bull;胡尔腾描述和评价的算法，VFDT，来预测它收到的记录标签。
数据流挖掘的分类是一个具有挑战性的研究领域。有许多问题需要解决，如处理连续属性，概念漂移，取试样的问题，分类精度问题，数据流管理和数据流的预处理。
1）处理连续属性
当数据流分类面临的实时性和内存限制，如何更快，更有效地压缩存储性能，以及如何更有效地压缩存储性能计算的评价函数的覆盖面值得进一步研究。
2）概念漂移
数据流漂移的挖掘理念是数据挖掘中最重要的领域之一。如何更迅速，更准确地判断概念漂移的范围，如何有效地利用概念漂移的采集，保存和大量使用的概念，而概念漂移的趋势需要认真研究。
3）样品取样
虽然Hoeffding取样方法不平等，如何从更少的样本中获得更高的精度，仍然是一个值得研究的问题。
4）分类准确度
高分类精度是所有分类算法的目标。如何提高分类准确率是非常重要的研究。
5）数据流管理
传统的数据库技术极大地推动了信息技术的发展，但传统技术在数据流方面显得无能为力。
6）数据流的预处理
数据流的预处理也需要考虑，如何设计一个轻量级的预处理算法，保证挖掘结果的质量是非常重要的。数据流的处理占据了大多数，如果运行时间，以及如何减少运行时间也很重要。
7）重新使用传统的分类方法
传统的分类如决策规则，贝叶斯分类，反向传播的方法，相关的分类，K近邻分类，实例推理，进化算法，粗糙集方法，模糊集合法等。目前的研究施加一些这些方法的数据流。如何使用这些方法的应用程序的数据流的特征将是非常有价值的。
1.2关联分类
分类已经研究了很多年，它在不同的主题方面得到了广泛的研究，包括统计，模式识别，机器学习，数据挖掘等，这是在数据挖掘和机器学习领域最重要的任务之一。分类主要发现有意义的信息，以满足从数据中的用户关联规则的需要。许多有效的模型和算法已经被提出来解决不同的方面，如支持向量机，决策树，基于规则的分类等问题。
与一些传统的基于规则的算法不同，关联分类尝试从输入数据集挖掘成套频繁模式，给用户指定的最小支持度阈值和/或歧视性的测量，如最小置信度阈值。例如，Apriori和FP-growth现在被广泛使用。
阿格拉瓦尔等提出了关联规则。挖掘关联规则是数据挖掘领域一个非常重要的研究，它用于在数据库中找到项集之间关系。简单来说，关联规则被用于描述属性之间相互作用的程度。随着连续大量收集和储存，对于很多业内人士来说，对从他们的数据库中挖掘关联规则越来越感兴趣。从大量的有趣的关系企业交易记录发现可以帮助很多业务决策。如设计的分类，交叉购物的分析和贱卖。
令I = {i1, i2, ... ..., im}为项的集合。
任务相关的数据集D是数据库事务的集合，其中每个事务T是项目的集合，而且Tsube;I.每一个事务有一个标识符，叫做TID。
设A是一个项集，且T包含A，且仅当Asube; T
关联规则是A B为形式的含义，其中Aisin;I，Bisin;I，和Acap;B=Phi;的含义。对于关联规则A =gt; B.
Support（A=gt;B）=P（Acup;B）.
Confidence(A=gt;B) = P(B | A) =support(A cup;
B)/support(A).
Lift(A =gt;B) = support(A cup; B)/support( A) times;
support( B).
支集为D的比例含有A或B，是关联规则的重要的措施，并解释这条规则在所有的事情有多大的代表性。如果支持较大，关联规则更重要。如果项目集满足最小支持度（min_sup），则它称为频繁项集。
D的可信度是包含A或B 的比例，是关联规则的准确的衡量。预测时，可信度是很自然的选择。它反映了A的前提下给B的关联。
提升率有时称为利息，这是A和B之间发生在同一时间的概率和在假定A和B独立前提A和B也发生的概率的概率。用来衡量A和B 之间的关联，当A和B之间的关联是偏差独立度的。如果提升率接近1，A和B是独立的。如果提升率小于1，这个规则是不是非常有意义的。提升率越大实用意义越大。
近年来，关联规则分类应用取得了良好的效果。这些方法主要是挖掘训练集，并得到一些高品质的规则，然后根据这些规则建立分类和预测标签的新范例。
令D是数据集。令I是集合D中的所有项目，且C是集合类的标签。我们说当一个项目子集X sube; di时，一个数据diisin;D包含X sube; I。一类关联规则（CAR）是形如X→C的含义，其中Xsube;I且cisin;C。
在使用分类训练之后的基础上，在挖掘分类模型的基础上，测试实例。刘兵等人首次提出了交流的方式，命名这种分类为基于关联算法（CBA），用于构建基于一组发现的一类关联规则的分类器。CBA是最经典的关联分类算法之一。实证结果表明，关联分类算法可以比绝对数据集的其它算法有更好的分类精度。然而，这种方法在这两个模式挖掘和特征选择方面需要运行很大的时间量，因为大多数开采频繁模式不是最歧视性的，并且之后将被放弃了。
在AC规则的发现和传统的频繁项集挖掘的区别在于，前者的任务可同时开展不同类别的挖掘规则多频繁项集挖掘的过程。在关联分类（AC）框架下的数据挖掘通常包括两个步骤：
（1）生成所有的类关联规则（CARs），它具有iset ＝ ＞ c的形式，其中ISET是项集，c是一个类。
（2）建立基于所生成的CAR的分类器。一般地，被选择的关联规则的子集，以形成一个分级和基于所述置信度量AC方法来选择规则。
大部分上面的算法被用于发现频繁项集。由于关联分类的基础是频繁模式挖掘，我们还介绍了相关的频繁模式挖掘的定义和符号。其中的一些被用来在数据流决策树分类中。
我们提出一种方法来挖掘关联规则，然后设计一个分类器在本文中。用关联分类判断的数据流是研究的一个新探索区域，其可以被看作是一个进一步扩展到超过数据流挖掘频繁项目集的早期工作。
2．数据流的关联分类
2.1问题的定义
数据流是大量无约束数据元素。由于流数据的独有的特性，大多通用算法不得不通过允许某些错误来牺牲其分析结果的正确性。因此，项集的X的真正的支集由Tsup(X)来表示，是迄今为止可见的事务数，其中项目集类似于一个子集。项集的X的估计支集，表示为Esup（X），是存储在X的存储在由一个扫描方式构成的摘要数据结构的估计支集，其中Esup(X)lt;=Tsup(X)。如果Tsup(X)gt;=Minsupport*CL，则项目集X被称为频繁项集。
因此，给定一个用户自定义的最小支持度minSupport（0 lt;= minSupportlt;= 1）和数据流DS，我们的目标是开发一个单通算法使用尽可能少的主要的标志性窗口模型的数据流进行分类存储器，使之成为可能。
图1 所提出的关联分类算法
2.2 数据流的关联分类算法
图1是提供了整个算法。该算法接受两个用户指定的参数：一个是分支持的支持阈值和另一个是窗口大小Swindow=| Bi |。设N表示流长度，即迄今所看到的记录的数量的当前长度。每次收到一个纪录，我们的算法可以根据从之前的记录中提取的关联规则预测其类的标签。每个规则有一个估计的支持Esup（X），其值比minSupport更大。
对于一个给定的数据块Bi，算法计数项目发生的第一遍确定频繁1项集。只要一套1项集不为空，算法随后进行第二遍找频繁（M 1）项集的工作。当算法得到所有的频繁项集，它会计算规则的自由度，并在内存中对它们进行排序。然后，如果存在分类的请求，分类器将预测记录的类的标签。在绑定的数据块Bi中，内存规则将被修剪，低支持度的规则将被删除。
2.3功能和数据结构
1）数据结构M
该数据结构M是一组的形式的条目（项集，f级（1），f级（2），...，f级（ⅰ），t），其中项目集是有条件的属性，f级（ⅰ）是一个子集，它代表类的大致频率的整数属性i和t是数据块，其中，项集首先出现的数目。最初，M是空的。每当一个新的关联规则（项集，（i）类）到来时，我们考察M欲查看条目MJ是否已经存在。如果存在，我们更新通过由一个递增其相应的频率f级（i）。否则，我们创建了一个新的
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[29317]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
