基于關(guān)聯(lián)規(guī)則算法的檢查器組優(yōu)化建議機制

李 昕，謝穎華

(東華大學(xué) 信息科學(xué)與技術(shù)學(xué)院，上海201620)

0 引言

工業(yè)產(chǎn)品生產(chǎn)過程離不開圖紙設(shè)計，一個功能完善、細(xì)節(jié)滿分的設(shè)計平臺可以為圖紙設(shè)計的過程提供極大的便利，甚至可以簡化或加快產(chǎn)品開發(fā)過程。Siemens PLM Software公司出品的NX就是這樣一個交互式CAD/CAM(Computer Aided Design and Computer Aided Manufacturing)系統(tǒng)，它不止提供模型設(shè)計平臺，還提供功能強大全面的Check-Mate模塊用于產(chǎn)品模型的質(zhì)量檢查[1]。檢查結(jié)果將通過QDB(Quality Dashboard)得以顯示，這一套功能形成一條閉環(huán)，為產(chǎn)品設(shè)計流程提供極大的便利。

第二代QDB更名為Cloud QDB，擺脫了第一代單機版的設(shè)計，實現(xiàn)了在線網(wǎng)頁版的轉(zhuǎn)變，引用云技術(shù)實現(xiàn)設(shè)計者范圍之內(nèi)的數(shù)據(jù)共享和設(shè)計監(jiān)控，不僅滿足了自定義報告展示的需求，還提供了更加美觀的用戶交互界面，更直觀展示Check-Mate檢查報告。NX的用戶較多從事汽車行業(yè)設(shè)計，設(shè)計的模型文件十分復(fù)雜，所以Check-Mate的運行時間也隨之變長，同時在運行Check-Mate的時候系統(tǒng)資源被占用，用戶工作效率不高。

針對Check-Mate用時過長這一問題，本文設(shè)計引入檢查器組優(yōu)化建議機制，通過關(guān)聯(lián)規(guī)則挖掘算法，挖掘存在關(guān)聯(lián)的檢查器，刪除冗余檢查器，在滿足有效檢查器組覆蓋率的基礎(chǔ)上為用戶提供檢查器組優(yōu)化建議，減少檢查時間，提高用戶的工作效率，節(jié)約生產(chǎn)制造中的成本。

1 系統(tǒng)總體架構(gòu)及功能模塊

1.1 總體架構(gòu)

檢查器組優(yōu)化建議系統(tǒng)總體架構(gòu)由數(shù)據(jù)庫端、數(shù)據(jù)提取端、數(shù)據(jù)分析單元、報告及優(yōu)化建議輸出端四部分構(gòu)成。檢查器組優(yōu)化建議系統(tǒng)可以為用戶提供檢查結(jié)果報告展示；將報告保存在云端，實現(xiàn)用戶群體之間的數(shù)據(jù)共享；并提供檢查結(jié)果分析，根據(jù)關(guān)聯(lián)規(guī)則挖掘算法探索檢查器之間的關(guān)聯(lián)，為用戶提供可以節(jié)省檢查時間的檢查器組優(yōu)化建議?？傮w架構(gòu)如圖1所示。

圖1 檢查器組優(yōu)化建議系統(tǒng)總體架構(gòu)

數(shù)據(jù)庫端使用的Solr負(fù)責(zé)保存以及管理數(shù)據(jù)引擎，具有在線保存并提供搜索XML格式的檢查結(jié)果文件的功能；數(shù)據(jù)提取端提供解析服務(wù)，通過解析檢查結(jié)果文件，提取檢查器的關(guān)鍵信息，包括檢查器狀態(tài)、運行用時、歷史狀態(tài)以及檢查器與模型文件的屬性特征信息；數(shù)據(jù)分析單元提供關(guān)聯(lián)規(guī)則挖掘功能，綁定關(guān)聯(lián)規(guī)則挖掘算法，挖掘檢查器組中的關(guān)聯(lián)規(guī)則，為優(yōu)化建議提供理論依據(jù)；報告及優(yōu)化建議輸出端可以整合數(shù)據(jù)分析單元輸出的規(guī)則，與前端的部件組合生成可視化報告，提供檢查器組優(yōu)化建議，在保證檢查器組覆蓋率的同時合理建議優(yōu)化檢查器組；優(yōu)化建議和報告將通過瀏覽器在前端展示，提供可視報告，為用戶的工作提供便利。

1.2 系統(tǒng)功能模塊

檢查器組優(yōu)化建議系統(tǒng)包含5個模塊，分別是檢查結(jié)果信息獲取模塊、數(shù)據(jù)預(yù)處理模塊、特征分析模塊、優(yōu)化建議過濾模塊以及報告輸出模塊。

檢查結(jié)果信息獲取模塊主要是用于提取檢查結(jié)果中的檢查器以及模型文件的關(guān)鍵信息，包括檢查器在該模型文件的狀態(tài)、運行用時、歷史狀態(tài)、檢查器本身的設(shè)計者及功能；數(shù)據(jù)預(yù)處理模塊可以綜合檢查器和模型兩部分信息，根據(jù)二者關(guān)聯(lián)部分進行檢查器組初次過濾；特征分析模塊的功能是分析模型文件特征，決定選取哪些檢查器的關(guān)鍵信息來作為關(guān)聯(lián)規(guī)則挖掘所需的數(shù)據(jù)；優(yōu)化建議過濾模塊綁定了關(guān)聯(lián)規(guī)則算法的運算，將特征分析模塊選取的數(shù)據(jù)加以運算生成規(guī)則后，對冗余檢查器進行篩選羅列；報告輸出模塊整合數(shù)據(jù)，根據(jù)用戶自定義格式的模板生成整體報告。圖2所示為系統(tǒng)功能模塊圖。

圖2 系統(tǒng)功能模塊

2 關(guān)聯(lián)規(guī)則挖掘的應(yīng)用

2.1 關(guān)聯(lián)規(guī)則挖掘

數(shù)據(jù)挖掘技術(shù)主要是指從大量的、模糊、隨機等數(shù)據(jù)流中，通過技術(shù)手段和智能分析獲取隱藏在龐雜數(shù)據(jù)中的有用信息[2]，本質(zhì)是數(shù)據(jù)庫內(nèi)的知識發(fā)現(xiàn)。這些信息反映了在一定規(guī)模的數(shù)據(jù)集中各元素之間的有效聯(lián)系，或許它們不能在所有領(lǐng)域中通用，但一定可以效力于某一特定領(lǐng)域。

目前運用最普遍的數(shù)據(jù)挖掘技術(shù)是關(guān)聯(lián)規(guī)則，關(guān)聯(lián)規(guī)則是指從指定數(shù)據(jù)集中迅速、有效地找到各個事務(wù)項目之間存在的、隱藏的、有價值的關(guān)聯(lián)關(guān)系，從而為用戶提供有力的決策支持[3]。最初它由Agrawal等專家學(xué)者于20世紀(jì) 90年代初提出，目的是用于發(fā)現(xiàn)顧客的商品消費模式，經(jīng)過了十幾年的發(fā)展，已日益成熟和完善[4]。

在實現(xiàn)關(guān)聯(lián)規(guī)則挖掘的過程中，為了最大限度找到有用的規(guī)則，需要使用某些度量來約束，其中最常用的是支持度(Support)和置信度(Confidence)。前者表示數(shù)據(jù)庫中項集出現(xiàn)的頻率，而后者則用來度量規(guī)則的可信程度，它們分別表示發(fā)現(xiàn)規(guī)則的有用性和確定性[5]。

此外，也經(jīng)常會使用提升度(Lift)來度量相互依賴程度。

提升度有三種情況，分別是等于1、大于 1和小于1。以1為分界線，其依賴程度隨提升度值呈正相關(guān)；當(dāng)?shù)扔?時，則表明前提和結(jié)論對應(yīng)的事件相互獨立。

至今關(guān)聯(lián)規(guī)則挖掘已經(jīng)衍生出多種算法，包括Apriori、FP-growth等算法。傳統(tǒng)關(guān)聯(lián)規(guī)則挖掘包含兩部分：生成頻繁項集以及生成關(guān)聯(lián)規(guī)則。生成有效規(guī)則的前提是存在可靠的頻繁項集，所以選取合適的數(shù)據(jù)來生成頻繁項集是算法的關(guān)鍵。

2.2 算法設(shè)計

進行檢查器組優(yōu)化分析的目的是縮短Check-Mate運行用時，而運行用時與檢查器組規(guī)模息息相關(guān)，故需要在保證Check-Mate可靠運行的同時盡可能縮減檢查器組規(guī)模。

關(guān)聯(lián)規(guī)則算法中的Apriori算法是一種基于頻繁項集理論的遞歸方法[6]，通過生成候選項集和情節(jié)的向下封閉檢測兩部分來產(chǎn)生頻繁項集，從數(shù)據(jù)庫中挖掘支持度大于最小支持度閾值以及置信度大于最小置信度閾值[7]的關(guān)聯(lián)規(guī)則。另一種名為FP-growth的關(guān)聯(lián)規(guī)則算法的原理是深度優(yōu)先搜索，相比于Apriori算法，F(xiàn)P-growth算法不會產(chǎn)生候選項集，僅僅遍歷數(shù)據(jù)集兩次，就能夠完成頻繁項集的發(fā)現(xiàn)。故FP-growth算法比Apriori算法效率高[8]。

已知Apriori算法需要多次掃描數(shù)據(jù)庫，每次利用候選項集產(chǎn)生頻繁項集；而FP-growth算法則利用樹形結(jié)構(gòu)，無需產(chǎn)生候選項集而是直接得到頻繁項集，大大減少掃描數(shù)據(jù)庫的次數(shù)，從而提高了算法的效率。另一方面Apriori算法在擴展性方面又優(yōu)于FP-growth算法，兩種算法各有千秋，故本文為了實現(xiàn)檢查器組針對模型的覆蓋率與運行速度的平衡，選擇FP-growth算法和Apriori算法組合來進行規(guī)則挖掘。

2.2.1 數(shù)據(jù)預(yù)處理

數(shù)據(jù)來源于每次運行Check-Mate之后生成的檢查結(jié)果文件，將它們按批次輸入，以批次數(shù)識別。將文件通過Cloud QDB中的解析功能從XML格式解析轉(zhuǎn)化成易于閱讀的JSON格式，重點提取當(dāng)前狀態(tài)為fail的檢查器名稱，對應(yīng)檢查用時、檢查器應(yīng)用、特色功能、設(shè)計特征以及繼承關(guān)系，甚至包括設(shè)計者信息、設(shè)計時間等邊緣信息。將這些信息制作成數(shù)據(jù)集的標(biāo)簽，整合成為數(shù)據(jù)集；之后進行數(shù)據(jù)預(yù)處理，綜合模型文件結(jié)構(gòu)和檢查器功能兩方信息，對檢查器組的組建進行分析，判斷檢查器功能是否與模型文件結(jié)構(gòu)要求吻合，對不符合要求的檢查器進行初次過濾；接下來進行特征分析，分析模型文件裝配層次，根據(jù)層次分類檢查器組信息，分層運算也可以幫助并行運算，從而縮短運行用時；接下來進入關(guān)聯(lián)規(guī)則挖掘步驟，第一步是生成頻繁項集，參考Apriori和 FP-growth兩種算法的特點，這一步選擇效率較高的FP-growth算法。

2.2.2 頻繁項集挖掘

FP-growth算法首先根據(jù)批次以及分層對數(shù)據(jù)編號，根據(jù)批次及分層提取數(shù)據(jù)集中狀態(tài)為fail的檢查器組作為相應(yīng)事務(wù)組，整合成清單。接下來對每個事務(wù)進行計數(shù)，設(shè)定最小支持度，按計數(shù)結(jié)果降序排列每一個事務(wù)，將不符合支持度的事務(wù)刪除并重新整理清單。然后到了關(guān)鍵的一步：構(gòu)建FP樹。創(chuàng)建一個虛擬的根節(jié)點，加入第一個事務(wù)組，即將根節(jié)點指向事務(wù)組中第一個事務(wù)，由于此時已經(jīng)過降序排列，排序靠前的事務(wù)也相應(yīng)有較高的權(quán)重。第一個事務(wù)將指向排序第二的事務(wù)，由此類推，將事務(wù)組內(nèi)所有事務(wù)按序完成指向。根據(jù)規(guī)則加入后續(xù)的事務(wù)組，如果出現(xiàn)相同的節(jié)點則進行累加，最終得到FP樹。挖掘頻繁項集需要獲取每一個事務(wù)的條件模式基，它是集合形式，包含以所查找事務(wù)為結(jié)尾的路徑。根據(jù)條件模式基構(gòu)造條件FP樹，和被分析的事務(wù)并集得到支持度大于2的所有頻繁項集。

2.2.3 挖掘規(guī)則

頻繁項集生成后，需要使用Apriori算法進行規(guī)則挖掘，將頻繁項集根據(jù)項數(shù)進行降序排列，發(fā)現(xiàn)最大頻繁項集。Apriori算法有一條定理，即頻繁項集的子集也是頻繁項集。所以最大頻繁項集中一定包含全部的頻繁項集。通過上一步FP-growth算法已經(jīng)得到了支持度計數(shù)，計算置信度和提升度就可以立即提取規(guī)則。具體流程如圖3所示。

3 實驗分析

基于關(guān)聯(lián)規(guī)則算法的檢查器組優(yōu)化建議分析需要從大量的驗證結(jié)果文件中獲取檢查器的特征信息。常規(guī)模型文件與檢查器組如表1所示，其中Part代表模型文件，其編號表示一次工程中所涉及到的模型文件，文件大小從KB到GB不等，據(jù)模型復(fù)雜度而定；Checkers表示檢查器組，Checkers(n)表示組內(nèi)檢查器個數(shù)，模型越復(fù)雜，所需檢查器越多，同時運行Check-Mate的時間也越長。

圖3 算法流程

本文采用的共計13 599份驗證結(jié)果文件取自Siemens PLM Software公司內(nèi)部測試文件。數(shù)據(jù)集的20%作為訓(xùn)練集，80%用于測試。

表1 模型與檢查器組

本文實驗環(huán)境：設(shè)備型號：HP Z240 Tower Workstation；CPU：:Intel?CoreTMi5-6400 CPU@2.70 GHz；Windows版本：Windows 7旗艦版。

3.1 運行時間對比

設(shè)置對照試驗，首先記錄Check-Mate在無優(yōu)化建議狀態(tài)下的運行時間(bf)，獲取同一檢查結(jié)果文件數(shù)據(jù)庫在經(jīng)過檢查器組優(yōu)化系統(tǒng)后得出的規(guī)則，用戶根據(jù)規(guī)則推算出的優(yōu)化建議來刪減冗余檢查器，而后再次對同一模型文件運行Check-Mate并記錄時間(af)，觀察兩次運行時間的對比。

優(yōu)化前后Check-Mate占時對比如圖4所示，可以看出在10次實驗中，優(yōu)化后(af)對比優(yōu)化前(bf)的Check-Mate用時有了顯著的縮短。

圖4 優(yōu)化前后占用時間對比

3.2 覆蓋率

Num1為Check-Mate在無優(yōu)化建議狀態(tài)下結(jié)果為fail的檢查器個數(shù)，接下來通過檢查器組優(yōu)化建議系統(tǒng)，刪除冗余檢查器，用此時被優(yōu)化后的檢查器組運行Check-Mate，參考檢查結(jié)果，修復(fù)模型文件中存在的設(shè)計問題。下一步使用被刪除的檢查器再次對該模型文件運行Check-Mate，記錄此時狀態(tài)仍為fail的檢查器個數(shù)為Num2，即被優(yōu)化建議誤刪除的檢查器個數(shù)。

覆蓋率由式(1)確定：

完整的檢查器組由于不篩選檢查器，所以檢查器組對于模型文件的覆蓋率可以達(dá)到100%，其代價就是用時過長，所以如果縮短用時，勢必要犧牲檢查器組的覆蓋率?？紤]到工業(yè)設(shè)計中對于模型文件的質(zhì)量需求，覆蓋率應(yīng)考慮在95%以上，才能認(rèn)為是有效的優(yōu)化系統(tǒng)。

如圖5所示，檢查器組優(yōu)化建議系統(tǒng)可以在保證覆蓋率在95%的基礎(chǔ)上對用時盡可能縮短，使覆蓋率和用時處于良性平衡。該優(yōu)化系統(tǒng)覆蓋率滿足實際工程的需求，由此系統(tǒng)可靠性得到了保證，證明檢查器組優(yōu)化建議系統(tǒng)值得推廣。

圖5 優(yōu)化后檢查覆蓋率(Cv)

4 結(jié)論

本文提出的基于關(guān)聯(lián)規(guī)則挖掘算法的檢查器組優(yōu)化建議機制，在保證覆蓋率的情況下，可以為用戶提供優(yōu)化建議，用戶可根據(jù)需要刪減檢查器組，縮短Check-Mate的運行時間，提高工作效率。