【摘要】 本文針對(duì)云計(jì)算提出了增量更新和協(xié)同工作的一種較為新型的數(shù)據(jù)挖掘更新方式，文章著重介紹了增量更新中基于網(wǎng)絡(luò)的表格化數(shù)據(jù)存儲(chǔ)和更新方式，以及對(duì)一般協(xié)同工作算法的稍加修改，通過(guò)這種新的數(shù)據(jù)方式實(shí)現(xiàn)避免掃描原始數(shù)據(jù)庫(kù)，來(lái)實(shí)現(xiàn)數(shù)據(jù)的快速挖掘和更新。

【關(guān)鍵字】 網(wǎng)絡(luò)遍歷 數(shù)據(jù)挖據(jù) 最小閾值 協(xié)同工作

一、問(wèn)題的提出

近年來(lái)，隨著網(wǎng)絡(luò)的快速發(fā)展以及信息技術(shù)的廣泛植入，提出了對(duì)信息處理能力更高的要求。在這種背景下，數(shù)據(jù)挖掘領(lǐng)域中的增量網(wǎng)絡(luò)遍歷技術(shù)應(yīng)運(yùn)而生，網(wǎng)絡(luò)遍歷挖掘是數(shù)據(jù)挖掘技術(shù)在網(wǎng)絡(luò)信息處理中的應(yīng)用。網(wǎng)絡(luò)遍歷挖掘是從大量訓(xùn)練樣本的基礎(chǔ)上得到數(shù)據(jù)對(duì)象間的內(nèi)在特征，并以此為依據(jù)進(jìn)行有目的的信息提取。但是以上的研究都是以假設(shè)數(shù)據(jù)庫(kù)為靜態(tài)的前提的。而事實(shí)上，在網(wǎng)絡(luò)中基本上所有類型的數(shù)據(jù)庫(kù)都處在不斷的更新（增加、刪除、修改）中，所有的支持度閾值也會(huì)不斷改變，并且動(dòng)態(tài)數(shù)據(jù)胡往往要求對(duì)用戶的查詢指令做出快速的反應(yīng)。因此，在網(wǎng)絡(luò)中，如何提高動(dòng)態(tài)數(shù)據(jù)庫(kù)的關(guān)聯(lián)規(guī)則，和其遍歷的效率成了個(gè)重要的問(wèn)題。

二、關(guān)鍵技術(shù)

2.1增量查找技術(shù)---網(wǎng)絡(luò)表格遍歷

為了增量的交互的挖掘 Web 訪問(wèn)序列模式，我們通過(guò)利用先前的挖掘結(jié)果發(fā)現(xiàn)新的模式來(lái)達(dá)到節(jié)省挖掘時(shí)間的目的，選擇一個(gè)好的存儲(chǔ)結(jié)構(gòu)來(lái)儲(chǔ)存先前的 挖掘結(jié)果很重要。于是我們選擇用網(wǎng)格結(jié)構(gòu)來(lái)保存先前挖掘結(jié)果。圖（1）給出了描述了一個(gè)含有ABC， ABD，CDA的簡(jiǎn)單數(shù)據(jù)庫(kù)的網(wǎng)格結(jié)構(gòu)。

通過(guò)圖（1）我們可以很清楚的觀察到，如果該數(shù)據(jù)庫(kù)的任何一個(gè)數(shù)據(jù)發(fā)生了變化，通過(guò)該網(wǎng)絡(luò)表格的存儲(chǔ)方式，都可以很快的發(fā)現(xiàn)， 避免了完全遍歷整個(gè)數(shù)據(jù)庫(kù)的過(guò)程，僅需要根據(jù)反饋，遍歷部分支路。

本文的算法按照自下而上的順序由網(wǎng)格結(jié)構(gòu)的第一層向最后一層逐層挖掘來(lái)發(fā)現(xiàn)。對(duì)于任意層 k（k≥1），產(chǎn)生所有的訪問(wèn)模式。每個(gè)層 k 中有兩個(gè)主要步驟：

第一步，當(dāng)舊的數(shù)據(jù)從數(shù)據(jù)庫(kù)中刪除時(shí)，相應(yīng)的網(wǎng)格結(jié)構(gòu)中從每個(gè) k 層節(jié)點(diǎn)刪除已刪除的數(shù)據(jù)的相關(guān)數(shù)據(jù)，如果出現(xiàn)該節(jié)點(diǎn)包含要?jiǎng)h除的子數(shù)據(jù)，則減少該節(jié)點(diǎn)支持度。

第二步，當(dāng)新的數(shù)據(jù)向數(shù)據(jù)庫(kù)中插入時(shí)。相應(yīng)的網(wǎng)格結(jié)構(gòu)中對(duì)于每個(gè)插入數(shù)據(jù) u，把 u 分解成長(zhǎng)度為 k 的訪問(wèn)序列，即產(chǎn)生的數(shù)據(jù) u 的所有長(zhǎng)度為 k 的子序列。參照網(wǎng)站結(jié)構(gòu)，刪除子序列中不合格的 k-子序列。檢查更新網(wǎng)格結(jié)構(gòu)，如果節(jié)點(diǎn)的支持計(jì)數(shù)為 0，那么將該節(jié)點(diǎn)和所有與該節(jié)點(diǎn)相關(guān)的連接從網(wǎng)格結(jié)構(gòu)中刪除。

2.2協(xié)同工作計(jì)算最小閾值

我們通過(guò)MapReduce來(lái)對(duì)分布式數(shù)據(jù)進(jìn)行處理和計(jì)算，通過(guò)Map（映射）和Reduce（簡(jiǎn)化）的方式實(shí)現(xiàn)數(shù)據(jù)的并行計(jì)算。在云計(jì)算的環(huán)境下，數(shù)據(jù)儲(chǔ)存和管理都是分布式的，應(yīng)用系統(tǒng)中的數(shù)據(jù)庫(kù)服務(wù)器稱為數(shù)據(jù)庫(kù)節(jié)點(diǎn)，每一個(gè)數(shù)據(jù)庫(kù)節(jié)點(diǎn)都具備數(shù)據(jù)儲(chǔ)存、管理和協(xié)調(diào)作用，能夠在每一個(gè)節(jié)點(diǎn)完成對(duì)分布式數(shù)據(jù)的存取和管理。采用的是基本的分布式數(shù)據(jù)協(xié)同處理方式，分布式數(shù)據(jù)協(xié)同管理的實(shí)現(xiàn)機(jī)制可以分為協(xié)同管理、執(zhí)行和數(shù)據(jù)管理三個(gè)層次。本文章通過(guò)調(diào)用簡(jiǎn)單的分布式數(shù)據(jù)處理以及添加相應(yīng)的代碼對(duì)數(shù)據(jù)在傳輸?shù)倪^(guò)程中進(jìn)行分析和計(jì)算，如圖（2）所示，指令核心內(nèi)容是對(duì)最小閾值a的計(jì)算

三、研究過(guò)程以及數(shù)據(jù)收集

A：未添加增量算法

B：添加了算法

對(duì)于新提出的增量算法我們進(jìn)行了仿真，并且與未添加增量算法的更新方式進(jìn)行了對(duì)比，如下圖（3）表所示。

我們?cè)O(shè)定了傳輸數(shù)據(jù)是20M/s，在不考慮其他因素的影響下，我們針對(duì)數(shù)據(jù)的傳輸進(jìn)行了初步仿真，并且初始設(shè)定最小閾值為68%，并且圖（3）中的五組數(shù)據(jù)都是統(tǒng)一的txt文件格式，其中每組數(shù)據(jù)變量都為50%，我們不難看出，隨著數(shù)據(jù)的增大，通過(guò)網(wǎng)絡(luò)表格存儲(chǔ)方式，來(lái)尋找變量的增量算法時(shí)間遠(yuǎn)遠(yuǎn)小于一般的數(shù)據(jù)傳輸所需要的時(shí)間。

對(duì)于初始最小閾值68%，是我們通多多次試驗(yàn)仿真的結(jié)果，如下圖我們對(duì)于20G的對(duì)象，并且數(shù)據(jù)變量為50%的不同閾值仿真得到的圖。

從圖 （4）中我們可以發(fā)現(xiàn)在閾值為65%-70%左邊，隨著閾值的增大到數(shù)據(jù)傳輸?shù)臅r(shí)間是減少的，然后當(dāng)閾值從70%增長(zhǎng)到80%，我們發(fā)現(xiàn)時(shí)間增長(zhǎng)，甚至?xí)谐^(guò)了原本的傳輸時(shí)間，這是因?yàn)樵陂撝档陀?5%左右時(shí)，增量挖掘算法可以較快的在數(shù)據(jù)庫(kù)中找到遍量，并且快速的對(duì)其進(jìn)行更新，而當(dāng)閾值越來(lái)越大時(shí)，挖掘和數(shù)據(jù)遍歷的時(shí)間都需要增加，因此未必比直接覆蓋更新更加高效。

圖（5）為30G時(shí)的不同閾值的仿真，從圖（4）（5）中我們可以發(fā)現(xiàn)對(duì)于三種不同的數(shù)據(jù)類型，相同的，所需要的數(shù)據(jù)傳輸時(shí)間也有較大的差別，于是我們添加了協(xié)同算法。

在本文章中，我們協(xié)同的核心算法是：

{if 遍歷數(shù)據(jù)是發(fā)現(xiàn)變量為txt文件，閾值減少2.5%；

if 遍歷數(shù)據(jù)是發(fā)現(xiàn)變量為word文件，閾值減少2%；

if 遍歷數(shù)據(jù)是發(fā)現(xiàn)變量為excel文件，閾值減少1%；

閾值初始為70%}

最終得出的a為最小閾值。

注：從（4）（5）我們可以發(fā)現(xiàn)excel文件傳輸時(shí)間閾值改變的影響最大，而txt文件受閾值改變的影響最想，而最合理的閾值是在65%-70%之間，因此我們做出了如上的核心算法中閾值的推測(cè)。

圖（6）是本文章提出算法的完整仿真，仿真對(duì)象是 20G的數(shù)據(jù)，其中txt，word，excel的比例為33%，33%，34%。

A： 變量為txt；B：變量為word；C：變量為excel。

我們?cè)诒敬畏抡嬷薪y(tǒng)一數(shù)據(jù)的變量為50%，如果同時(shí)出現(xiàn)2中數(shù)據(jù)類型的變量，則變量均勻分布。例如，同時(shí)出現(xiàn)數(shù)據(jù)類型為txt和word 的變量，則30%位txt變量，30%為word變量。

圖（6）為我們所有的仿真數(shù)據(jù)的統(tǒng)計(jì)，我們可以發(fā)現(xiàn)基本上，最合適的最小閾值基本滿足與核心算法相對(duì)應(yīng)，例如只有txt變量，最小閾值得為67.5%，由圖（6）我們可以觀察得出，時(shí)間最少的在67%-68%之間，誤差不大。

四、目前存在的問(wèn)題

到如今，我們的研究結(jié)果還存在兩個(gè)問(wèn)題，

1、核心算法包括的數(shù)據(jù)類型太片面，未包含視頻等其他格式的文件。目前打算，是在今后繼續(xù)深入的進(jìn)行數(shù)據(jù)收集，將更多的數(shù)據(jù)類型能夠添加到算法中，如果可以的話，可以將不同的數(shù)據(jù)在導(dǎo)讀數(shù)據(jù)庫(kù)是統(tǒng)一進(jìn)行轉(zhuǎn)碼，并且打上節(jié)點(diǎn)，考慮到該技術(shù)實(shí)現(xiàn)的復(fù)雜性，本文章并沒(méi)有涉及到數(shù)據(jù)庫(kù)不同數(shù)據(jù)的轉(zhuǎn)碼方式，并且由于核心算法涉及到協(xié)同工作分析數(shù)據(jù)的效率，所以不能一味地添加條件，具體的還需要今后通過(guò)更多的仿真來(lái)改進(jìn)。

2、算法的應(yīng)用性。對(duì)于算法的可實(shí)現(xiàn)性，我們已經(jīng)進(jìn)行的分析和仿真，問(wèn)題不是很大，但是在后期數(shù)據(jù)整理的過(guò)程中，我們發(fā)現(xiàn)如果我們完全貼合現(xiàn)在的數(shù)據(jù)傳輸能力，8M/s的傳輸能力，傳輸?shù)膶?duì)象一般1G到10G不等，我們也做了一個(gè)仿真，其中變化的數(shù)據(jù)依舊是50%。

注：A：添加完整算法；B：未添加。

我們可以發(fā)現(xiàn)，如果結(jié)合實(shí)際中的具體情況，本文章提出的算法不適用于過(guò)小的數(shù)據(jù)增量更新，這是由于協(xié)同工作的服務(wù)器分析數(shù)據(jù)，調(diào)用數(shù)據(jù)是需要一定的時(shí)間，并且增量更新在進(jìn)行數(shù)據(jù)遍歷的時(shí)候也是需要一部分時(shí)間的。因此，本文章具體的應(yīng)用方向主要在云計(jì)算的大數(shù)據(jù)處理，在面對(duì)小型的數(shù)據(jù)處理時(shí)有一些累贅。

參 考 文 獻(xiàn)

[1]戴炳榮，宋俊典等《云計(jì)算環(huán)境下式數(shù)據(jù)處理協(xié)同機(jī)制的研究》

[2]基于云計(jì)算的Web數(shù)據(jù)挖掘.計(jì)算機(jī)科學(xué).2011，38

[3] Han J，Kamber M.Data Minng Concepts and techniques. Morgan Kaufmann. San Francisco，2006