信息系統(tǒng)的數(shù)據(jù)庫指標(biāo)多維度異常發(fā)現(xiàn)算法分析

郝成亮 劉超 劉洪波 臧洪睿 王宇

摘要：當(dāng)今，信息化建設(shè)快速發(fā)展，數(shù)據(jù)庫作為信息系統(tǒng)的重要組成部分，是信息系統(tǒng)穩(wěn)定運行的重要保障條件之一。隨著數(shù)據(jù)庫種類和數(shù)量的不斷增加以及IT架構(gòu)越來越復(fù)雜，也直接增加了信息系統(tǒng)運維人員的工作量和工作難度，同時提出了更高的運維要求，從而使得數(shù)據(jù)庫的故障處理難度急劇增長。為了提升數(shù)據(jù)庫缺陷分析能力，故障處置，本文將分析比較五種數(shù)據(jù)庫指標(biāo)多維度異常的相關(guān)算法，并在這些算法的基礎(chǔ)上提出更加適合電力信息系統(tǒng)的數(shù)據(jù)庫指標(biāo)多維度異常發(fā)現(xiàn)的算法。

關(guān)鍵詞：信息系統(tǒng);數(shù)據(jù)庫;多維度異常;檢測算法

中圖分類號：TP311? ? ? 文獻標(biāo)識碼：A

文章編號：1009-3044（2020）35-0018-03

開放科學(xué)（資源服務(wù)）標(biāo)識碼（OSID）：

隨著社會信息化的高速發(fā)展建設(shè)，信息系統(tǒng)所承接的業(yè)務(wù)也越來越多，種類也越來越復(fù)雜多樣。大量的業(yè)務(wù)數(shù)據(jù)都需要信息系統(tǒng)中的數(shù)據(jù)庫來進行存儲。因此，數(shù)據(jù)庫作為信息系統(tǒng)的“倉庫”，是能夠支撐系統(tǒng)健康穩(wěn)定運行的重要保障。然而為了存儲海量數(shù)據(jù)，數(shù)據(jù)庫的數(shù)量是不斷增加的，種類也更加多元化，再加上IT架構(gòu)復(fù)雜性的增長，運維人員疲于應(yīng)付巡檢和故障檢修，從而使得數(shù)據(jù)庫的故障處理難度急劇增長。

由于數(shù)據(jù)庫關(guān)聯(lián)分析的指標(biāo)較為固定，因此關(guān)聯(lián)分析方法主要從頻繁模式的生成和篩選上有所改變，這其中還涉及數(shù)據(jù)中心數(shù)據(jù)類型與傳統(tǒng)關(guān)聯(lián)分析的數(shù)據(jù)類型有所差異的問題，例如運維系統(tǒng)產(chǎn)生的告警數(shù)據(jù)往往包含事件描述，事件發(fā)生的時間，這在傳統(tǒng)關(guān)聯(lián)分析中都是不曾出現(xiàn)的。

1 五種算法介紹

1.1 Apriori算法

Apriori算法是最早也是最經(jīng)典的頻繁項集挖掘算法，它作為一種先驗算法可以在一堆數(shù)據(jù)集中尋找數(shù)據(jù)之間的某種聯(lián)系，即從大量數(shù)據(jù)中找出不同項的關(guān)聯(lián)規(guī)則。因此可應(yīng)用的領(lǐng)域相對廣泛。例如，商業(yè)活動中顧客的消費數(shù)據(jù)挖掘;網(wǎng)絡(luò)中入侵攻擊檢測;高校學(xué)生信息數(shù)據(jù)管理及移動通信中用戶特征推薦等。以便商場掌握顧客的消費情況，然后商場可通過這些有價值的數(shù)據(jù)來提升自己的服務(wù)，如促銷活動、庫存商品管理、消費者關(guān)系維護等。通過數(shù)據(jù)關(guān)聯(lián)性分析和挖掘，作為決策制定的重要參考價值。

（1）商業(yè)活動數(shù)據(jù)挖掘

在商業(yè)活動中，企業(yè)利用Apriori算法處理日常運營中所積累的消費者海量交易數(shù)據(jù)。通過對這些數(shù)據(jù)進行深度挖掘和分析，能夠獲得不同產(chǎn)品之間的價格關(guān)系，從而企業(yè)可根據(jù)數(shù)據(jù)掌握顧客的消費習(xí)慣及趨勢，進而企業(yè)可進行定向的推廣服務(wù)和活動，從而節(jié)約了成本預(yù)算并可帶來更大的收益。

（2）網(wǎng)絡(luò)安全檢測

在網(wǎng)絡(luò)安全中，可利用Apriori算法通過自學(xué)習(xí)的方式對網(wǎng)絡(luò)用戶的行為進行檢測，以發(fā)現(xiàn)網(wǎng)絡(luò)入侵攻擊行為，并快速鎖定攻擊者。因此提高了網(wǎng)絡(luò)安全地檢測效率，提高了網(wǎng)絡(luò)的安全性。

（3）高校學(xué)生數(shù)據(jù)管理

在高校中，由于學(xué)生數(shù)量眾多，個人信息各不相同，如籍貫、專業(yè)、家庭情況等，因此增加了學(xué)校管理部門的工作難度。因此學(xué)校管理部門在工作當(dāng)中可利用Apriori算法來進行學(xué)生相關(guān)數(shù)據(jù)的管理工作，并可對學(xué)生數(shù)據(jù)信息進行快速挖掘，從而輔助高校管理部門快速獲得需求數(shù)據(jù)，準(zhǔn)確獲得相關(guān)信息，提高了工作效率。

（4）移動通信

隨著移動網(wǎng)絡(luò)的快速發(fā)展，移動通信領(lǐng)域的服務(wù)也越來越多樣化。通常運營商利用Apriori算法，對電信增值服務(wù)中的數(shù)據(jù)進行深度挖掘來回去用戶特征和用戶習(xí)慣，從而間接地反映了市場特點和趨勢。這些數(shù)據(jù)也可以為運營商提供輔助參考，方便其在業(yè)務(wù)運營和業(yè)務(wù)方面做出合適的決策。

Apriori算法作為基于關(guān)聯(lián)規(guī)則的頻繁項集算法，其通過在候選項集合是掃描檢測中進行遞推計算。在這種算法中，頻繁項集是指其中所有支持度大于最小支持度的項集。

Apriori算法采用的是層次搜索的迭代方法，因此避免了復(fù)雜的理論推導(dǎo)過程，只需簡單的處理即可實現(xiàn)。但因為層次搜索迭代方法，也帶來了一定的缺點，如：

需要對數(shù)據(jù)庫進行多次掃描;

會導(dǎo)致在數(shù)據(jù)挖掘過程中產(chǎn)生較多的中間項集合;

僅使用唯一支持度;

算法的適應(yīng)面廣度不夠。

1.2 FP-growth算法

FP-Growth算法是一種基于Apriori原理的關(guān)聯(lián)結(jié)構(gòu)分析算法，其通過將數(shù)據(jù)存儲在一種叫模式樹（Frequent Pattern Tree）的數(shù)據(jù)結(jié)構(gòu)上來發(fā)現(xiàn)頻繁項集。其中，F(xiàn)P-tree是一種由頻繁項頭表和前綴樹構(gòu)成的。FP-Growth算法則基于以上的結(jié)構(gòu)加快了挖掘過程。

FP-Growth算法的作用是用于發(fā)現(xiàn)數(shù)據(jù)集中頻繁模式，因為其利用了Apriori算法的原理，并只對數(shù)據(jù)集進行兩次掃描，因此加快了數(shù)據(jù)的挖掘過程，運行速率更快。在FP-Growth算法中，數(shù)據(jù)集都集中存儲在頻繁模式樹中，隨后可通過查找元素項的條件基和構(gòu)建條件頻繁模式樹來發(fā)現(xiàn)頻繁項集，重復(fù)執(zhí)行該動作后，最終在頻繁模式樹中只包含了一個元素，其包含以下步驟：

（1）為每個頻繁項構(gòu)建條件投影數(shù)據(jù)庫和投影頻繁模式樹;

（2）對每個新構(gòu)建的頻繁模式樹重復(fù)（1）中的工作，最終新構(gòu)建的頻繁模式樹為空或只包含一條路徑;

（3）若最終獲得的頻繁模式樹為空，則其前綴可視為FP。若其只包含一條路徑，則通過列舉出所有可能的組合并與此樹的前綴連接即可得到FP。

與Apriori算法是通過生成候選項集再進行頻繁檢測相比，F(xiàn)P-Growth算法是將數(shù)據(jù)集都存儲在頻繁模式樹中來發(fā)現(xiàn)頻繁項集或頻繁相對。因此，F(xiàn)P-Growth算法的執(zhí)行速度要比Apriori算法快兩個數(shù)量級以上。

1.3 DLG算法

DLG（Directed Link Graph）算法即引入了關(guān)聯(lián)圖結(jié)構(gòu)，采用的是鄰接表存儲方式。它的原理是當(dāng)k>=3時，則對頻繁k-1項集進行掃描，并將這些候選集在關(guān)聯(lián)圖中連接生成，當(dāng)k<3時，候選集仍需要由Apriori算法生成。

與Apriori算法相比，DLG算法的優(yōu)點是可以通過關(guān)聯(lián)圖連接各節(jié)點，從而快速找出候選集，進行反復(fù)使用，但是它的缺點依然明顯，即在判定頻繁集擴展節(jié)點的過程時，仍然需要對數(shù)據(jù)庫進行反復(fù)的掃描，并且在項集小于3時仍是采用Apriori的連接方法，因此中間的工作量并沒有減少，效率并沒有提高。

1.4 FUP算法

增量關(guān)聯(lián)規(guī)則挖掘（Fast Update Pattern）算法的提出同樣是基于關(guān)聯(lián)規(guī)則的概念，并且根據(jù)了Apriori算法以及實際情況中數(shù)據(jù)集不斷增大的情況。因此，F(xiàn)UP算法在創(chuàng)建候選集的步驟中也使用了Apriori算法連接步驟。

而與Apriori算法不同之處在于FUP算法同時將數(shù)據(jù)集增量的情況考慮了進去。當(dāng)數(shù)據(jù)庫更新時，利用FUP算法無須再對原有數(shù)據(jù)集進行重新執(zhí)行動作，在原有數(shù)據(jù)集上已發(fā)現(xiàn)的頻繁集基礎(chǔ)上進行更新。因此，避免了重復(fù)掃描的過程，提高了工作效率。

1）FUP算法的定義

假設(shè)DB為原數(shù)據(jù)集，db為新增數(shù)據(jù)集，[Lk]為DB的k項集，[Ck]為DB和db中的候選k項集。

2）算法步驟：

（1）對于原始數(shù)據(jù)集DB進行支持度計數(shù)，得到初始頻繁1項集;

（2）在產(chǎn)生候選k項集合[Ck]時，對于新增數(shù)據(jù)集db，重新計算頻繁k項集的[Lk]，并指出其中不滿足支持度的項目;

（3）迭代進行步驟（2）， 直至算法不再產(chǎn)生新的候選集合。

1.5 FIUA2算法

快速增量更新算法（Fast Incremental Update Algorithm）是基于樹結(jié)構(gòu)的關(guān)聯(lián)規(guī)則，針對增量項集提出的更新算法，即在最小支持度不變的情況下，將新增數(shù)據(jù)集db添加到原數(shù)據(jù)集DB中時，增量更新的挖掘。

FIUA2算法的原理是基于樹結(jié)構(gòu)算法，并保留了樹結(jié)構(gòu)算法在原數(shù)據(jù)集DB中的頻繁項集，無須再產(chǎn)生新的候選項集，在挖掘過程中只需要獲取新增數(shù)據(jù)集db中的新增頻繁項集k，因此新的結(jié)果為原數(shù)據(jù)集中的頻繁項集與新增數(shù)據(jù)集中的新增頻繁項集的并集。

FIUA2算法與前文提到的樹結(jié)構(gòu)算法類似，因而同樣會面臨因為樹的子節(jié)點過多導(dǎo)致的算法效率低的問題。

2 五種算法的比較

2.1 Apriori算法

Apriori算法使用了其本身的性質(zhì)來生產(chǎn)候選項集，雖然在產(chǎn)生候選項目集時循環(huán)產(chǎn)生的組合過多，但很大程度上壓縮了頻繁集的大小，提升了檢測的性能和相關(guān)異常指標(biāo)的監(jiān)測精度。在解決復(fù)雜環(huán)境下，問題的快速發(fā)現(xiàn)和提前預(yù)判方面，提供了有價值的參考決策，顯著降低了故障對業(yè)務(wù)運行的影響。雖然Apriori算法不能較大程度地提高工作人員的工作效率，但在工作質(zhì)量方面卻提供了有力保證。因此，通過使用Apriori算法可實現(xiàn)故障的快速診斷和精確定位，并能夠最大限度降低故障對業(yè)務(wù)運行的影響，提升運維能力的自動化、智能化技術(shù)水平，實現(xiàn)信息系統(tǒng)運維工作從“事后堵漏式補救”向“事先主動式管理”的運維模式轉(zhuǎn)變。

2.2 Fp-growth算法

Fp-growth算法是利用樹形結(jié)構(gòu)，省去了產(chǎn)生候選頻繁集的過程，直接得到頻繁集，一定程度上減了少數(shù)據(jù)庫的掃描次數(shù)，從而提高了算法的效率。但是算法擴展性相對于其他算法來說不夠優(yōu)秀，在解決復(fù)雜環(huán)境下的問題或者故障的快速診斷和定位方面，無法做到高精準(zhǔn)應(yīng)對。

2.3 DLG算法

與Apriori算法和Fp-growth算法相比較，DLG算法實際上并沒有減少候選集合生成的數(shù)量，仍需要對數(shù)據(jù)庫進行多次掃描，因此并未正在提高工作效率。此外，在數(shù)據(jù)庫智能化運維方面進行應(yīng)用時，在異常指標(biāo)監(jiān)測和故障快速定位方面的精度并沒有顯著的提高，在日常運行的效率方面仍然與Arpior算法有不小的差距。

2.4 FUP算法

FUP算法的支持度計數(shù)操作除了通過對數(shù)據(jù)庫的記錄執(zhí)行字符串比較函數(shù)進行逐行掃描外，還對其進行了修剪操作，候選集的生成由Apriori算法連接來獲得，F(xiàn)UP算法與Apriori算法的作用一樣，在提高工作人員工作質(zhì)量，以及降低故障對業(yè)務(wù)運行的影響方面都具有比較優(yōu)異的性能。但是與Apriori算法相比較，F(xiàn)UP算法又增加了修剪操作等一些額外的操作，因此在運行效率方面沒有Apriori算法更加高效。

2.5 FIUA2算法

FIUA2算法在運行效率方面要強于其他算法，但是實現(xiàn)比較困難，在某些數(shù)據(jù)集上性能會下降。因此不滿足數(shù)據(jù)庫智能運維技術(shù)普遍應(yīng)用的具體需求，并且較大的實現(xiàn)難度使得工作質(zhì)量難以得到有效的保障。

3 MADA算法

基于前文的五種算法的介紹和比較可以發(fā)現(xiàn)，在數(shù)據(jù)庫智能化運維方面，Apriori算法相對于Fp-growth算法、DLG算法、FUP算法、FIUA2算法不僅能夠最大限度地降低故障對業(yè)務(wù)運轉(zhuǎn)的影響，提升運維人員工作質(zhì)量，并且能夠提升信息系統(tǒng)運維能力的自動化、智能化技術(shù)水平，在對運維人員工作效率的提升方面相對于其他算法也沒有顯著降低，具備著最好的綜合性能。

因此，在Apriori算法基礎(chǔ)上本文提出改進后的MADA數(shù)據(jù)庫指標(biāo)多維度異常發(fā)現(xiàn)算法（Multi-dimensional anomaly detection algorithm for database indicators）。與Apriori算法類似，MADA算法是通過對數(shù)據(jù)庫的每個項進行掃描，并抓取其中滿足最小支持度條件的項，在其中挖掘頻繁a項集的集合，并將該集合標(biāo)記為La;然后，在La中找出頻繁b項集的集合Lb，接著利用Lb找出Lc，以此類推，直到不能再找到頻繁n項集。其中，每找出一個Ln需要對數(shù)據(jù)庫進行一次掃描。

3.1 MADA算法概念

1）定義[item_k（k=1，2，...，m）]為一個項，[（itemset）]為項集，則項的集合稱為[itemset={item_1，item_2，...，item_m}]，其中，k指項集中包含的項的數(shù)量。

2）在[（itemset）]項集中，某一個事物T被稱為該項集的一個子集，且每個事務(wù)有且只有一個標(biāo)識符Tid。因此，所有的事物T組合起來形成了事物集不，從而形成了關(guān)聯(lián)規(guī)則發(fā)現(xiàn)的事務(wù)數(shù)據(jù)庫。

3）支持度（support）：

[support（A?B）=P（A?B）]

4）置信度（confidence）：

[confidence（A?B）=P（B|A）]

[P（B|A）=support（A?B）support（A）=support（A?B）support_count（A）]

5）強關(guān)聯(lián)規(guī)則是指在被發(fā)現(xiàn)的頻繁項集所產(chǎn)生的強關(guān)聯(lián)規(guī)則。強關(guān)聯(lián)規(guī)則包含以下流程：

（1）在[itemset]項集中，產(chǎn)生[itemset]的所有非空子集s是頻繁項集;

（2）對于[itemset]的每個非空子集s，如果[support_count（l）support_count（s）≥min_conf]，則輸出[s?（l-s）]，其中[min_conf]為最小置信度閾值。

3.2 MADA算法實現(xiàn)步驟

MADA算法實現(xiàn)包含以下過程：

1）首先通過算法對所有事務(wù)進行掃描，獲得候選1項，并最終生成所有候選項集合C1。然后根據(jù)最小支持度條件，對候選項集中每個候選項項進行計數(shù)，并去除不滿足條件的項，最終生成由頻繁1構(gòu)成的頻繁項集L1;

2）基于（1）中的步驟，對L1中進行掃描獲得候選2項，并生成集合C2。同樣根據(jù)最小支持度條件，然后對C2中每個候選項進行計數(shù)，從C2中刪除不滿足的項，從而獲得頻繁2項集L2;

3）以此類推，基于以上步驟可得到，對Lk-1中進行掃描獲得候選k項。并生成Ck。然后對Ck中的每個候選項進行計數(shù)，從Ck中刪除不滿足的項，最終獲得頻繁k項集Lk。

4 總結(jié)

本文通過介紹五種數(shù)據(jù)庫多維度指標(biāo)研究相關(guān)的算法，并對這五種算法的原理、流程及適合的應(yīng)用領(lǐng)域進行了詳細說明。結(jié)合現(xiàn)行數(shù)據(jù)庫智能化運維過程中碰到的實際問題，在原先Apriori算法的基礎(chǔ)上進行了細微的調(diào)整，提出了MADA算法。該算法能夠更好地契合自身系統(tǒng)的需求，達到降低數(shù)據(jù)庫運維工作人員工作量，提高工作效率的要求。

參考文獻：

[1] 文芳，黃慧玲，李騰達，等.基于FP-growth關(guān)聯(lián)規(guī)則的圖書館數(shù)據(jù)快速挖掘算法研究[J].重慶理工大學(xué)學(xué)報（自然科學(xué)版），2020，34（6）：189-194.

[2] 沈慧娟，曹曉麗.基于頻集的Apriori關(guān)聯(lián)規(guī)則算法的應(yīng)用研究[J].物聯(lián)網(wǎng)技術(shù)，2020，10（10）：57-61.

[3] 王鳳肆.一種基于知識點邏輯關(guān)系模型的改進的Apriori算法[J].信息系統(tǒng)工程，2020（1）：47-48.

[4] 陳寅.基于FP-GROWTH算法的關(guān)聯(lián)規(guī)則挖掘算法研究[J].無線互聯(lián)科技，2017（19）：118-121，124.

[5] 翁進，陳亞凱，張禾裕.基于DLG精細化DEM的內(nèi)插算法及其精度評價[J].國土資源導(dǎo)刊，2015，12（4）：79-84.

[6] 歐陽猛.基于矩陣壓縮的FUP算法優(yōu)化研究[D].長春：東北師范大學(xué)，2019.

[7] 朱玉全，孫志揮，季小俊.基于頻繁模式樹的關(guān)聯(lián)規(guī)則增量式更新算法[J].計算機學(xué)報，2003，26（1）：91-96.

[8] 張雅琴.關(guān)聯(lián)規(guī)則挖掘算法的設(shè)計[J].山西電子技術(shù)，2005（3）：10-12.

[9] Lasmedi Afuan，Ahmad Ashari，Yohanes Suyanto. Query Expansion in Information Retrieval using Frequent Pattern （FP） Growth Algorithm for Frequent Itemset Search and Association Rules Mining[J]. International Journal of Advanced Computer Science and Applications （IJACSA），2019（10）.

【通聯(lián)編輯：光文玲】