筆記本電腦ＢＴＯ生產計劃中關聯規則挖掘的應用研究

[摘要] 本文將數據挖掘技術中的關聯規則算法運用于筆記本電腦BTO生產計劃中，并基于BTO制造的特點，采用了分類、多最小支持度和增量挖掘的改進算法，挖掘PC配置選擇的關聯關系，為制造部門制定準確的生產計劃提供科學的支持。

[關鍵詞] 關聯規則 多最小支持度 按訂單制造 生產計劃 筆記本電腦

一、應用背景

近年來筆記本電腦市場發展迅速，預計2007年全球產量將突破9000萬臺。為了在滿足市場多樣化需求的同時又能降低生產成本、提高響應速度，許多企業都在實施一種以銷訂產、按訂單生產（Build to Order， BTO）的模式。BTO模式的成功運行強烈地依賴于原材料供應商、制造企業和銷售公司之間的協作關系。然而筆記本電腦制造企業所面對的原材料供應商大多為壟斷企業，它們為了自身利益要求按照企業給出的采購預測供貨，這樣制造企業如何制定一個盡可能準確反映用戶個性化需求的生產計劃變得尤為重要。但是通常這樣的生產計劃在現實中僅僅是少數人員根據經驗制定，缺乏科學性和準確性。隨著數據挖掘技術的不斷成熟，在商業領域有著巨大的發展潛力。本文運用其中的關聯規則經典算法并結合BTO制造的特點加以改進，挖掘出歷史數據庫中筆記本電腦配置關聯關系，為生產計劃提供科學的支持。

二、關聯規則基本概念和描述

關聯規則挖掘是目前數據挖掘領域最活躍的分支之一。一條關聯規則是形如 XY 的蘊涵式，其中XY的支持度是事務集中包含X和Y的事務數與所有事務數之比，即Support(XY) =P(XY)；它的置信度則是事務集中包含X和Y的事務數與包含X的事務數之比，即Confidence((XY))= P(XY)/P(X);若支持度和置信度分別大于用戶定義的最小支持度和最小置信度，則XY為強關聯規則。實現關聯規則挖掘的算法很多，以下以Apriori算法來描述：

三、關聯規則應用改進

BTO制造的特殊性和難點在于無法預測到用戶的具體需求，業界普遍采用的一種方案是為各機型建立一份備選組件清單，生產計劃將轉化為對各個組件需求數量的預測。通常，一臺筆記本電腦包含了外框體以及若干自選組件，如CPU，RAM，HDD等。與傳統的貨籃分析相比，BTO筆記本電腦配置信息挖掘又有它不同的特點：

1.耦合性

BTO筆記本電腦的訂單從內容上看更像是一份電腦組件選購清單，對于大多數組件，不可以重復選擇其同類的其他組件。因此，對關聯規則算法做如下改進：由頻繁K-項集生成侯選K+1項集時，直接忽略同類組件間的關聯。對組件進行分類，將所有項目集合I分解為n類: 且有其中表示第n類下的第m種組件。在Apriori_Cgen(Lk)過程中增加限制條件，改進為：

，且有

2.多樣差異性

電腦組件的可替換性、供應商情況和庫存成本等因素決定了它們的重要程度各不相同。然而傳統關聯規則算法僅使用單一的最小支持度，對不同組件重要程度沒有區分。因此，采用多支持度關聯規則挖掘方法對Apriori算法進行改進。定義各部品的最小支持度為min_sup(in)，將候選k-項集中的某一候選項的最小支持度定義為：min_sup(c)= MIN(min_sup(i1)， min_sup(i2) ，...， min_sup(ik)，其中c={i1， i2， …， ik})。Apriori算法的實現基于以下前提：頻繁項的任意子集必是頻繁項。但是多支持度關聯規則挖掘算法無法滿足這一前提。為此，特別規定在1-項頻繁項的挖掘過程中對所有的候選項采用所有項支持度的最小值，此后多項頻繁項挖掘再采用多支持度的方法，保證算法能夠繼續適用。

3.動態性

企業信息系統每天都在不停地接收來自全球各地的訂單，因此采用一種動態更新的關聯規則挖掘算法，當數據更新時充分利用原有數據關聯規則信息，僅對新增數據進行挖掘，得到新的關聯規則結果。本應用將在數據庫中記錄所有候選項的支持度，無論其最終是否成為頻繁項，這樣不必重復先前的工作。假設DB為原有的訂單記錄，db為新增記錄。若c在DBdb上頻繁，則c至少在DB和db中的一個上頻繁。基于以上性質，在db增量數據挖掘時采取以下策略：若c在DBdb上同為頻繁項或非頻繁項，那么直接定義c在DB和db上頻繁或非頻繁；若c僅在DB和db中的一個上頻繁，則重新計算其支持度進行判定。為此對Apriori_Lgen(Ck)作了補充，比較原有關聯規則信息:(1)對增量挖掘中新出現或者丟失的頻繁項重新計算其支持度判定頻繁屬性;(2)對在DB和db中都頻繁的項繼續判定為頻繁項。

四、應用實例

我們選取了某筆記本制造企業的一種機型為研究對象，將其組件分為16大類120多項，以下將對其中5類部件關聯規則加以跟蹤和描述:(1)根據用戶提供的包括庫存成本，供應商情況等信息對各類電腦組件設定不同的最小支持度（百分比形式），具體為CPU：2%、RAM：10%、LCD：10%、ODD：15%、HDD：8%。 (2)將所有的組件作為候選1-項頻繁集，掃描數據庫，得到各項支持度如表1所示。根據3.2的改進，此處最小支持度閾值統一采用2%，因此YCPUT135等3項（刪除線）被定為非頻繁項，而YRAM1520D等8項（帶*項）雖然支持度小于本類組件設定的最小支持度，但仍然入選1-項頻繁項集。(3)由性質4.1，直接忽略同類組件之間的關聯，比如排除{YCPUT225，YCPUT23D}成為2-項候選項，可以減少158次計算。生成2-項頻繁項時，采用新的最小支持度計算方法。以{YCPUT23E，YHDDS087}為例該項的最小支持度為2%，計算得到支持度為3.87%，因此入選頻繁項集。(4)用同樣的方法，得到k-項頻繁項集，結果如表2所示:注意頻繁2-項集中的{YCPUT23D，YHDDS065}，正是由于在1-項頻繁項挖掘過程中采用了2%作為支持度閾值使YHDDS065能夠入選，否則該2-項頻繁項將被丟失。(5)前幾步針對該機種某月前2周的3450個訂單數據生成了關聯規則，在第3周又發生了1473筆新的訂單，因此需要更新關聯規則信息。在新增數據中發現了新的9組頻繁項，如：{YCPUT76D，YRAM162GD}，而原關聯規則信息中的16組頻繁項在新增數據中為非頻繁項，如：{YCPUT23D，YHDDS065}，因此基于上一次挖掘結果重新計算支持度。以上述兩項為例，原記錄中SUPDB({YCPUT76D，YRAM162GD})=1.72%新增記錄中的支持度為SUPDB({YCPUT76D，YRAM162GD})=4.72%，計算得到新的支持度為SUPDBdb({YCPUT76D， YRAM162GD})=，所以該項成為頻繁項，而SUPDBdb({YCPUT23D，YHDDS065})=1.86%，因此從頻繁項集中排除。

通過對訂單數據關聯規則的挖掘，使用戶在制定生產計劃時能夠充分考慮到這些組件之間的相關性，從一定程度上改變了以往對單個組件孤立地進行預估的狀況，使得對各組件產量的計劃能夠有比較科學的比例關系，更能準確地反映出用戶偏好的變化規律，計劃更加準確。

參考文獻:

[1]2006～2007年中國筆記本電腦產業研究報告[R/OL]. http://www.ccidnet.com/

[2]宮雨:分組多支持度關聯規則研究[J].計算機工程與設計，2007，(05):1205～1207

[3]Cheung D W:Maintenance of discovered association rules in large databases: An incremental updating technique [C]. Proceedings of the 12th International Conference on Data Engineering，1996:106～114

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。