李馥林,孟 晨,王 成,范書義

( 陸軍工程大學石家莊校區(qū) 導彈工程系,石家莊 050003)

0 引言

隨著大數(shù)據(jù)技術的廣泛應用和相關技術的不斷成熟,人們利用數(shù)據(jù)資源的能力得到了較大提升。在數(shù)據(jù)巨量增加、數(shù)據(jù)種類繁多和數(shù)據(jù)格式迥異的情況下,如何從海量數(shù)據(jù)中獲取有價值的信息,成為了大數(shù)據(jù)運用的核心問題。作為一種對數(shù)據(jù)高效處理和全面利用的技術,數(shù)據(jù)挖掘技術是應對上述挑戰(zhàn)的有效手段之一,已經(jīng)在許多領域得到了應用[1-3]。數(shù)據(jù)挖掘就是從大量數(shù)據(jù)中獲取有用信息的過程,為了從數(shù)據(jù)中獲取滿足人們實際需求的知識,就要求所獲得的數(shù)據(jù)具有較強的可用性[4-5]。但事實上,即使原始數(shù)據(jù)可靠性足夠高,能準確反映裝備的實際情況,從中挖掘信息的過程可能依然存在困難,數(shù)據(jù)類型的影響同樣不可忽視。針對數(shù)據(jù)挖掘技術用于裝備質(zhì)量信息分析時,可能面臨部分數(shù)據(jù)類型不適應數(shù)據(jù)挖掘方法的問題,本文中提出一種裝備質(zhì)量數(shù)據(jù)離散化方法。

運用數(shù)據(jù)挖掘方法能夠從海量數(shù)據(jù)中找出隱含的規(guī)律和有價值的信息,然而許多數(shù)據(jù)挖掘算法并不適用于連續(xù)型數(shù)據(jù),因此數(shù)據(jù)離散化是實施數(shù)據(jù)挖掘之前不可或缺的預處理環(huán)節(jié)。數(shù)據(jù)離散化是通過在連續(xù)屬性的數(shù)據(jù)中插入斷點,將其轉化為若干個數(shù)值區(qū)間的過程[6-7]。將連續(xù)型數(shù)據(jù)轉化為離散數(shù)據(jù),能夠使數(shù)據(jù)挖掘算法順利運行。連續(xù)數(shù)據(jù)通常具有較高的數(shù)據(jù)精度與數(shù)據(jù)量,對其進行離散化可減輕機器的壓力,而且離散數(shù)據(jù)更容易被計算機識別,能使數(shù)據(jù)挖掘效率得到提升。

在機器學習、模式識別、數(shù)據(jù)挖掘等領域,研究人員已經(jīng)提出了許多數(shù)據(jù)離散化方法[8-11]。離散化算法可大致劃分為以下幾類:① 按照屬性空間利用情況可分為局部離散化算法和整體離散化算法;② 按照離散化方向可分為自底向上的方法與自頂向下的方法;③ 按照處理時是否參考類別屬性可分為有監(jiān)督離散化算法和無監(jiān)督離散化算法;④ 按照是否考慮屬性聯(lián)系可分為基于單屬性的離散化方法和基于多屬性的離散化方法;⑤ 按照是否同步進行離散化與決策樹生成可分為靜態(tài)離散化算法和動態(tài)離散化算法。

類別屬性最大相互依賴算法是一種基于單屬性的自頂向下的有監(jiān)督靜態(tài)離散化算法,適用于規(guī)則提取等方法的數(shù)據(jù)預處理。但是該算法仍存在信息易缺失和易過度離散化的問題,將對其基本原理進行介紹,在經(jīng)典算法的基礎上進一步提出改進算法,并通過實驗檢驗其性能。

1 類別屬性最大相互依賴的離散化算法

類別屬性最大相互依賴(class-attribute interdependency maximization,CAIM)算法是Kurgan等人提出的一種受監(jiān)督的離散化算法,簡稱CAIM算法[12]。該算法的目的是使數(shù)據(jù)對象所屬類別與其屬性值之間的依賴性最大化,并盡可能少地生成離散區(qū)間,下面對其進行簡要介紹。

1.1 類別屬性最大相互依賴準則

類別屬性最大相互依賴準則是CAIM算法選取離散斷點依據(jù)。假設存在一個包含N個對象和m個連續(xù)屬性的數(shù)據(jù)集,其所有對象分別屬于T個類別。對于其中任一連續(xù)屬性Fi,存在一種離散化方案,將Fi的屬性值劃分成n個離散的數(shù)值區(qū)間,有:

D={[d0,d1],[d1,d2],…,[dn-1,dn]}

(1)

式(1)中:d0是屬性Fi的最小值;dn是屬性Fi最大值。

在這種框架下,類別C和屬性Fi的離散區(qū)間構成了一個二維量子矩陣,如表1所示。

表1 二維量子矩陣

對于i=1,2,…,T和r=1,2,…,n,qir表示屬于區(qū)間[dr-1,dr]內(nèi)的第i類的連續(xù)數(shù)值的總數(shù),Mi+表示屬于第i類的對象總數(shù),M+r表示區(qū)間[dr-1,dr]內(nèi)屬性Fi的連續(xù)數(shù)值的總數(shù)。

類別屬性最大相互依賴準則定義了類別C和屬性Fi的離散化方案D之間的依賴性,計算公式為

(2)

式(2)中:n是區(qū)間數(shù),用r來迭代所有區(qū)間;R是所有qir中的最大值,即量子矩陣第r列中的最大數(shù)值;M+r是區(qū)間[dr-1,dr]內(nèi)屬性Fi的連續(xù)數(shù)值的總數(shù)。R對應的類別是區(qū)間[dr-1,dr]中的主導類,主導類中的元素越多,CAIM值越大,類別與屬性之間的關聯(lián)程度也越大,斷點的選擇越合理。

1.2 CAIM算法

CAIM算法的目的是將連續(xù)的屬性值劃分成若干個離散的區(qū)間,然后依次實現(xiàn)對每一個連續(xù)屬性的離散化,其核心環(huán)節(jié)是求取用于劃分區(qū)間的斷點集合。首先定義GlobalCAIM值,將其初始化為0。定義離散斷點集合D并分配適當?shù)拇鎯臻g,計算當前屬性所有相鄰數(shù)值的平均值,作為暫時的離散斷點,然后求出這些斷點的CAIM值并升序排列,再逐一與GlobalCAIM比較。若某個斷點的CAIM值大于GlobalCAIM,則將該點存入斷點集合D,同時將GlobalCAIM的值更新為該點的CAIM值,然后比較GlobalCAIM與下一個斷點的CAIM值,重復上述步驟直到完成對所有斷點的比較。在此過程中,當離散斷點集合D中的元素數(shù)量超過類別數(shù)量時,結束對該屬性的離散化。用相同的方法對下一個屬性再進行離散化,直到所有的連續(xù)屬性均完成離散化。

算法主要步驟如下。

Input:包含T類M個對象的數(shù)據(jù)決策表;

對于每個連續(xù)屬性Fi均執(zhí)行以下步驟:

Step1 找到當前屬性所有數(shù)值的最大值dn和最小值d0;

Step2 對Fi的所有數(shù)值升序排序,用最大值dn、最小值d0和集合中所有相鄰數(shù)對的平均值初始化分界點集合B;

Step3 將初始離散化方案設置為D:{[d0,dn]},定義變量GlobalCAIM,將其初始化為0;

Step4 初始化k為1;

Step5 暫時從集合B中添加一個不在D中的內(nèi)邊界,并計算相應的CAIM值;

Step6 在所有嘗試性的添加完成后,采用CAIM值最高的方案;

Step7 若CAIM>GlobalCAIM或者k

Step8 令k=k+1并前往Step5;

Output:離散化方案D。

在理想情況下,執(zhí)行以上算法步驟能夠得到k-1個斷點和k個離散區(qū)間,其中任意一個區(qū)間中的元素均屬于同一種類別,CAIM達到最大值:CAIM=M/k,此時已選定的k-1個斷點為最佳離散斷點。但是在實際應用中,CAIM值會隨著離散斷點數(shù)量的增加而增加,通常在達到局部最大化之后會開始減小。CAIM算法主要有2個缺陷:一是僅考慮區(qū)間中主導類與屬性之間的依賴性,容易導致信息缺失,降低數(shù)據(jù)離散化的質(zhì)量;二是最終形成的離散化方案所劃分的區(qū)間數(shù)通常與類別數(shù)量很接近,容易使離散化過度,影響結果的準確度。

2 基于改進CAIM算法的數(shù)據(jù)離散化方法

針對CAIM算法在應用中存在的不足,提出一種改進的離散化算法用于數(shù)據(jù)預處理。為解決CAIM算法信息缺失過多的問題,采用統(tǒng)一的標準衡量數(shù)據(jù)中各屬性的重要程度,由屬性的重要性決定對其進行離散化的順序。為解決CAIM算法容易離散化過度的問題,根據(jù)粗糙集理論[13],引入屬性分辨率控制離散化過程。

2.1 粗糙集理論

假設存在一個信息系統(tǒng)I=(U,A,V,F),其中U={x1,x2,…,xm}為論域,A為所有屬性的集合,V為屬性所有取值的集合,F為U×A→V的映射。設C為條件屬性集合,D為決策屬性集合,如果A=C∪D且C∩D=?,則將該系統(tǒng)稱為決策表。

定義1：設x,y∈U,對P?A,θP是U上的一個等價關系,若滿足xθPy?(?p∈P)(fp(x)=fp(y)),則θP稱為x和y的一個不可分辨關系。

定義2：U為論域,P和Q為U上的等價關系簇,Q的P正域記為POSP(Q),定義為:

(3)

定義3：設P?C,P將對象劃分為n個類別{Y1,Y2,…,Yn},其近似精度為:

(4)

式(4)中,card表示集合的基數(shù)。近似精度γP描述了論域U的知識完備程度,反映了對決策表分類的合理性。

定義4：對于決策表I=(U,A,V,F)和條件屬性集合C的子集B,反映任意條件屬性a∈C相對于條件屬性集合B對決策屬性集合D依賴程度的屬性重要度定義為:

sgf(a,B,D)=γB+{a}-γB

(5)

2.2 屬性分辨率

粗糙集理論認為知識就是區(qū)分事物的能力。對于論域U,如果所有對象都能被劃入同一個等價類,那么該論域包含的知識是最少的;如果其中任意2個對象都能被區(qū)分開,那么該論域包含的知識是最多的。本節(jié)基于知識量的含義,引入屬性分辨率概念。CAIM算法實施區(qū)間劃分所依據(jù)的標準相當于粗糙集理論中的近似精度,本文中提出的改進算法在經(jīng)典算法理念的基礎上,增加了屬性分辨率的控制作用,從而限制過度的離散化。屬性分辨率推導過程如下。

若論域U中含有M個對象,其中任意2個對象都能被區(qū)分,則其近似精度為1,此時該論域中的可分辨對個數(shù)為:

(6)

這是理論上能達到的最大值。將可分辨對最大個數(shù)乘以K(1,1)即最大知識量,K(1,1)為常數(shù),本節(jié)取值為2。

若論域U中含有M個對象,某屬性將其劃分為n個等價類,各個類別包含的對象數(shù)分別為m1,m2,…,mn,則該屬性具有的知識量為:

(7)

屬性分辨率是信息系統(tǒng)中某屬性具有的知識量在整個信息系統(tǒng)最大知識量中占有的比例。計算方法為:

(8)

2.3 屬性重要性評價方法

屬性重要度對分類具有重要影響,但是CAIM算法的離散化過程是按照數(shù)據(jù)集中各屬性的自然順序進行的,未考慮屬性重要程度的影響。本文中提出的改進算法是根據(jù)類別屬性依賴冗余準則與類別屬性依賴不確定性準則評價各屬性的重要性并重新進行排序[14-15],通過更合理的離散化順序減少信息損失。

由表1量子矩陣可知,屬性F的值在區(qū)間[dr-1,dr]內(nèi)并且屬于類別Ci的聯(lián)合估計概率為:

(9)

屬性F的值屬于類別Ci的邊際估計概率pi+,以及屬性F的值在區(qū)間[dr-1,dr]內(nèi)的邊際估計概率p+r分別為:

(10)

(11)

類別C和屬性F的離散化方案D之間的類別屬性交互信息定義為:

(12)

類別屬性信息和香農(nóng)熵分別定義為:

(13)

(14)

由式(12)、式(13)和式(14)得到類別屬性依賴冗余度CAIR與類別屬性依賴不確定度CAIU為:

(15)

(16)

類別屬性依賴冗余度標準反映類別和離散屬性之間的相互依賴性,CAIR值越大,類別與離散區(qū)間的相關性越好,與類的數(shù)量和連續(xù)屬性取值的數(shù)量均無關。對類別屬性依賴不確定性標準同樣適用,但關系是相反的,即CAIU值越大,類別與離散區(qū)間的相關性越差。將2種指標結合得到屬性重要性評價標準S為

S=CAIR·(1-CAIU)

(17)

式(17)中:S的值越大,表明對應的屬性越重要,對其進行離散化的程度應相對小些。

2.4 算法步驟

算法步驟如下。

Input:包含T類M個對象的數(shù)據(jù)決策表;

Step1 根據(jù)式(17)計算每個連續(xù)屬性Fi的屬性重要度S;

Step2 按照S的值將表中所有連續(xù)屬性從小到大重新排序;

對于每個連續(xù)屬性Fi均執(zhí)行以下步驟:

Step3 找到當前屬性所有數(shù)值的最大值dn和最小值d0,根據(jù)式8計算連續(xù)屬性Fi的初始分辨率Dro(F);

Step4 對Fi的所有數(shù)值升序排序,用最大值dn、最小值d0和集合中所有相鄰數(shù)對的平均值初始化分界點集合B;

Step5 將初始離散化方案設置為D:{[d0,dn]},定義變量GlobalCAIM,將其初始化為0;

Step6 初始化k為1;

Step7 暫時從集合B中添加一個不在D中的內(nèi)邊界,并計算相應的CAIM值;

Step8 在所有嘗試性的添加完成后,采用CAIM值最高的方案;

Step9 若CAIM>GlobalCAIM或者k

Step10 令k=k+1并前往Step7;

Step11 返回離散化方案D;

Step12 根據(jù)式(8)計算連續(xù)屬性Fi離散化后的分辨率Dr(F);

Step13 若Dr(F)

Output:離散化后的屬性值區(qū)間。

3 實驗分析

為檢驗所提出的改進CAIM算法是否具備優(yōu)越性,開展了相關實驗并分析了實驗結果。實驗目的是比較經(jīng)典CAIM算法與改進CAIM算法對數(shù)據(jù)集中的連續(xù)屬性進行離散化處理的效果。

鑒于本文中討論的算法都是由對象的類別與各屬性之間的依賴關系得到離散化方案,本實驗所使用的是UCI數(shù)據(jù)庫中的公開數(shù)據(jù)集,數(shù)據(jù)集的基本信息如表2所示。

表2 實驗數(shù)據(jù)集

使用2種算法對數(shù)據(jù)集進行離散化處理,得到對應的8個離散數(shù)據(jù)集,隨機選取其中80%的數(shù)據(jù)作為訓練數(shù)據(jù)集,剩余的數(shù)據(jù)作為測試數(shù)據(jù)集,運用支持向量機對離散數(shù)據(jù)進行分類。采用“一對多”多分類,模型選用C-支持向量分類機,核函數(shù)選用高斯核。分類之前需要對各數(shù)據(jù)集的離散數(shù)據(jù)進行歸一化處理,方法為

(18)

式(18)中:ai為任意離散數(shù)據(jù);ni為歸一化之后的數(shù)據(jù),-1≤ni≤1。

歸一化完成后開始分類,計算每個離散數(shù)據(jù)集用于分類的精度,結果如表3所示。

表3 分類精度

從表3結果來看,用改進CAIM算法處理的數(shù)據(jù)集的分類精度總體較用經(jīng)典CAIM算法處理的數(shù)據(jù)集高,表明改進算法造成的信息缺失較少,離散化效果較好。

為檢驗本文中所提方法的有效性,以某型裝備為例進行實驗。采集某型裝備運行過程中的測試數(shù)據(jù),提取部分數(shù)據(jù)建立數(shù)據(jù)決策表,包括產(chǎn)品類型、氣溫、加工溫度、轉速、扭矩等屬性,數(shù)據(jù)決策表見表4。

表4 數(shù)據(jù)決策表

原始數(shù)據(jù)除了包含離散型數(shù)據(jù),還包含大量連續(xù)型數(shù)據(jù),運用所提方法進行數(shù)據(jù)處理,得到表5所示離散化編碼。

表5 離散化編碼

根據(jù)離散化編碼對原始數(shù)據(jù)進行處理,將其中的連續(xù)型數(shù)據(jù)轉化為離散數(shù)據(jù),離散化后的數(shù)據(jù)決策表如表6所示。

將關聯(lián)規(guī)則挖掘這一重要的數(shù)據(jù)挖掘技術應用于離散化后的數(shù)據(jù),采用了經(jīng)典的Apriori算法[16]。根據(jù)關聯(lián)規(guī)則基本原理,最小支持度和最小置信度是用戶根據(jù)需要設定的2個閾值。最小支持度規(guī)定關聯(lián)規(guī)則必須滿足的最低重要程度,最小置信度規(guī)定關聯(lián)規(guī)則必須滿足的最低可靠程度。這些參數(shù)對算法的執(zhí)行過程和結果具有重要影響,對于運行中產(chǎn)生的項集,若其支持度不低于最小支持度,則將其視為頻繁項集;如果一條關聯(lián)規(guī)則的支持度不低于最小支持度,且置信度不低于最小置信度,則稱其為強關聯(lián)規(guī)則。支持度閾值和置信度閾值的取值由用戶自行決定,通常支持度閾值不宜設得過高,防止有用信息過多丟失。初次實驗將支持度閾值設為10%,置信度閾值設為70%,由于裝備發(fā)生質(zhì)量特性退化,出現(xiàn)顯性故障的情況相對較少,若希望發(fā)掘出更多與此類情況相關的知識,可動態(tài)調(diào)整參數(shù)設置多次實驗。實驗得到若干與裝備壽命周期內(nèi)的質(zhì)量變化規(guī)律相關的規(guī)則,表7列出了部分強關聯(lián)規(guī)則。

表7 強關聯(lián)規(guī)則

規(guī)則1表示裝備散熱失效時空氣溫度為301.65～303.75 K,說明散熱失效這一故障模式與空氣溫度之間存在關聯(lián),裝備運行時若氣溫處于301.65～303.75 K,需重點關注散熱性能。

規(guī)則2表示裝備運行功率為1 154.4～3 514.3 W時發(fā)生斷電。

規(guī)則3表示裝備運行功率為9 023.9～10 524.3 W時發(fā)生斷電。結合規(guī)則2與規(guī)則3可知,該型裝備不適合在3 514.3 W以下或9 023.9 W以上的功率下工作,否則容易斷電,日常使用中應盡量避免功率過低或過高。

由以上分析說明本文所提方法是有效的。

4 結論

1) 提出一種基于改進CAIM算法的裝備質(zhì)量數(shù)據(jù)離散化方法,用于裝備質(zhì)量信息分析的數(shù)據(jù)預處理,解決數(shù)據(jù)類型不適應數(shù)據(jù)挖掘方法的問題。

2) 在經(jīng)典算法的基礎上進行了改進,引入粗糙集理論和屬性分辨率,實現(xiàn)了對過度離散化的限制;提出屬性重要性評價方法,減少了數(shù)據(jù)離散化過程中的信息缺失。通過對比實驗驗證了本文中所提方法的優(yōu)越性。

3) 運用提出的方法對數(shù)據(jù)集進行預處理,并對其進行關聯(lián)規(guī)則挖掘,得到了反映裝備壽命周期內(nèi)質(zhì)量變化規(guī)律的知識,驗證了本文方法的有效性。