论文部分内容阅读
【摘要】 本文针对云计算提出了增量更新和协同工作的一种较为新型的数据挖掘更新方式，文章着重介绍了增量更新中基于网络的表格化数据存储和更新方式，以及对一般协同工作算法的稍加修改，通过这种新的数据方式实现避免扫描原始数据库，来实现数据的快速挖掘和更新。
【关键字】 网络遍历 数据挖据 最小阈值 协同工作
一、问题的提出
近年来，随着网络的快速发展以及信息技术的广泛植入，提出了对信息处理能力更高的要求。在这种背景下，数据挖掘领域中的增量网络遍历技术应运而生，网络遍历挖掘是数据挖掘技术在网络信息处理中的应用。网络遍历挖掘是从大量训练样本的基础上得到数据对象间的内在特征，并以此为依据进行有目的的信息提取。但是以上的研究都是以假设数据库为静态的前提的。而事实上，在网络中基本上所有类型的数据库都处在不断的更新（增加、删除、修改）中，所有的支持度阈值也会不断改变，并且动态数据胡往往要求对用户的查询指令做出快速的反应。因此，在网络中，如何提高动态数据库的关联规则，和其遍历的效率成了个重要的问题。
二、关键技术
2.1增量查找技术---网络表格遍历
为了增量的交互的挖掘 Web 访问序列模式，我们通过利用先前的挖掘结果发现新的模式来达到节省挖掘时间的目的，选择一个好的存储结构来储存先前的 挖掘结果很重要。于是我们选择用网格结构来保存先前挖掘结果。图（1）给出了描述了一个含有ABC， ABD，CDA的简单数据库的网格结构。
通过图（1）我们可以很清楚的观察到，如果该数据库的任何一个数据发生了变化，通过该网络表格的存储方式，都可以很快的发现， 避免了完全遍历整个数据库的过程，仅需要根据反馈，遍历部分支路。
本文的算法按照自下而上的顺序由网格结构的第一层向最后一层逐层挖掘来发现。对于任意层 k（k≥1），产生所有的访问模式。每个层 k 中有两个主要步骤：
第一步，当旧的数据从数据库中删除时，相应的网格结构中从每个 k 层节点删除已删除的数据的相关数据，如果出现该节点包含要删除的子数据，则减少该节点支持度。
第二步，当新的数据向数据库中插入时。相应的网格结构中对于每个插入数据 u，把 u 分解成长度为 k 的访问序列，即产生的数据 u 的所有长度为 k 的子序列。参照网站结构，删除子序列中不合格的 k-子序列。检查更新网格结构，如果节点的支持计数为 0，那么将该节点和所有与该节点相关的连接从网格结构中删除。
2.2协同工作计算最小阈值
我们通过MapReduce来对分布式数据进行处理和计算，通过Map（映射）和Reduce（简化）的方式实现数据的并行计算。在云计算的环境下，数据储存和管理都是分布式的，应用系统中的数据库服务器称为数据库节点，每一个数据库节点都具备数据储存、管理和协调作用，能够在每一个节点完成对分布式数据的存取和管理。采用的是基本的分布式数据协同处理方式，分布式数据协同管理的实现机制可以分为协同管理、执行和数据管理三个层次。本文章通过调用简单的分布式数据处理以及添加相应的代码对数据在传输的过程中进行分析和计算，如图（2）所示，指令核心内容是对最小阈值a的计算
三、研究过程以及数据收集
A：未添加增量算法
B：添加了算法
对于新提出的增量算法我们进行了仿真，并且与未添加增量算法的更新方式进行了对比，如下图（3）表所示。
我们设定了传输数据是20M/s，在不考虑其他因素的影响下，我们针对数据的传输进行了初步仿真，并且初始设定最小阈值为68%，并且图（3）中的五组数据都是统一的txt文件格式，其中每组数据变量都为50%，我们不难看出，随着数据的增大，通过网络表格存储方式，来寻找变量的增量算法时间远远小于一般的数据传输所需要的时间。
对于初始最小阈值68%，是我们通多多次试验仿真的结果，如下图我们对于20G的对象，并且数据变量为50%的不同阈值仿真得到的图。
从图 （4）中我们可以发现在阈值为65%-70%左边，随着阈值的增大到数据传输的时间是减少的，然后当阈值从70%增长到80%，我们发现时间增长，甚至会有超过了原本的传输时间，这是因为在阈值低于65%左右时，增量挖掘算法可以较快的在数据库中找到遍量，并且快速的对其进行更新，而当阈值越来越大时，挖掘和数据遍历的时间都需要增加，因此未必比直接覆盖更新更加高效。
图（5）为30G时的不同阈值的仿真，从图（4）（5）中我们可以发现对于三种不同的数据类型，相同的，所需要的数据传输时间也有较大的差别，于是我们添加了协同算法。
在本文章中，我们协同的核心算法是：
{if 遍历数据是发现变量为txt文件，阈值减少2.5%；
if 遍历数据是发现变量为word文件，阈值减少2%；
if 遍历数据是发现变量为excel文件，阈值减少1%；
阈值初始为70%}
最终得出的a为最小阈值。
注：从（4）（5）我们可以发现excel文件传输时间阈值改变的影响最大，而txt文件受阈值改变的影响最想，而最合理的阈值是在65%-70%之间，因此我们做出了如上的核心算法中阈值的推测。
图（6）是本文章提出算法的完整仿真，仿真对象是 20G的数据，其中txt，word，excel的比例为33%，33%，34%。 A： 变量为txt；B：变量为word；C：变量为excel。
我们在本次仿真中统一数据的变量为50%，如果同时出现2中数据类型的变量，则变量均匀分布。例如，同时出现数据类型为txt和word 的变量，则30%位txt变量，30%为word变量。
图（6）为我们所有的仿真数据的统计，我们可以发现基本上，最合适的最小阈值基本满足与核心算法相对应，例如只有txt变量，最小阈值得为67.5%，由图（6）我们可以观察得出，时间最少的在67%-68%之间，误差不大。
四、目前存在的问题
到如今，我们的研究结果还存在两个问题，
1、核心算法包括的数据类型太片面，未包含视频等其他格式的文件。目前打算，是在今后继续深入的进行数据收集，将更多的数据类型能够添加到算法中，如果可以的话，可以将不同的数据在导读数据库是统一进行转码，并且打上节点，考虑到该技术实现的复杂性，本文章并没有涉及到数据库不同数据的转码方式，并且由于核心算法涉及到协同工作分析数据的效率，所以不能一味地添加条件，具体的还需要今后通过更多的仿真来改进。
2、算法的应用性。对于算法的可实现性，我们已经进行的分析和仿真，问题不是很大，但是在后期数据整理的过程中，我们发现如果我们完全贴合现在的数据传输能力，8M/s的传输能力，传输的对象一般1G到10G不等，我们也做了一个仿真，其中变化的数据依旧是50%。
注：A：添加完整算法；B：未添加。
我们可以发现，如果结合实际中的具体情况，本文章提出的算法不适用于过小的数据增量更新，这是由于协同工作的服务器分析数据，调用数据是需要一定的时间，并且增量更新在进行数据遍历的时候也是需要一部分时间的。因此，本文章具体的应用方向主要在云计算的大数据处理，在面对小型的数据处理时有一些累赘。
参 考 文 献
[1]戴炳荣，宋俊典等《云计算环境下式数据处理协同机制的研究》
[2]基于云计算的Web数据挖掘.计算机科学.2011，38
[3] Han J，Kamber M.Data Minng Concepts and techniques. Morgan Kaufmann. San Francisco，2006
【关键字】 网络遍历 数据挖据 最小阈值 协同工作
一、问题的提出
近年来，随着网络的快速发展以及信息技术的广泛植入，提出了对信息处理能力更高的要求。在这种背景下，数据挖掘领域中的增量网络遍历技术应运而生，网络遍历挖掘是数据挖掘技术在网络信息处理中的应用。网络遍历挖掘是从大量训练样本的基础上得到数据对象间的内在特征，并以此为依据进行有目的的信息提取。但是以上的研究都是以假设数据库为静态的前提的。而事实上，在网络中基本上所有类型的数据库都处在不断的更新（增加、删除、修改）中，所有的支持度阈值也会不断改变，并且动态数据胡往往要求对用户的查询指令做出快速的反应。因此，在网络中，如何提高动态数据库的关联规则，和其遍历的效率成了个重要的问题。
二、关键技术
2.1增量查找技术---网络表格遍历
为了增量的交互的挖掘 Web 访问序列模式，我们通过利用先前的挖掘结果发现新的模式来达到节省挖掘时间的目的，选择一个好的存储结构来储存先前的 挖掘结果很重要。于是我们选择用网格结构来保存先前挖掘结果。图（1）给出了描述了一个含有ABC， ABD，CDA的简单数据库的网格结构。
通过图（1）我们可以很清楚的观察到，如果该数据库的任何一个数据发生了变化，通过该网络表格的存储方式，都可以很快的发现， 避免了完全遍历整个数据库的过程，仅需要根据反馈，遍历部分支路。
本文的算法按照自下而上的顺序由网格结构的第一层向最后一层逐层挖掘来发现。对于任意层 k（k≥1），产生所有的访问模式。每个层 k 中有两个主要步骤：
第一步，当旧的数据从数据库中删除时，相应的网格结构中从每个 k 层节点删除已删除的数据的相关数据，如果出现该节点包含要删除的子数据，则减少该节点支持度。
第二步，当新的数据向数据库中插入时。相应的网格结构中对于每个插入数据 u，把 u 分解成长度为 k 的访问序列，即产生的数据 u 的所有长度为 k 的子序列。参照网站结构，删除子序列中不合格的 k-子序列。检查更新网格结构，如果节点的支持计数为 0，那么将该节点和所有与该节点相关的连接从网格结构中删除。
2.2协同工作计算最小阈值
我们通过MapReduce来对分布式数据进行处理和计算，通过Map（映射）和Reduce（简化）的方式实现数据的并行计算。在云计算的环境下，数据储存和管理都是分布式的，应用系统中的数据库服务器称为数据库节点，每一个数据库节点都具备数据储存、管理和协调作用，能够在每一个节点完成对分布式数据的存取和管理。采用的是基本的分布式数据协同处理方式，分布式数据协同管理的实现机制可以分为协同管理、执行和数据管理三个层次。本文章通过调用简单的分布式数据处理以及添加相应的代码对数据在传输的过程中进行分析和计算，如图（2）所示，指令核心内容是对最小阈值a的计算
三、研究过程以及数据收集
A：未添加增量算法
B：添加了算法
对于新提出的增量算法我们进行了仿真，并且与未添加增量算法的更新方式进行了对比，如下图（3）表所示。
我们设定了传输数据是20M/s，在不考虑其他因素的影响下，我们针对数据的传输进行了初步仿真，并且初始设定最小阈值为68%，并且图（3）中的五组数据都是统一的txt文件格式，其中每组数据变量都为50%，我们不难看出，随着数据的增大，通过网络表格存储方式，来寻找变量的增量算法时间远远小于一般的数据传输所需要的时间。
对于初始最小阈值68%，是我们通多多次试验仿真的结果，如下图我们对于20G的对象，并且数据变量为50%的不同阈值仿真得到的图。
从图 （4）中我们可以发现在阈值为65%-70%左边，随着阈值的增大到数据传输的时间是减少的，然后当阈值从70%增长到80%，我们发现时间增长，甚至会有超过了原本的传输时间，这是因为在阈值低于65%左右时，增量挖掘算法可以较快的在数据库中找到遍量，并且快速的对其进行更新，而当阈值越来越大时，挖掘和数据遍历的时间都需要增加，因此未必比直接覆盖更新更加高效。
图（5）为30G时的不同阈值的仿真，从图（4）（5）中我们可以发现对于三种不同的数据类型，相同的，所需要的数据传输时间也有较大的差别，于是我们添加了协同算法。
在本文章中，我们协同的核心算法是：
{if 遍历数据是发现变量为txt文件，阈值减少2.5%；
if 遍历数据是发现变量为word文件，阈值减少2%；
if 遍历数据是发现变量为excel文件，阈值减少1%；
阈值初始为70%}
最终得出的a为最小阈值。
注：从（4）（5）我们可以发现excel文件传输时间阈值改变的影响最大，而txt文件受阈值改变的影响最想，而最合理的阈值是在65%-70%之间，因此我们做出了如上的核心算法中阈值的推测。
图（6）是本文章提出算法的完整仿真，仿真对象是 20G的数据，其中txt，word，excel的比例为33%，33%，34%。 A： 变量为txt；B：变量为word；C：变量为excel。
我们在本次仿真中统一数据的变量为50%，如果同时出现2中数据类型的变量，则变量均匀分布。例如，同时出现数据类型为txt和word 的变量，则30%位txt变量，30%为word变量。
图（6）为我们所有的仿真数据的统计，我们可以发现基本上，最合适的最小阈值基本满足与核心算法相对应，例如只有txt变量，最小阈值得为67.5%，由图（6）我们可以观察得出，时间最少的在67%-68%之间，误差不大。
四、目前存在的问题
到如今，我们的研究结果还存在两个问题，
1、核心算法包括的数据类型太片面，未包含视频等其他格式的文件。目前打算，是在今后继续深入的进行数据收集，将更多的数据类型能够添加到算法中，如果可以的话，可以将不同的数据在导读数据库是统一进行转码，并且打上节点，考虑到该技术实现的复杂性，本文章并没有涉及到数据库不同数据的转码方式，并且由于核心算法涉及到协同工作分析数据的效率，所以不能一味地添加条件，具体的还需要今后通过更多的仿真来改进。
2、算法的应用性。对于算法的可实现性，我们已经进行的分析和仿真，问题不是很大，但是在后期数据整理的过程中，我们发现如果我们完全贴合现在的数据传输能力，8M/s的传输能力，传输的对象一般1G到10G不等，我们也做了一个仿真，其中变化的数据依旧是50%。
注：A：添加完整算法；B：未添加。
我们可以发现，如果结合实际中的具体情况，本文章提出的算法不适用于过小的数据增量更新，这是由于协同工作的服务器分析数据，调用数据是需要一定的时间，并且增量更新在进行数据遍历的时候也是需要一部分时间的。因此，本文章具体的应用方向主要在云计算的大数据处理，在面对小型的数据处理时有一些累赘。
参 考 文 献
[1]戴炳荣，宋俊典等《云计算环境下式数据处理协同机制的研究》
[2]基于云计算的Web数据挖掘.计算机科学.2011，38
[3] Han J，Kamber M.Data Minng Concepts and techniques. Morgan Kaufmann. San Francisco，2006