基于聚類和關(guān)聯(lián)規(guī)則的煤炭項(xiàng)目挖掘

商新新，牟莉

（西安工程大學(xué)計(jì)算機(jī)科學(xué)學(xué)院，陜西西安 710048）

近年來(lái)，隨著兗礦集團(tuán)經(jīng)營(yíng)管理系統(tǒng)的不斷應(yīng)用，系統(tǒng)中積累了大量的歷史數(shù)據(jù)。同時(shí)，集團(tuán)每天都會(huì)產(chǎn)生大量的數(shù)據(jù)信息，不科學(xué)的數(shù)據(jù)處理方法會(huì)造成大量數(shù)據(jù)浪費(fèi)。文中從數(shù)據(jù)本身出發(fā)，對(duì)傳統(tǒng)管理系統(tǒng)產(chǎn)生的龐大數(shù)據(jù)進(jìn)行提取、分析，從中篩選出能夠影響企業(yè)發(fā)展的關(guān)鍵性數(shù)據(jù)。從大量數(shù)據(jù)中心發(fā)現(xiàn)隱藏的數(shù)據(jù)價(jià)值能夠?yàn)榧瘓F(tuán)的科學(xué)管理提供有效的數(shù)據(jù)支撐[1]。

在對(duì)數(shù)據(jù)進(jìn)行離散化時(shí)，文中采用優(yōu)化的K-means算法，主要針對(duì)項(xiàng)目完成屬性描述，為關(guān)聯(lián)規(guī)則挖掘提供有效的數(shù)據(jù)支撐。采用這種優(yōu)化過(guò)的Kmeans 算法的原因是在傳統(tǒng)的K-means 聚類[2]應(yīng)用中存在收斂速度慢、收斂效果差以及分析結(jié)果不準(zhǔn)確等缺陷，故文獻(xiàn)[3]中提出改進(jìn)退火算法，改進(jìn)了K-means 算法的收斂問(wèn)題。文獻(xiàn)[4]為解決利用Kmeans 算法計(jì)算學(xué)生成績(jī)不準(zhǔn)確的問(wèn)題，改進(jìn)并提出了標(biāo)準(zhǔn)偏移量的K-means 算法。文獻(xiàn)[5]中提出基于樣本分布聚類中心強(qiáng)度的改進(jìn)，并取得了較好的成果。因此，采用改變初始聚類的K-means 算法實(shí)現(xiàn)了對(duì)數(shù)據(jù)的聚類分析。

關(guān)聯(lián)規(guī)則分析算法主要是為了發(fā)現(xiàn)答案量數(shù)據(jù)之間的關(guān)聯(lián)性從而描述事物出現(xiàn)的規(guī)律[6]，同時(shí)Apriori 算法也是關(guān)聯(lián)規(guī)則中最常用的算法。但是傳統(tǒng)的Apriori 算法只有支持度和置信度兩個(gè)評(píng)估標(biāo)準(zhǔn)，導(dǎo)致挖掘的規(guī)則有時(shí)是人們不感興趣或錯(cuò)誤的。文獻(xiàn)[7]中為了提高Apriori 算法的挖掘效率，提出利用分割-垂直數(shù)據(jù)格式整合的思想，對(duì)Apriori 算法提出改進(jìn)。文獻(xiàn)[8]中提出了基于二分法的改進(jìn)Apriori 關(guān)聯(lián)算法研究。文中提出了一種引入差異性思想的Apriori 算法對(duì)兗礦集團(tuán)的項(xiàng)目信息進(jìn)行關(guān)聯(lián)規(guī)則分析。

1 算法建模

1.1 改進(jìn)的K-means算法

K-means 算法是聚類算法中的經(jīng)典算法，并得到廣泛的應(yīng)用。但是也存在許多缺陷，例如在運(yùn)算過(guò)程中輸入的參數(shù)范圍越大越容易導(dǎo)致算法分散等。傳統(tǒng)的聚類算法K-means 有兩個(gè)參數(shù)；1）初始聚類中心，2）聚類數(shù)目[9]。且參數(shù)1）的選擇是隨機(jī)的，所以容易導(dǎo)致聚類的不穩(wěn)定性。針對(duì)此問(wèn)題，文中將采用文獻(xiàn)[10]中的K-means 改進(jìn)方法。通過(guò)改變初始聚類中心，尋找一個(gè)類內(nèi)密集程度大的作為聚類中心，強(qiáng)度越大說(shuō)明聚類的效果越好。

目標(biāo)函數(shù)如（1）、（2）所示：

式中，p是所有數(shù)據(jù)的平方誤差總和，由此可知同一聚類中的對(duì)象相似度較高；而不同聚類中的對(duì)象相似度較低。其中，ci是所有標(biāo)記為i的數(shù)據(jù)xj和與標(biāo)記為i的數(shù)據(jù)個(gè)數(shù)nj的比值，d(xj,cj)是數(shù)據(jù)xj與標(biāo)記i的簇中心的歐氏距離。

改變初始聚類的K-means 算法步驟如下：

1）選擇較可靠的數(shù)據(jù)樣本集；

2）輸入K值，選擇初始聚類中心參數(shù)；

3）進(jìn)行K-means 算法至迭代結(jié)束；

4）計(jì)算pi；

5）選擇不同的聚類中心，循環(huán)2）、3）過(guò)程，直到p的值最小；

6）輸出與最小p值相對(duì)應(yīng)的結(jié)果，即為類內(nèi)密集程度。

1.2 改進(jìn)的Apriori算法

關(guān)聯(lián)規(guī)則算法可以找出龐大數(shù)據(jù)庫(kù)中不同因子之間的有趣關(guān)系[10]。假設(shè)關(guān)聯(lián)規(guī)則描述為(X?Y)，X為規(guī)則前件，Y為規(guī)則后件，規(guī)則支持度S(X?Y)如式（3）所示，置信度C(X?Y)如式（4）所示[12]。

在頻繁項(xiàng)集中，強(qiáng)規(guī)則是根據(jù)最小支持度和最小閾值來(lái)判斷的。最小支持度一般是由經(jīng)驗(yàn)豐富的管理者來(lái)制定，記作min_s(0 ＜min_s＜1)。最小置信度表示Apriori 算法的最低可靠性,記作min_c(0 ＜min_c＜1)。強(qiáng)規(guī)則要同時(shí)滿足最小支持度和最小置信度。

1.2.1 差異思想興趣度

文獻(xiàn)[12]中收集整理了多個(gè)關(guān)聯(lián)規(guī)則挖掘興趣度模型的計(jì)算公式，包括影響興趣度模型、信息量興趣度模型、差異思想興趣度模型、相關(guān)性興趣度模型和基于概率興趣度模型[11]。根據(jù)各方面的對(duì)比，文中將采用該文獻(xiàn)中的差異思想興趣度模型計(jì)算公式。將關(guān)聯(lián)規(guī)則(X?Y)興趣度表示為：

其中，C(X?Y)是關(guān)聯(lián)規(guī)則(X?Y)的置信度，如式（4）所示；S(Y)是關(guān)聯(lián)規(guī)則(X?Y)中Y的支持度，其值為count(X)/N。I(X?Y)的取值范圍為[-1,1]。基于差異思想興趣度模型的思想是由規(guī)則置信度和后項(xiàng)支持度的差異來(lái)定義的，其優(yōu)點(diǎn)是可以刪除不感興趣的規(guī)則，消除規(guī)則后項(xiàng)的高支持率對(duì)規(guī)則的影響[12]。

1.2.2 引入差異思想的Apriori算法

經(jīng)典的關(guān)聯(lián)規(guī)則算法Apriori 算法，其核心是一種遞推算法思想。傳統(tǒng)的Apriori 算法的關(guān)聯(lián)規(guī)則強(qiáng)度是由它的支持度和置信度來(lái)衡量的。但是僅憑支持度和置信度找不到準(zhǔn)確、完美的關(guān)聯(lián)規(guī)則。

針對(duì)以上問(wèn)題，引入差異思想的Apriori 算法，再構(gòu)建篩選后頻繁項(xiàng)集的關(guān)聯(lián)規(guī)則。興趣度能夠反映用戶對(duì)規(guī)則感興趣的程度，是針對(duì)用戶興趣綜合性考慮的[13-14]。引入差異性思想的Apriori 算法的運(yùn)行步驟如下：

輸入：輸入數(shù)據(jù)集D、置信度閾值、支持度閾值、興趣度閾值。

1）找出所有頻繁1 項(xiàng)集，通過(guò)掃描數(shù)據(jù)集D，設(shè)置K=1；

2）挖掘頻繁K項(xiàng)集；

3）K=K+1，執(zhí)行2）。

輸出：將符合條件的規(guī)則輸出。

2 挖掘案例集及結(jié)果分析

2.1 數(shù)據(jù)源

分析兗礦集團(tuán)的六大資金模塊中的項(xiàng)目信息，其中有207 個(gè)單位近5 年來(lái)積累的項(xiàng)目信息。六大資金數(shù)據(jù)包括技術(shù)改造、基礎(chǔ)建設(shè)、科技開(kāi)發(fā)、維檢、修理費(fèi)、生產(chǎn)安全。例如科技開(kāi)發(fā)模塊中項(xiàng)目信息包含單位名稱、建設(shè)類型、建設(shè)規(guī)模、開(kāi)工時(shí)間、投產(chǎn)年月、計(jì)劃資金、調(diào)整資金、調(diào)整類型、完成投資等17個(gè)項(xiàng)目信息屬性。科技開(kāi)發(fā)模塊部分原始數(shù)據(jù)如表1所示。

表1 部分原始數(shù)據(jù)集

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

由于現(xiàn)實(shí)中的數(shù)據(jù)是有缺陷的，所以為了使挖掘更加準(zhǔn)確，就要對(duì)數(shù)據(jù)進(jìn)行預(yù)處理。數(shù)據(jù)預(yù)處理如下：

數(shù)據(jù)清洗：去噪聲和無(wú)關(guān)數(shù)據(jù)；

數(shù)據(jù)集成：將不同來(lái)源、格式、特點(diǎn)的數(shù)據(jù)集中存儲(chǔ)；

數(shù)據(jù)變換：把原始數(shù)據(jù)轉(zhuǎn)換成為適合數(shù)據(jù)挖掘的形式；

數(shù)據(jù)規(guī)約：縮小數(shù)據(jù)集規(guī)模。

2.2.1 數(shù)據(jù)清洗

為了方便研究，要對(duì)不同的項(xiàng)目屬性信息進(jìn)行調(diào)整統(tǒng)一。例如科技開(kāi)發(fā)模塊中的項(xiàng)目類型是由文字描述的；定義資金時(shí)單位為“萬(wàn)元”或是“元”，資金的單位標(biāo)準(zhǔn)統(tǒng)一；基本建設(shè)中的建設(shè)規(guī)模等。此外原始數(shù)據(jù)中存在大量的冗余數(shù)據(jù)，因此應(yīng)將不涉及的數(shù)據(jù)項(xiàng)刪掉。

2.2.2 數(shù)據(jù)離散化

原始數(shù)據(jù)經(jīng)過(guò)數(shù)據(jù)清洗以后再進(jìn)行篩選和轉(zhuǎn)換，得到可利用的待測(cè)數(shù)據(jù)。由于文中研究的項(xiàng)目初始信息是按六大資金數(shù)據(jù)區(qū)分的。因此，針對(duì)這六大數(shù)據(jù)分別進(jìn)行分析。將直方圖劃分成5 個(gè)部分：很低、很高、高、低、中，再將其轉(zhuǎn)換為Apriori 算法的輸入值[15]，運(yùn)行結(jié)果如圖1 所示。

其中，技術(shù)改造數(shù)據(jù)398 組、基礎(chǔ)建設(shè)397 組、科技開(kāi)發(fā)399 組、維檢409 組、修理費(fèi)458 組、生產(chǎn)安全450 組。

項(xiàng)目的實(shí)施可能會(huì)受到不同因素的影響，例如施工單位、項(xiàng)目性質(zhì)等因素，項(xiàng)目是否能按時(shí)完成的情況并不穩(wěn)定，可能存在一些特征。圖1 是按值劃分后各類分布的直方圖，從圖中可以看出，項(xiàng)目信息的4 種情況中量級(jí)分化不是很明顯，一般情況下都是按時(shí)完成，只有極少數(shù)的項(xiàng)目可能在某些因素下拖延完成、調(diào)整以后完成或是未完成。

從圖1 中可以看出，六大資金項(xiàng)目的完成情況是比較穩(wěn)定的。其中科技開(kāi)發(fā)模塊中項(xiàng)目是偏向調(diào)整后完成，且該模塊中未完成項(xiàng)目比其他模塊多。技術(shù)改造模塊和基礎(chǔ)建設(shè)模塊中項(xiàng)目正常完成情況較平穩(wěn)。

圖1 六大資金項(xiàng)目完成情況劃分

將K-means 數(shù)據(jù)離散結(jié)果交給集團(tuán)管理者，為今后項(xiàng)目的管理提供參考數(shù)據(jù)。

2.3 挖掘規(guī)則及分析

文中引用差異思想興趣度的Apriori 算法，通過(guò)對(duì)比傳統(tǒng)的Apriori 算法[16]和引入差異思想興趣度的Apriori 算法，可以看出引入差異思想的Apriori 算法的優(yōu)點(diǎn)。組成3 種不同的參數(shù)，第一組：最小興趣度Imin=0.5，最小置信度Cmin=0.3；第二組：最小支持度Smin=0.06，最小興趣度Imin=0.5；第三組：最小支持度Smin=0.06，最小置信度Cmin=03。圖2～4 所示為兩種算法的規(guī)則變化情況。

從圖2～4 中可以看出，改進(jìn)后的Apriori 算法可以降低規(guī)則數(shù)量，提高挖掘的效率和質(zhì)量。設(shè)Smin=0.065，Cmin=0.36，Imin=0.5，得110 條強(qiáng)規(guī)則，部分規(guī)則如表2 所示。

表2 科技開(kāi)發(fā)挖掘規(guī)則部分展示

圖2 不同的支持度下兩種方法規(guī)則比較

圖3 不同置信度下兩種方法規(guī)則比較

圖4 不同的興趣度下兩種規(guī)則比較

從表2 中的規(guī)則1、6、11 可以看出，在得知建設(shè)規(guī)模的情況下，建設(shè)的規(guī)模越大該項(xiàng)目的投資金額越大，計(jì)劃申報(bào)的資金額度越大，完成工期越長(zhǎng)。項(xiàng)目的建設(shè)規(guī)模是在項(xiàng)目計(jì)劃階段最先考慮和最先確定的項(xiàng)目屬性。同時(shí)從表中的規(guī)則2、3、4、9、10 可以看出，項(xiàng)目的建設(shè)規(guī)模完全影響管理者對(duì)項(xiàng)目其他信息的判斷，例如項(xiàng)目的投產(chǎn)年分、工期長(zhǎng)度、具體計(jì)劃資金額度和最終完成該項(xiàng)目所需要的資金數(shù)。對(duì)項(xiàng)目的整體把握情況和根據(jù)此類型的項(xiàng)目預(yù)測(cè)其他相同類型的項(xiàng)目時(shí)，可以避免一些重復(fù)性的錯(cuò)誤，提高項(xiàng)目完成效率。因此，集團(tuán)應(yīng)該加強(qiáng)項(xiàng)目前期工作中對(duì)項(xiàng)目規(guī)模的把控，正確判斷建設(shè)規(guī)模。同時(shí)作為施工單位，根據(jù)項(xiàng)目規(guī)模更加精準(zhǔn)地預(yù)測(cè)項(xiàng)目的計(jì)劃數(shù)據(jù)，例如計(jì)劃資金的申報(bào)等。

由表2 中的規(guī)則5、8、9 可知，項(xiàng)目在實(shí)施過(guò)程中，調(diào)整金額、調(diào)整次數(shù)受項(xiàng)目類型、單位、建設(shè)規(guī)模的影響。項(xiàng)目類型同樣可以影響項(xiàng)目其他屬性的重要項(xiàng)目屬性，因此集團(tuán)管理者應(yīng)該加大對(duì)這些項(xiàng)目屬性的重視，減少建設(shè)規(guī)模和項(xiàng)目類型對(duì)未來(lái)項(xiàng)目實(shí)施帶來(lái)的不良影響。

3 結(jié)束語(yǔ)

歷史數(shù)據(jù)的充分利用，對(duì)企業(yè)管理有著重要的作用，提取其中隱藏的有價(jià)值的信息，對(duì)今后企業(yè)集團(tuán)的發(fā)展和管理有著戰(zhàn)略性的意義。根據(jù)兗礦集團(tuán)的實(shí)際情況和需求，采用改進(jìn)后的K-means算法，引入差異思想的Apriori 算法對(duì)集團(tuán)的歷史項(xiàng)目數(shù)據(jù)進(jìn)行離散、挖掘。首先在對(duì)歷史數(shù)據(jù)進(jìn)行離散時(shí)，采用改變初始聚類中心的K-means 方法，收到了較好的效果。再通過(guò)引入差異性思想的Apriori 算法對(duì)每一個(gè)模塊中的數(shù)據(jù)進(jìn)行針對(duì)性挖掘，提高了挖掘的質(zhì)量。最后，得到的相關(guān)數(shù)據(jù)結(jié)果對(duì)今后集團(tuán)項(xiàng)目的管理和未來(lái)項(xiàng)目的計(jì)劃、審批有著重要的意義，提高了集團(tuán)的決策力。