基于高速無線網(wǎng)絡的云計算平臺上的增量和協(xié)同技術研究

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

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

一、問題的提出

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

二、關鍵技術

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

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

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

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

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

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

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

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

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

A：未添加增量算法

B：添加了算法

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

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

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

從圖 （4）中我們可以發(fā)現(xiàn)在閾值為65%-70%左邊，隨著閾值的增大到數(shù)據(jù)傳輸?shù)臅r間是減少的，然后當閾值從70%增長到80%，我們發(fā)現(xiàn)時間增長，甚至會有超過了原本的傳輸時間，這是因為在閾值低于65%左右時，增量挖掘算法可以較快的在數(shù)據(jù)庫中找到遍量，并且快速的對其進行更新，而當閾值越來越大時，挖掘和數(shù)據(jù)遍歷的時間都需要增加，因此未必比直接覆蓋更新更加高效。

圖（5）為30G時的不同閾值的仿真，從圖（4）（5）中我們可以發(fā)現(xiàn)對于三種不同的數(shù)據(jù)類型，相同的，所需要的數(shù)據(jù)傳輸時間也有較大的差別，于是我們添加了協(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文件傳輸時間閾值改變的影響最大，而txt文件受閾值改變的影響最想，而最合理的閾值是在65%-70%之間，因此我們做出了如上的核心算法中閾值的推測。

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

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

我們在本次仿真中統(tǒng)一數(shù)據(jù)的變量為50%，如果同時出現(xiàn)2中數(shù)據(jù)類型的變量，則變量均勻分布。例如，同時出現(xiàn)數(shù)據(jù)類型為txt和word 的變量，則30%位txt變量，30%為word變量。

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

四、目前存在的問題

到如今，我們的研究結果還存在兩個問題，

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

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

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

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

參 考 文 獻

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

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

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