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

李 昕，謝穎華

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

0 引言

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

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

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

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

1.1 總體架構

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

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

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

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

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

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

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

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

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

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

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

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

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

提升度有三種情況，分別是等于1、大于 1和小于1。以1為分界線，其依賴程度隨提升度值呈正相關；當等于1時，則表明前提和結論對應的事件相互獨立。

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

2.2 算法設計

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

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

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

2.2.1 數據預處理

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

2.2.2 頻繁項集挖掘

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

2.2.3 挖掘規(guī)則

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

3 實驗分析

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

圖3 算法流程

本文采用的共計13 599份驗證結果文件取自Siemens PLM Software公司內部測試文件。數據集的20%作為訓練集，80%用于測試。

表1 模型與檢查器組

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

3.1 運行時間對比

設置對照試驗，首先記錄Check-Mate在無優(yōu)化建議狀態(tài)下的運行時間(bf)，獲取同一檢查結果文件數據庫在經過檢查器組優(yōu)化系統(tǒng)后得出的規(guī)則，用戶根據規(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)下結果為fail的檢查器個數，接下來通過檢查器組優(yōu)化建議系統(tǒng)，刪除冗余檢查器，用此時被優(yōu)化后的檢查器組運行Check-Mate，參考檢查結果，修復模型文件中存在的設計問題。下一步使用被刪除的檢查器再次對該模型文件運行Check-Mate，記錄此時狀態(tài)仍為fail的檢查器個數為Num2，即被優(yōu)化建議誤刪除的檢查器個數。

覆蓋率由式(1)確定：

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

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

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

4 結論

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