陳立寧,林伯奇,魏 唯,胡曉宇

(中國電子科技集團公司第四十八研究所，湖南長沙410111)

一種用于預估MOCVD工藝結果的改進方法

陳立寧,林伯奇,魏 唯,胡曉宇

(中國電子科技集團公司第四十八研究所，湖南長沙410111)

Apriori算法是關聯規(guī)則中的一種典型算法。該算法結構簡單，以遞歸統(tǒng)計為基礎，采用逐層搜索的方式對大量數據進行提取，挖掘數據記錄之間的關聯規(guī)則。針對Apriori算法產生候選記錄集過多的問題，提出了一種改進方法減少候選記錄集的組合個數。一項MOCVD工藝包含了流量、壓力、溫度等多種實時數據，數據量龐大，根據改進方法對MOCVD工藝中所產生的實時數據以及操作記錄進行分析、挖掘出這些數據記錄之間的關聯關系；然后根據MOCVD工藝結果，判斷這些關聯關系對MOCVD工藝的影響，并作為下一次工藝數據編輯的依據。

Apriori算法；MOCVD；關聯規(guī)則；候選記錄集

隨著計算機硬件技術的提高，計算機對數據的處理能力也在日漸提升，加上當前互聯網絡的發(fā)展以及普及，數據信息量在不斷上漲，人們已經進入了一個信息爆炸的時代。人們除了利用現有的關系數據庫標準查詢語句得到一般的、直觀的信息外，很多時候因為業(yè)務的需求不得不挖掘其內含的、未知的卻又實際存在的數據關系，而這些數據關系往往是對業(yè)務存在極大價值，也是人們迫切想要知道的信息。對個人尤其是對企業(yè)而言，如何從這些海量的數據當中挖掘出潛在的、有用的信息是一個挑戰(zhàn)。數據挖掘[1]就是從大量的、不完全的、有噪聲的、模糊的、隨機的實際應用數據中，提取隱含在其中的、人們事先不知道的、但又非常有價值的信息的過程。

一項MOCVD工藝包含了時間、氣體流量、氣體壓力、真空、溫度、轉速、開關量等多種實時數據。一個典型的工藝一般要進行數個小時，從工藝開始到結束，會產生大量的實時數據以及操作記錄。因此，一項工藝運行當中的操作記錄，即使在工藝運行過程當中沒有出現意外或者報警，在一定程度上也存在參考價值。所以從這些實時現場記錄當中，挖掘出其中潛在的關聯關系也對下次工藝運行具有一定參考意義。

1 算法相關知識

1.1 Apriori算法思想與原理

Apriori算法采用一種逐層搜索的迭代方法，k項集用于搜索（k+1）項集，來窮盡數據集中的所有頻繁項集。算法的主要步驟如下：(用Lk表示k項頻繁集，Ck表示k項候選集)

1.1.1 連接步

先找到頻繁1項集L1，然后將L1和自身連接產二維候選項集C2，以此類推，通過將Lk-1進行自身連接產生候選k項集，即Ck。

1.1.2 剪枝步

Ck是Lk的超集，Ck的成員既包含頻繁項也含有非頻繁項，但所有頻繁k項集一定都包含在Ck中。對數據庫進行掃描，確定Ck中每個候選的計數，從而確定Lk。但是，Ck可能很大，這樣所涉及的計算量很大。因此，利用任何非頻繁的（k-1）項集都不是頻繁k項集的子集這一性質來壓縮Ck[7,8]。若候選k項集的（k-1）項子集不在Lk-1中，則該候選項也不可能是頻繁的，可以從Ck中刪除。

1.2 關聯規(guī)則和置信度

關聯規(guī)則和置信度的定義為：令U={I1，I2，I3，...，In-1，In}，S(U)表示U的支持度，a是U的一個子集，S(a)表示a的支持度。如果S(U)/S(a)≥最小置信度，那么就存在如下關聯規(guī)則a->Cs(a)，其中Cs(a)為a在U中的補集。S(U)/S(a)的值就是該條規(guī)則的置信度。例如，假設U={I1，I3，I4，I6}，a= {I4，I6}，那么Cs(a)={I1，I3}。

1.3 Apriori算法的缺陷

Apriori算法的基本思路：

第一步：簡單統(tǒng)計所有含有一個元素的項目出現頻率，并找出那些大于或等于最小支持度的項目集，產生一維頻繁項目集。

第二步：循環(huán)處理直到未能再產生維數更高的頻繁項目集。循環(huán)過程是在第k步中，根據k-1步生成的k-1維頻繁項集來生成k維候選項目集。

可以看出Apriori算法有以下缺陷：

（1）在每一步產生候選項目集時循環(huán)產生的組合過多，沒有排除不應該參與組合的元素；

（2）每次計算項集的支持度時，都對數據庫中的全部記錄進行了一遍掃描比較，如果數據庫中擁有上萬條甚至幾十萬條或更多條記錄，這種掃描比較將大大增加計算機系統(tǒng)的I/O開銷，這種開銷隨著數據庫記錄的增加呈幾何級數增長。

2 改進算法的設計思想

2.1 動態(tài)項集計數

本算法改進的核心思想是：生成k維頻繁項集Lk后，在參與生成下一維候選項集前先對Lk中的一維元素進行計數。若它的計數小于k-1的話，說明該元素不是組成Lk+1項目集的元素。因為對一個一維元素而言，要成為k維項目集中的元素的話，該元素在k-1階頻繁項目集中的計數必須大于或等于k-1個，否則不可能生成k維項目集。

2.2 算法的實施過程

本文針對Apriori算法不足之處，通過候選項集計數的方法，統(tǒng)計當前頻繁項集中一維元素個數，將不是組成下一維項目集的元素刪除，減少項目集的個數。改進算法流程如下：

步驟1：統(tǒng)計所有一維元素出現的次數，保留次數不小于最小支持度的一維元素，生成一維頻繁項集L1。

步驟2：通過合并L1中所有一維頻繁項，生成二維候選項集，以此類推。通過第(k-1)維頻繁項集Lk-1，合并生成k維候選項集Ck。因為最大項目集的子集必為最大項目集。所以在計算Ck中元素支持度時，先刪除Ck中所有(k-1)維子集不在Lk-1中的項目集。

步驟3：掃描原始數據庫，計算Ck中每個元素在原始數據庫中的支持度。然后將統(tǒng)計后的支持度同最小支持度比較，刪除那些支持度小于最小支持度的項目，生成k維頻繁項集Lk。

步驟4：統(tǒng)計Lk中每個一維元素的個數，若它的計數小于k的話，說明該元素不是組成Lk+1項目集的元素。因為對一個一維元素而言，要成為k維項目集中的元素的話，該元素在k-1階頻繁項目集中的計數必須大于或等于k-1個，否則不可能生成k維項目集。

步驟5：重復步驟2至步驟4的內容，直到不能再生成下一維項目集。

2.3 改進算法偽代碼

改進算法生成頻繁項集的偽代碼如下：

2.4 實例說明

表1表示MOCVD工藝中操作記錄所對應的編號，即，I1={第2步，步時間：32->64}。

原始數據庫中每條記錄中的操作事件是由逗號隔開的，以此為分隔點掃描每條記錄中的操作事件，例如:掃描到I1后比較之前掃描到的事件有沒有與I1相同的，如果沒有就將I1作為一個單獨元素對其計數為1；如果相同，就將掃描到I1的計數加1，以此類推，直到掃描完所有的記錄中的操作事件就得到了一維候選項集C1，然后將每個元素的支持度（即每個元素出現的次數）與最小支持度比較，得到L1，按照圖1說明的過程推導出最大頻繁項集。

圖1 最大頻繁項集挖掘過程

圖1中所示的最大頻繁項集推導過程說明如下：

(1)統(tǒng)計原始數據庫中各MOCVD工藝操作事件出現的次數，保留出現次數不小于最小支持度S的操作事件，并記為一維元素，用該一維元素生成一維元素集L1；其中，最小支持度S為3；

(2)將L1中元素兩兩合并，生成二維候選項目集C2；

(3)計算C2中2維元素在原始數據庫中的支持度，刪除C2中支持度小于最小支持度的二維元素，生成二維頻繁項集L2；

(4)統(tǒng)計L2中一維元素的頻度，刪除包含頻度小于2的一維元素的二維元素，并用剩余的二維元素組成新的頻繁項集L2；

(5)將新L2中的二維元素項目兩兩合并，生成三維候選項目集C3；

(6)計算C3中的三維元素在原始數據庫中的支持度，刪除支持度小于最小支持度的三維元素，生成頻繁項集L3；

(7)統(tǒng)計L3中一維元素的頻度，刪除L3中包含頻度小于3的一維元素的三維元素，生成新的三維頻繁項集L3；

(8)將新L3中的三維元素兩兩合并，生成四維候選項目集C4，由于不能再繼續(xù)生成下一維候選項集，且C4中元素的支持度大于最小支持度，故C4為L4，即本實施例的最大頻繁項集。

由關聯規(guī)則的定義，根據最大頻繁項集，可得到如下關聯規(guī)則：

(1)I6->I1I3I4置信度：S(I1I3I4I6)/S(I6)=3/4=75%

(2)I1I3->I4I6置信度：S(I1I3I4I6)/S(I1I3)=3/4=75%

(3)I1I4->I3I6置信度：S(I1I3I4I6)/S(I1I4)=3/3=100%

(4)I1I6->I3I4置信度：S(I1I3I4I6)/S(I1I6)=3/3=100%

(5)I3I6->I1I4置信度：S(I1I3I4I6)/S(I3I6)=3/3=100%

(6)I4I6->I1I3置信度：S(I1I3I4I6)/S(I4I6)=3/3=100%

(7)I1I3I4->I6置信度：S(I1I3I4I6)/S(I1I3I4)=3/3=100%

(8)I1I4I6->I3置信度：S(I1I3I4I6)/S(I1I4I6)=3/3=100%

(9)I1I3I6->I4置信度：S(I1I3I4I6)/S(I1I3I6)=3/3=100%

(10)I3I4I6->I1置信度：S(I1I3I4I6)/S(I3I4I6)=3/3=100%

上述規(guī)則中，置信度達到100%的，說明工藝人員進行了某些操作后，必定會進行其他的操作，例如：第8條規(guī)則中，工藝人員進行了I1I4I6三步操作后，必定會進行I3操作，由于工藝運行中每一步操作都可能對工藝結果造成不同程度的影響，所以從上述規(guī)則當中可以認為，置信度達到100%的工藝操作對工藝結果有直接的影響，根據工藝結果的好壞，可以從這些推導出的規(guī)則當中總結出：下次工藝時，這樣一系列操作是可行的還是需要改進的。

3 實驗結果及分析

MOCVD工藝數據一般為以下幾種類型：質量流量計數據包括H2、N2、NH3三種載氣流量，SiH4(硅烷)流量以及MO源(三甲基鋁、三甲基鎵、三乙基鎵、二茂鎂、三甲基銦)的流量；壓力控制器數據包括反應室壓力、三種載氣壓力和MO源壓力；石墨盤的溫度和轉速。工藝操作主要就是對上述對象進行設置、更改。而工藝中所有實時數據以及操作記錄都是存儲在數據物理表中。

改進算法就是以日志表中的操作事件為對象，對每條操作事件進行編號，然后按兩兩組合的方式合并每條記錄，生成高維的數據記錄集，然后統(tǒng)計這些數據記錄集個數，挖掘出最大頻繁項集。記錄集的維數就是集合中每個元素包含的操作事件的個數，其中元素相當于前面的操作事件的內容，是一個字符串數據。

本次實驗采用C++程序編寫，針對數據庫這些操作記錄進行合并刪除，推導出這些記錄之間的關聯規(guī)則。算法實驗環(huán)境為：CPU:Intel Core Duo T2050@801 MHz/1.60 GHz，內存信息：PC2-5300 DDR2666 MHz雙通道1 G，開發(fā)環(huán)境：VC++.net。實驗數據：MOCVD3個月的工藝數據，操作記錄約為27 000條。

該算法試驗中，在選擇不同最小支持度閾值的情況下，測試了改進算法和傳統(tǒng)算法在挖掘所有頻繁項集所用的時間試驗數據如下表2所示。

表2 不同最小支持度下算法挖掘所有頻繁項集所用時間

根據表2的實驗結果將兩算法所用的時間繪制成圖，如圖2所示。

圖2 改進算法和傳統(tǒng)算法挖掘所有頻繁項集所用時間

實驗結果顯示，本文所提出的改進算法比傳統(tǒng)算法在時間上大約優(yōu)化了10%～20%。因為Apriori算法是利用頻繁項集Lk-1項兩兩相結合產生候選項集Ck，k越大所產生的候選項集的數目就越多，呈指數級增長；其次就是在剪枝步以及計算支持度時需要遍歷一次數據庫。改進算法生成k維頻繁項集后，在兩兩結合生成k+1維候選項集前，先計算一維元素的頻度，刪除了不可能構成k+1維候選項集的元素組合，這樣在連接步時就大大減少了候選項集的數目，提高了算法效率。但由于在生成候選項集以及計算支持度時仍然要掃描數據庫，因此改進算法在效率上還有更多可優(yōu)化的空間。

4 結 論

本文針對Apriori算法效率上的不足，在其基礎上提出了一種改進方法。改進的思想主要是在頻繁項集兩兩結合生成下一維候選項集時，先掃描頻繁項集中一維元素的個數，如果一維元素個數小于當前頻繁項集的維數，則將包含有該一維元素的元素組合從當前頻繁項集中刪除，這樣就能減少下一維候選項集的個數，因為候選集候選項集元素多是影響算法效率的瓶頸，因此改進算法在時間開銷上要優(yōu)于傳統(tǒng)算法。但是改進算法在生成候選項集和計算支持度時仍然要掃描數據庫，因此如何采用更好的數據結構或方法，進一步減少數據庫的掃描次數，是下一步的研究重點。

[1] 李先通，李建中，高宏.一種高效頻繁子圖挖掘算法[J].軟件學報，2007，18(10)：2469-2472.

[2] 王映龍，楊珺，周法國，等.加權最大頻繁子圖挖掘算法的研究[J].計算機工程與應用，2009，45(20)：31-34.

[3] 吳甲，陳峻.一種快速的頻繁子圖挖掘算法[J].計算機應用，2008，28(10)：2533-2534.

[4] 謝均，尚學群，王淼，等.解決數據樣本不平衡性的頻繁子圖挖掘算法[J].計算機工程與應用，2008，44(36)：146-147.

[5] InokuchiA，WashioT，MotodaH.Complete mining of frequent patterns from graphs：Mining graph data[J].Machine Learning，2003，50(3)：324-340.

[6] 王艷輝，吳斌，王柏.頻繁子圖挖掘算法綜述[J].計算機科學，2005，32(10)：193-194.

[7] 白似雪，朱濤，梅君.基于圖的Apriori改進算法[J].南昌大學學報，2009，31(1)：36-37.

[8] 黃建明，趙文靜，王星星.基于十字鏈表的Apriori改進算法[J].計算機工程，2009，35(2)：37-38.

[9] 嚴蔚敏，吳偉民，著.數據結構[M].北京：清華大學出版社，1996.7：161-166.

Improved Method for Estimating Recipe Results of MOCVD

CHEN Lining,LIN Boqi,WEI Wei,HU Xiaoyu

(The 48th Research Institute of CETC,Changsha 410111，China)

Apriori algorithm is one of the classical algorithms about association rules,which is based on recursion and very simple.This method extracts data by layer-by-layer search and deduces the association rule.An improved method is mentioned to reduce the amount of candidate recordsets in connection with lots of candidate record sets generated by Apriori algorithm.So much real time data like flow,pressure,temperature and so on is available in a MOCVD recipe.The rcipe data is analyzed in a MOCVD recipe with this improved method and the association rule is deduced in this dissertation. This association rule deduced by this method can be used to evaluate a MOCVD recipe and become reference for the next recipe.

Apriori algorithm；MOCVD；Association rule；Candidate record set

TN304.05

：A

：1004-4507(2015)08-0010-06

陳立寧（1984-），男，碩士，主要研究方向為數據庫技術、數據挖掘。

2015-06-25