基于時空約束和小波設(shè)計的非侵入式負載數(shù)據(jù)協(xié)同挖掘算法

鄭憲秋

(山西工程技術(shù)學院 信息工程與大數(shù)據(jù)科學系,山西 陽泉 045000)

0 引 言

數(shù)據(jù)挖掘是知識數(shù)據(jù)發(fā)現(xiàn)過程較為關(guān)鍵的環(huán)節(jié),其原理是將所需數(shù)據(jù)從數(shù)量龐大的數(shù)據(jù)整體中挖掘出來，這種知識提取形式與計算機的應(yīng)用聯(lián)系十分緊密[1]。近幾年來,信息業(yè)界對于數(shù)據(jù)協(xié)同挖掘技術(shù)越來越重視,如何在繁雜的數(shù)據(jù)中將數(shù)據(jù)轉(zhuǎn)化為有用的知識與信息,并且能夠同時實現(xiàn)提取,成為比較重要的研究任務(wù)[2]。

相關(guān)專家對非侵入式負載數(shù)據(jù)協(xié)同挖掘算法進行了深入研究,并已取得一些成果。文獻[3]提出社交網(wǎng)絡(luò)下非結(jié)構(gòu)化數(shù)據(jù)協(xié)同過濾推薦算法改進，通過引入粗集,高速分割負載數(shù)據(jù)和數(shù)據(jù)類項目,將分割后的數(shù)據(jù)與初始數(shù)據(jù)相似性進行對比,對相似度最高的數(shù)據(jù)集進行挖掘,從而實現(xiàn)數(shù)據(jù)推薦，其中最為關(guān)鍵的數(shù)據(jù)挖掘步驟雖然挖掘速度快,但精度不高。文獻[4]提出一種適合大數(shù)據(jù)存儲系統(tǒng)的高效負載均衡算法設(shè)計，該算法考慮優(yōu)先級處理超負載,對系統(tǒng)中的超負載數(shù)據(jù)進行有限平衡處理,實現(xiàn)非侵入式負載數(shù)據(jù)的挖掘，該方法在提高挖掘精度的同時,降低了挖掘?qū)崟r性,難以保證挖掘效率。文獻[5]提出基于MapReduce的頻繁模式挖掘算法的優(yōu)化，使用的FP-growth算法包括Fp-tree構(gòu)建和頻繁模式挖掘2個階段,其中平衡算法用來均衡非侵入式負載數(shù)據(jù),降低數(shù)據(jù)分配的隨機性,挖掘出負載數(shù)據(jù)，提高了挖掘精度。文獻[6]提出大數(shù)據(jù)環(huán)境下基于Hadoop框架的數(shù)據(jù)挖掘算法的研究與實現(xiàn)，該算法采用Hadoop平臺降低挖掘算法的難度且易于管理,通過一種自底向上的深度優(yōu)化策略改進PrePost算法,降低挖掘算法對內(nèi)存造成的開銷,同時采用負載均衡的分組策略,來提高挖掘算法的效率，該算法挖掘效率較高,但挖掘精度仍不理想。文獻[7]提出一種基于Spark框架的并行FP-Growth挖掘算法。該算法進行數(shù)據(jù)分組時,利用負載均衡策略,存入分組數(shù)據(jù)是相應(yīng)頻繁項的編碼，根據(jù)編碼實現(xiàn)數(shù)據(jù)的挖掘，該算法效率較高,但挖掘精度不能滿足要求。文獻[8]提出Hadoop異構(gòu)集群下的負載均衡算法研究，該算法根據(jù)節(jié)點的剩余空間來計算各個節(jié)點的理論空間利用率,調(diào)整節(jié)點的最大負載率,完成負載數(shù)據(jù)的調(diào)用,進而實現(xiàn)負載數(shù)據(jù)的挖掘，該算法對節(jié)點空間利用率進行了改善,但對于數(shù)據(jù)挖掘的精度和效率問題,改善不明顯。文獻[9]提出一種基于MapReduce計算模型的并行關(guān)聯(lián)規(guī)則挖掘算法。該方法對已有的MapReduce計算模型進行分類,在此基礎(chǔ)上從伸縮性、自動負載均衡和自動容錯3個角度對并行關(guān)聯(lián)規(guī)則挖掘算法進行優(yōu)化。文獻[10]提出一種基于時空分析的位置大數(shù)據(jù)挖掘方法，首先對高維位置數(shù)據(jù)采用基于時空約束的頻率剪枝算法進行數(shù)據(jù)清洗,然后提取興趣位置點,再根據(jù)歐式距離劃分與聚類劃分的原理相似性,結(jié)合K-Means聚類實現(xiàn)對地理位置關(guān)系的挖掘。然而上述2種方法的挖掘精度較低,挖掘效果不夠理想。

為解決上述傳統(tǒng)方法存在的問題,提出一種基于時空約束和小波設(shè)計的非侵入式負載數(shù)據(jù)協(xié)同挖掘算法,在篩選非侵入式負載數(shù)據(jù)的基礎(chǔ)上,對數(shù)據(jù)進行集成學習方法的計算,獲取負載數(shù)據(jù)的最優(yōu)解,將最優(yōu)解集進行協(xié)同挖掘CMA算法處理,完成負載數(shù)據(jù)的挖掘與轉(zhuǎn)換,實現(xiàn)非侵入式負載數(shù)據(jù)協(xié)同挖掘。實驗驗證表明,該算法在較大程度上加深了傳統(tǒng)數(shù)據(jù)挖掘算法的深度,利于對非入侵式負載數(shù)據(jù)進行深入研究與知識轉(zhuǎn)換,提高了數(shù)據(jù)挖掘的精確率。

1 非侵入式負載數(shù)據(jù)篩選

初始的非侵入式負載數(shù)據(jù)無法作為挖掘協(xié)同算法的基礎(chǔ)數(shù)據(jù)進行直接運算,因此在算法設(shè)計的前期,需在時空約束條件下對非侵入式負載數(shù)據(jù)進行篩選,以提高數(shù)據(jù)協(xié)同挖掘算法的精度。時空約束條件下非侵入式負載數(shù)據(jù)的篩選是通過對所有基礎(chǔ)數(shù)據(jù)所包含的特征進行加權(quán),既可以增加各基礎(chǔ)數(shù)據(jù)之間的空間區(qū)分度,也可以保證數(shù)據(jù)的時序連貫性。其步驟如下:

(1)確立了解對非侵入式負載數(shù)據(jù)應(yīng)用范圍；

(2)預(yù)留數(shù)據(jù),并對數(shù)據(jù)進行加工整合；

(3)設(shè)計篩選數(shù)據(jù)模型的構(gòu)建方案；

(4)整體知識管理。

1.1 空間約束下的數(shù)據(jù)特征

為增強對數(shù)據(jù)篩選的精度,應(yīng)對基礎(chǔ)數(shù)據(jù)間不相似的特征賦予較大的權(quán)值,對較為相似的特征賦予較小的權(quán)值。假設(shè)f代表數(shù)據(jù)特征,Qf代表篩選目標所包含的特征,Sf代表背景。由于背景Sf是由多個窗口Si組成的,則背景區(qū)域的特征目標值為

(1)

對于特征qf,結(jié)合其在時間t內(nèi)的背景間區(qū)分度Lf,將高區(qū)分度的特征值看作正值,將低區(qū)分度的特征值看作負值,通過歸一化處理使各特征值的權(quán)值分布更加集中,則有

(2)

由于基礎(chǔ)數(shù)據(jù)特征權(quán)值的大小與特征區(qū)分度成正相關(guān)。此方法能增大目標與背景之間的區(qū)分度,因此可通過上述空間約束擴大數(shù)據(jù)分類邊界,增強數(shù)據(jù)篩選過程的魯棒性。

1.2 時間約束的數(shù)據(jù)特征

由于僅考慮空間約束有可能會忽略目標面積變化而導致漏篩選,因此還需建立基礎(chǔ)數(shù)據(jù)的時序特征模型。設(shè)時序特征池為P=[p1,p2,…，pt],pt為時間t時的數(shù)據(jù)特征,對pt創(chuàng)建時序特征權(quán)值為

(3)

式中：λf為示特征qf在時間t時的變化速率。為保證時間約束中數(shù)據(jù)特征具有連貫性,因為時序特征池P中時間越近的數(shù)據(jù)有效性越高,則設(shè)為k遺忘因子,時序特征池P在t時刻的目標特征為

(4)

1.3 時空權(quán)值融合

在得到了空間約束下的特征值W和時間約束下的特征值Q后,將兩類權(quán)值有效融合,設(shè)α代表融合比例系數(shù),t時間的時空約束權(quán)值為

σ=αW+(1-α)Q

(5)

綜上,根據(jù)空間約束下的基礎(chǔ)數(shù)據(jù)特征融合結(jié)果對初始數(shù)據(jù)進行篩選。初始數(shù)據(jù)經(jīng)過篩選后,可以被稱為同原數(shù)據(jù)。經(jīng)過先知經(jīng)驗對數(shù)據(jù)進行下一步分析,在對數(shù)據(jù)進行初始訓練基礎(chǔ)上對數(shù)據(jù)進行整合,獲取變換后的訓練知識模型,并保證其完整性。

2 數(shù)據(jù)集成學習運算處理

在經(jīng)過數(shù)據(jù)的篩選之后,對數(shù)據(jù)進行集成學習,從中找尋數(shù)據(jù)挖掘最佳參數(shù)。首先根據(jù)數(shù)據(jù)管理知識,利用知識技術(shù)手段,將篩選后的數(shù)據(jù)進行加工整合,對顯性與隱性知識進行確定掌控與選擇創(chuàng)造,傳播有效的管理信息[11]。

為得到效果更佳的集成學習結(jié)果,將數(shù)據(jù)集成的個體學習設(shè)備獨立為個體集成學習器,并設(shè)定一定的規(guī)則使得各學習器之間具有較為明顯的差異[12]。給定一個具體數(shù)集,并對數(shù)據(jù)中的訓練數(shù)據(jù)樣本進行數(shù)據(jù)采樣,并由此產(chǎn)生不同的學習子集,同時為每個不同的學習子集設(shè)置相應(yīng)的基礎(chǔ)學習器,由此獲得的訓練模型數(shù)據(jù)具備一定的個體差別性,取得的基礎(chǔ)學習器在較高的幾率上具有差別明顯的特征[13]。若每個學習子集僅得到數(shù)量較少的學習數(shù)據(jù)樣本,即使樣本的差異率較小,但數(shù)據(jù)樣本的數(shù)量較少,最終得到的個體集成學習器無法獲得較為充足的訓練程度。因此,針對此種情況,采取系統(tǒng)自動取樣方法進行處理[14],其采樣示意圖如圖1所示。

圖1 采樣示意圖

系統(tǒng)自動取樣方法的步驟如下:

(1)選取標準數(shù)集A,數(shù)據(jù)及其中所包含的樣本個數(shù)為N,對此數(shù)集進行集中采樣處理,得到的新生數(shù)集用A′表示;

(2)在數(shù)集A中隨機抽取一個數(shù)據(jù)樣本,將該樣本記載到新生數(shù)集中,再將其放回數(shù)集A中,促使該樣本在下一次抽取中仍有被抽中的可能性;

(3)重復以上過程,達到m次,最終獲得含有m個數(shù)據(jù)樣本的新生數(shù)集。

在該過程中,數(shù)據(jù)集A終會有一小部分的樣本在新生數(shù)據(jù)集中出現(xiàn),但另外一部分樣本則不會出現(xiàn)。假設(shè)數(shù)據(jù)樣本在m次采樣中不會被抽取到的概率為φ,其最終獲得的極限表達式為

(6)

在系統(tǒng)自動取樣過程中,原始數(shù)據(jù)集A大約含有1/e的數(shù)據(jù)樣本未重復出現(xiàn)在新生數(shù)據(jù)集中,若文中系統(tǒng)的新生數(shù)集作為訓練數(shù)集而存在,則次訓練數(shù)據(jù)集中至少會存在一半的數(shù)據(jù)樣本無法在新生數(shù)據(jù)集中同時出現(xiàn),可以具備較為完善的數(shù)據(jù)校驗效果[15]。

除此之外,系統(tǒng)自動取樣法可以在原始數(shù)據(jù)集A中同時產(chǎn)生不同的訓練數(shù)據(jù)集,對于集成學習方法的運算過程具有較大的幫助[16]。本文在此基礎(chǔ)上進行進一步的算法支撐研究,將決策樹作為數(shù)據(jù)學習器的基本構(gòu)成部分,并將數(shù)據(jù)系統(tǒng)隨機性添加至數(shù)據(jù)集中,在決策樹的節(jié)點進行數(shù)據(jù)屬性的自行選擇時,摒棄在初始節(jié)點中選擇最佳方式屬性的傳統(tǒng)方法,將每個決策樹的基本節(jié)點進行對準操作,在對準后的節(jié)點中進行方式屬性的集合選擇,選取出一個涵蓋多個方式屬性的數(shù)據(jù)子集,并在選出的數(shù)據(jù)子集中選擇一個最佳方式進行屬性劃分,降低數(shù)據(jù)集成學習運算處理偏差[17]。

3 協(xié)同挖掘CMA算法

協(xié)同挖掘CMA算法不僅為構(gòu)建數(shù)據(jù)挖掘模型,更可以為數(shù)據(jù)挖掘算法模型進行知識數(shù)據(jù)管理的調(diào)整[18]。CMA算法是盲均衡算法中較為常見的一種,在干擾抑制和波束形成等領(lǐng)域應(yīng)用廣泛。本文利用CMA算法設(shè)計恒模小波信號,當每一級的恒模陣捕獲到一個恒模信號后,就會把該信號對消掉,然后把含有其余信號的混合數(shù)據(jù)輸入到下一級恒模陣做相同處理,直到把所有恒模信號捕獲并分離出來,實現(xiàn)數(shù)據(jù)的協(xié)同挖掘。

由于在數(shù)據(jù)知識原則的構(gòu)建階段,算法的復雜程度作為單獨學習模型算法的復雜程度的直線構(gòu)成框架,且獨立學習算法模型是在同原數(shù)據(jù)的數(shù)據(jù)信息基礎(chǔ)上建立的,數(shù)據(jù)與數(shù)據(jù)之間不會發(fā)生數(shù)據(jù)交互現(xiàn)象以及數(shù)據(jù)算法迭代計算現(xiàn)象,因此能夠利用并行數(shù)據(jù)算法進行算法復雜程度的降低操作[19]。

在基于時空約束和小波設(shè)計的非侵入式負載數(shù)據(jù)協(xié)同挖掘算法的設(shè)計中,利用CMA算法設(shè)計恒模小波信號,將標量小波中由單個尺度函數(shù)生成的多分辨空間擴展為由多個尺度函數(shù)生成的多分辨空間,保證更大的挖掘自由度。用多恒模小波表示均衡器,則均衡器的輸出結(jié)果為

(7)

根據(jù)均衡器的輸出結(jié)果,將該信號從接收數(shù)據(jù)中對消掉,然后將其余信號的混合數(shù)據(jù)輸入到下一級恒模陣中,并做相同處理,直到選出所有的恒模小波信號。在此基礎(chǔ)上,導入知識數(shù)據(jù)原則庫中的容量限制條件,在大容量數(shù)據(jù)庫中進行適當?shù)囊?guī)則管理,較為清晰地分辨出小容量數(shù)據(jù)庫中的數(shù)據(jù)耦合度,加大對數(shù)據(jù)庫的容量清理力度,在進行容量清理后,對清理后的數(shù)據(jù)進行數(shù)據(jù)耦合度分析,挑選出耦合度較高的數(shù)據(jù)進行去除,并保留耦合度較低的數(shù)據(jù),進而提高挖掘準確率[20-22]。

4 結(jié)果與分析

為驗證本文基于時空約束和小波設(shè)計的非侵入式負載數(shù)據(jù)協(xié)同挖掘算法的數(shù)據(jù)挖掘效果,與傳統(tǒng)算法進行對比,并分析實驗結(jié)果。

針對非侵入式負載數(shù)據(jù)的性能及數(shù)據(jù)的特殊性,對數(shù)據(jù)進行挖掘,并構(gòu)建協(xié)同挖掘算法模型,如圖2所示。

圖2 協(xié)同挖掘算法模型

根據(jù)上述算法模型,進行實驗參數(shù)的設(shè)定:數(shù)據(jù)來源為公開數(shù)據(jù)庫信息;數(shù)據(jù)置信度為1,最小支持度為0.005;數(shù)據(jù)庫為知識規(guī)則庫;主要數(shù)據(jù)分析方法為關(guān)聯(lián)規(guī)則決策樹分析;數(shù)據(jù)規(guī)則屬性一致。

根據(jù)上述算法模型進行對比實驗,將本文基于時空約束和小波設(shè)計的非侵入式負載數(shù)據(jù)協(xié)同挖掘算法的挖掘效果與傳統(tǒng)的基于MapReduce的頻繁模式挖掘算法的數(shù)據(jù)挖掘效果進行比較,得到的數(shù)據(jù)挖掘深度對比圖與數(shù)據(jù)挖掘準確率對比圖如圖3和4所示。

分析圖3和圖4可知,在相同的實驗條件下,基于時空約束和小波設(shè)計的非侵入式負載數(shù)據(jù)協(xié)同挖掘算法的數(shù)據(jù)挖掘深度隨時間的增加而不斷增大,且增幅較大,準確率較高。而傳統(tǒng)的基于MapReduce的頻繁模式挖掘算法的數(shù)據(jù)挖掘深度雖然也隨時間增加而增大,但增長幅度較小,且挖掘的準確率較低,算法的工作效率不高。

圖3 數(shù)據(jù)挖掘深度對比圖

圖4 數(shù)據(jù)挖掘準確率對比圖

本文算法在較高的程度上對非侵入式負載數(shù)據(jù)進行了全面的分析整理,提高了數(shù)據(jù)挖掘的準確率,并加深了數(shù)據(jù)挖掘的深度,能夠更好地對數(shù)據(jù)進行處理,對數(shù)據(jù)進行精密的評估分析,減少了數(shù)據(jù)的冗雜度,增強了系統(tǒng)對數(shù)據(jù)的分類整理能力,算法簡便快捷,具備更加廣闊地推廣空間。

5 結(jié) 語

本文在傳統(tǒng)算法的基礎(chǔ)上研究了一種新式基于時空約束和小波設(shè)計的非侵入式負載數(shù)據(jù)協(xié)同挖掘算法, 先對所需挖掘的非侵入式負載數(shù)據(jù)進行綜合整理,并對其進行數(shù)據(jù)預(yù)處理,根據(jù)處理后的數(shù)據(jù)得到所需的準確數(shù)據(jù)信息,在此基礎(chǔ)上進行數(shù)據(jù)集成學習算法計算,推算出合理的挖掘參數(shù),降低數(shù)據(jù)的挖掘偏差,同時減少其他因素對挖掘數(shù)據(jù)的干擾,為數(shù)據(jù)的挖掘提供較為有利的挖掘環(huán)境,最后將運算后的數(shù)據(jù)進行協(xié)同挖掘CMA算法處理,對數(shù)據(jù)進行全面的挖掘,加大數(shù)據(jù)的挖掘深度與力度,獲得更加準確的挖掘數(shù)據(jù)信息,實現(xiàn)對非侵入式負載數(shù)據(jù)的精準挖掘。

相對于傳統(tǒng)算法,本文算法在較大程度上提高了數(shù)據(jù)挖掘的準確度以及算法的運行效率,能夠較好的保證數(shù)據(jù)的特征完整性,并提供更加清晰可靠的挖掘數(shù)據(jù)信息,降低數(shù)據(jù)挖掘方差,為使用者提供了更好的挖掘選擇,具有較為優(yōu)越的使用市場,但該算法在算法運算程度上需要進行進一步的改良加強,使其更加簡便,具有更高的使用價值。