邢鵬程,曾獻(xiàn)輝

(1.東華大學(xué) 信息科學(xué)與技術(shù)學(xué)院,上海201620;2.數(shù)字化紡織服裝技術(shù)教育部工程研究中心,上海201620)

基于改進(jìn)Apriori算法的紡紗生產(chǎn)質(zhì)量預(yù)測(cè)研究

邢鵬程1,2,曾獻(xiàn)輝1,2

(1.東華大學(xué) 信息科學(xué)與技術(shù)學(xué)院,上海201620;2.數(shù)字化紡織服裝技術(shù)教育部工程研究中心,上海201620)

隨著工業(yè)大數(shù)據(jù)時(shí)代的到來(lái),紡織企業(yè)正加速向智能制造進(jìn)行產(chǎn)業(yè)轉(zhuǎn)型升級(jí)。以提高紡織品質(zhì)量預(yù)測(cè)準(zhǔn)確度為研究目標(biāo),在基于關(guān)聯(lián)規(guī)則Apriori算法及引入興趣度的I_Apriori算法的紡紗生產(chǎn)質(zhì)量預(yù)測(cè)模型基礎(chǔ)上,針對(duì)Apriori算法效率低、時(shí)間復(fù)雜度大、不精確的缺點(diǎn),提出了一種基于遺傳算法的全局優(yōu)化策略,對(duì)Apriori算法進(jìn)行了改進(jìn)和優(yōu)化。通過(guò)對(duì)紡紗廠現(xiàn)場(chǎng)數(shù)據(jù)的試驗(yàn)和分析,對(duì)Apriori算法、I_Apriori算法和優(yōu)化算法效果進(jìn)行了對(duì)比,結(jié)果顯示優(yōu)化算法的處理效率更高、規(guī)則挖掘更準(zhǔn)確,對(duì)預(yù)測(cè)效果有顯著提升。

紡紗生產(chǎn);質(zhì)量預(yù)測(cè);Apriori算法;遺傳算法

0 前言

質(zhì)量預(yù)測(cè)作為一種質(zhì)量控制的高級(jí)手段,是紡織生產(chǎn)中重要的環(huán)節(jié)之一,準(zhǔn)確的紡織質(zhì)量預(yù)測(cè)可以大幅度地降低成本、提高生產(chǎn)效率。傳統(tǒng)的質(zhì)量預(yù)測(cè)方式主要是憑借技術(shù)人員的經(jīng)驗(yàn)來(lái)判斷配棉方案的可行性,缺乏對(duì)產(chǎn)品質(zhì)量和原棉性能指標(biāo)之間關(guān)系的細(xì)致研究,因此經(jīng)常會(huì)出現(xiàn)產(chǎn)品指標(biāo)要求不符合、產(chǎn)品質(zhì)量波動(dòng)、成本增高等問(wèn)題,浪費(fèi)了很多寶貴的時(shí)間和資源[1]。

近年來(lái),我國(guó)有關(guān)部門和紡織企業(yè)加大了對(duì)紡織品質(zhì)量預(yù)測(cè)的重視和研究,國(guó)家經(jīng)貿(mào)委和科技部都設(shè)立了相關(guān)項(xiàng)目資助該方面的工作[2]。目前智能化質(zhì)量預(yù)測(cè)系統(tǒng)多采用人工神經(jīng)網(wǎng)絡(luò)技術(shù)來(lái)實(shí)現(xiàn)分類、回歸與預(yù)測(cè)預(yù)報(bào)等,例如提出了神經(jīng)網(wǎng)絡(luò)預(yù)測(cè)模型,預(yù)測(cè)紗線質(zhì)量指標(biāo)[3]。

隨著智能質(zhì)量預(yù)測(cè)控制研究的不斷深入,許多優(yōu)秀的智能算法被提出來(lái)應(yīng)用于紡織領(lǐng)域,Apriori智能算法對(duì)企業(yè)的質(zhì)量預(yù)測(cè)和生產(chǎn)決策產(chǎn)生了良好的效果[4],但在實(shí)際應(yīng)用中,尤其在處理大數(shù)據(jù)的情況下,Apriori算法仍有很多缺陷:(1)掃描頻繁項(xiàng)集時(shí)會(huì)產(chǎn)生大量的候選項(xiàng)集,并且在剪枝過(guò)程中需要計(jì)算出每個(gè)候選項(xiàng)集的所有子集并判斷它們是否是頻繁的,因此算法的時(shí)間復(fù)雜度過(guò)大,同時(shí)候選項(xiàng)子集的重復(fù)組合增加了計(jì)算時(shí)間;(2)在計(jì)算候選項(xiàng)集的支持度時(shí),需要多次重新遍歷數(shù)據(jù)庫(kù)?；诩徔椘髽I(yè)的海量數(shù)據(jù)規(guī)模,Apriori算法的處理效率會(huì)大大降低,系統(tǒng)的I/O負(fù)載也會(huì)增大;(3)僅通過(guò)設(shè)置支持度和置信度來(lái)尋找關(guān)聯(lián)規(guī)則并不能保證數(shù)據(jù)的完整挖掘[5],最終得到的一些強(qiáng)關(guān)聯(lián)規(guī)則會(huì)與實(shí)際情況不符,無(wú)法滿足紡織企業(yè)智能制造的技術(shù)要求。

針對(duì)Apriori算法的不足,本文提出了一種基于遺傳算法的全局優(yōu)化算法,在優(yōu)化了修剪頻繁策略的基礎(chǔ)上,引入遺傳算法來(lái)避免窮舉搜索和搜索過(guò)程中的局部最優(yōu)解,對(duì)全局的搜索過(guò)程進(jìn)行了優(yōu)化。將傳統(tǒng)的Apriori算法、引入興趣度的I_Apriori算法以及全局優(yōu)化算法應(yīng)用到紡織大數(shù)據(jù)中并進(jìn)行了對(duì)比,試驗(yàn)顯示了改進(jìn)算法在大數(shù)據(jù)處理上的優(yōu)越性,提高了效率的同時(shí)有效地提取了最有價(jià)值的關(guān)聯(lián)規(guī)則。

1 Apriori算法和I_Apriori算法

1.1 Apriori算法

Apriori算法的原理是利用頻繁項(xiàng)集性質(zhì)的先驗(yàn)知識(shí),通過(guò)逐層搜索的迭代方式,來(lái)基于k項(xiàng)集搜索k+1項(xiàng)集直至窮盡數(shù)據(jù)集中的所有頻繁項(xiàng)集[6],再根據(jù)置信度閾值從頻繁項(xiàng)集中產(chǎn)生關(guān)聯(lián)規(guī)則。Apriori算法計(jì)算頻繁項(xiàng)集可分為兩步:連接和剪枝。

1.1.1連接

通過(guò)頻繁k-項(xiàng)集Lk與自身進(jìn)行連接來(lái)產(chǎn)生候選(k+1)-項(xiàng)集Ck+1。連接規(guī)則如下:

頻繁k-項(xiàng)集Lk的任意兩個(gè)子集la、lb可以連接的條件是:若它們的前k-1項(xiàng)相同,則可連接。即

(la[1]=lb[1])∧(la[2]=lb[2])∧…∧(la[k-1]=lb[k-1])

則la、lb連接產(chǎn)生的結(jié)果是:

la[1]la[2]…la[k-1]la[k]lb[k]

1.1.2剪枝

剪枝主要分為兩個(gè)部分:

(1)依據(jù)Apriori“任一頻繁項(xiàng)集的所有非空子集也必須是頻繁的”的性質(zhì),對(duì)候選k-項(xiàng)集Ck的所有項(xiàng)集進(jìn)行掃描求出它們的(k-1)-項(xiàng)子集,并判斷這些子集是否是頻繁的;

(2)掃描數(shù)據(jù)庫(kù),求出候選k-項(xiàng)集Ck的每個(gè)候選項(xiàng)集的支持度,并與支持度閾值進(jìn)行比較,刪除小于支持度閾值的項(xiàng)集,得到最終的頻繁k-項(xiàng)集Lk。

1.2 I_Apriori算法

I_Apriori算法是針對(duì)Apriori算法容易忽視規(guī)則負(fù)相關(guān)性的缺點(diǎn)而產(chǎn)生的,例如某條強(qiáng)關(guān)聯(lián)規(guī)則A?B滿足可信度閾值,但其負(fù)相關(guān)規(guī)則置信度同樣也很大,導(dǎo)致此問(wèn)題的原因可能是項(xiàng)集間存在負(fù)相關(guān)的抑制作用,或者項(xiàng)集之間相互獨(dú)立,因此此規(guī)則是相互矛盾的,是錯(cuò)誤的?；谏鲜鰡?wèn)題,提出一個(gè)興趣度模型:

此興趣度的范圍是[-1,1],即當(dāng)interest(A?B)＞0時(shí),A對(duì)B是促進(jìn)作用,且當(dāng)興趣度越接近1,則A和B的關(guān)聯(lián)性越強(qiáng);當(dāng)interest(A?B)＜0時(shí),A對(duì)B是抑制作用,且當(dāng)興趣度越接近-1,則ˉA和B的關(guān)聯(lián)性越強(qiáng),可以看出A?B規(guī)則的負(fù)關(guān)聯(lián)規(guī)則ˉA?B并沒(méi)有被忽視,所以此規(guī)則是相互矛盾的,可刪除此規(guī)則;當(dāng)interest(A?B)=0時(shí),A與B獨(dú)立不相關(guān)。

I_Apriori算法有效地去除錯(cuò)誤的強(qiáng)關(guān)聯(lián)規(guī)則,但和Apriori算法一樣,在尋找頻繁項(xiàng)集時(shí)仍要對(duì)數(shù)據(jù)庫(kù)進(jìn)行規(guī)模較大的遍歷,同時(shí)也無(wú)法避免大量的候選項(xiàng)子集的重復(fù)組合。本文針對(duì)上述缺點(diǎn)提出了基于遺傳算法的全局優(yōu)化算法。

2 基于遺傳算法的Apriori全局優(yōu)化算法

此算法主要從兩個(gè)方面進(jìn)行優(yōu)化:一是在執(zhí)行連接剪枝步驟之前對(duì)頻繁項(xiàng)集進(jìn)行修剪,以減少候選項(xiàng)集數(shù)目,提高效率;二是引入遺傳算法對(duì)尋找頻繁項(xiàng)集的搜索過(guò)程進(jìn)行全局優(yōu)化。

2.1 修剪頻繁項(xiàng)集策略

在生成頻繁k-項(xiàng)集后,利用Apriori算法的性質(zhì)2,來(lái)簡(jiǎn)化執(zhí)行連接剪枝步驟所要用的項(xiàng)集數(shù)量,從而減少了連接產(chǎn)生候選(k+1)-項(xiàng)集的過(guò)程中重復(fù)組合的數(shù)量級(jí),優(yōu)化了執(zhí)行時(shí)間,預(yù)計(jì)采用改進(jìn)后的Apriori算法可以使掃描次數(shù)減少一半[7]。

性質(zhì)2為某元素要成為頻繁k-項(xiàng)集的一元素,該元素在頻繁k-項(xiàng)集中的出現(xiàn)次數(shù)必須不小于k次,否則包含此元素的項(xiàng)集不能產(chǎn)生候選(k+1)-項(xiàng)集[8]。

2.2 遺傳算法全局優(yōu)化策略

Apriori算法的核心問(wèn)題是如何找到頻繁項(xiàng)集,利用遺傳算法對(duì)此全局搜索過(guò)程進(jìn)行全局優(yōu)化,可以大幅度地提高Apriori算法的效率。

根據(jù)實(shí)際問(wèn)題,先對(duì)紡織生產(chǎn)中的數(shù)據(jù)進(jìn)行編碼,例如,影響棉紗線單強(qiáng)的因素有嘜頭、技等、回潮率等物理屬性,由于設(shè)備采集的此類數(shù)據(jù)類型屬于非布爾型數(shù)據(jù),且每個(gè)屬性的取值是連續(xù)的、不固定的,因此需要根據(jù)歷史數(shù)據(jù)和實(shí)際情況對(duì)屬性取值劃分為區(qū)間,并將這些區(qū)間定義為“值1”、“值2”,…,“值n”。如表1所示。

利用適應(yīng)度函數(shù)來(lái)評(píng)價(jià)個(gè)體的優(yōu)劣,并決定此個(gè)體是否可以進(jìn)入下一代,因此定義適應(yīng)度函數(shù)是算法的關(guān)鍵。衡量項(xiàng)集是否頻繁的依據(jù)是此項(xiàng)集的支持度,因此根據(jù)支持度來(lái)定義適應(yīng)度函數(shù)。

一般來(lái)說(shuō)適應(yīng)度函數(shù)定義為:

其中,Supp(X)代表當(dāng)前項(xiàng)集X的支持度,Min Supp代表最小支持度閾值。

但由于算法目的是尋找單強(qiáng)屬性最好的關(guān)聯(lián)規(guī)則,所以我們更需要單強(qiáng)屬性較大的規(guī)則;同時(shí),對(duì)于單強(qiáng)屬性很低的關(guān)聯(lián)規(guī)則同樣有價(jià)值,因?yàn)槲覀兛梢酝ㄟ^(guò)此規(guī)則知道造成單強(qiáng)屬性低的因素,從而避免它。因此,在公式(2)的基礎(chǔ)上,通過(guò)設(shè)定單強(qiáng)屬性的權(quán)值來(lái)重新定義適應(yīng)度函數(shù):

其中,Supp(X1,X2,…,Xn-1)是除單強(qiáng)屬性其他所有屬性組合的支持度,W1～6是單強(qiáng)屬性的權(quán)值,其中單強(qiáng)屬性數(shù)據(jù)設(shè)置為6個(gè)區(qū)間,單強(qiáng)屬性越高或者越低的權(quán)值越大,單強(qiáng)屬性趨于中間值的權(quán)值最低,如表2所示。

表1 棉線物理屬性的數(shù)據(jù)區(qū)間編碼表

表2 單強(qiáng)屬性區(qū)間及權(quán)值分配表

根據(jù)適應(yīng)度函數(shù)的大小,進(jìn)行選擇、交叉、變異的遺傳操作,產(chǎn)生下一代規(guī)則;經(jīng)過(guò)反復(fù)迭代以后,直到滿足終止條件,得到一組規(guī)則;最后利用置信度和興趣度對(duì)產(chǎn)生的所有規(guī)則進(jìn)行篩選和提取。流程如圖1所示。

圖1 優(yōu)化算法的運(yùn)作流程

3 對(duì)比和分析

以紡紗生產(chǎn)中對(duì)紡織產(chǎn)品的質(zhì)量預(yù)測(cè)為研究目標(biāo),根據(jù)紡織工藝特點(diǎn),確立了可通過(guò)棉纖維各項(xiàng)性能指標(biāo)來(lái)定量地預(yù)測(cè)成紗質(zhì)量[9]。通過(guò)Apriori算法、I_Apriori算法以及基于遺傳算法的全局優(yōu)化算法對(duì)棉纖維性能數(shù)據(jù)的試驗(yàn)和仿真,分析3種算法的預(yù)測(cè)性能,從而得出優(yōu)化算法的優(yōu)越性。

試驗(yàn)使用的是浙江某棉紡企業(yè)提供的現(xiàn)場(chǎng)數(shù)據(jù),共1 500條數(shù)據(jù)組成了棉紡紗線單強(qiáng)試驗(yàn)訓(xùn)練樣本,該組數(shù)據(jù)是在轉(zhuǎn)杯紡快速紡紗系統(tǒng)中普梳18.2 tex紗線所取得[9],其中截取的部分?jǐn)?shù)據(jù)如圖2所示。

圖2 棉紡紗線單強(qiáng)實(shí)驗(yàn)數(shù)據(jù)

通過(guò)測(cè)試樣本來(lái)檢驗(yàn)3個(gè)算法的預(yù)測(cè)性能。測(cè)試規(guī)則如下:試驗(yàn)遵循單一變量原則,在相同支持度和置信度條件下,分別通過(guò)3種算法得到了單強(qiáng)數(shù)據(jù)的預(yù)測(cè)值,并與真實(shí)值一同記錄下來(lái)。其中,每組試驗(yàn)的測(cè)試樣本是從數(shù)據(jù)庫(kù)中隨機(jī)選取5條數(shù)據(jù)(每條數(shù)據(jù)由嘜頭、技等、回潮率等12項(xiàng)組成),共做10組試驗(yàn)。

將每次的試驗(yàn)結(jié)果做成橫坐標(biāo)為真實(shí)值、縱坐標(biāo)為預(yù)測(cè)值的散點(diǎn)圖上,如圖3所示,其中圖中的斜線表示真實(shí)值和預(yù)測(cè)值絕對(duì)相等的軌跡。

圖3 測(cè)試結(jié)果

對(duì)10組試驗(yàn)結(jié)果進(jìn)行單因素方差分析,從數(shù)學(xué)的角度分析不同的算法是否對(duì)預(yù)測(cè)效果產(chǎn)生了顯著影響。利用均方差計(jì)算公式:

即預(yù)測(cè)值和真實(shí)值之差的算術(shù)平均數(shù)的平方根,它可以反應(yīng)某算法得出的預(yù)測(cè)值距離真實(shí)值的離散度,是表示預(yù)測(cè)精確度的重要指標(biāo)。

通過(guò)10組試驗(yàn)的測(cè)試分析,最后得到的結(jié)果是:Apriori算法的均方差為3.131,I_Apriori算法的均方差為2.862,基于遺傳算法的優(yōu)化算法均方差為1.11。因此可以看出,本文提出的全局優(yōu)化算法在準(zhǔn)確度上大大優(yōu)于傳統(tǒng)的Apriori算法和I_Apriori算法,傳統(tǒng)的Apriori算法并不能滿足實(shí)際生產(chǎn)需要,它的預(yù)測(cè)值離散度太大,不能很好地預(yù)測(cè)紡紗品的質(zhì)量;I_Apriori算法在一定程度上修正了傳統(tǒng)算法,其預(yù)測(cè)值的均方差降低,但預(yù)測(cè)效果仍然差強(qiáng)人意;對(duì)比Apriori算法和I_Apriori算法,全局優(yōu)化算法的預(yù)測(cè)效果得到了顯著的提升,預(yù)測(cè)結(jié)果較為理想,因此其性能遠(yuǎn)優(yōu)于傳統(tǒng)算法。

4 結(jié)語(yǔ)

在紡織智能制造中常用的兩種關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘算法Apriori算法和I_Apriori算法,針對(duì)它們的不足提出了一種基于遺傳算法的全局優(yōu)化Apriori算法,并通過(guò)對(duì)棉紡質(zhì)量數(shù)據(jù)的試驗(yàn)對(duì)比分析,證明此算法有效地彌補(bǔ)了Apriori算法的不足。

未來(lái)通過(guò)對(duì)算法的進(jìn)一步完善可應(yīng)用到大數(shù)據(jù)上,由于紡織企業(yè)數(shù)據(jù)庫(kù)規(guī)模較大,因此掃描和比較時(shí)間的縮減將會(huì)更加明顯,大幅度的優(yōu)化了算法的效率,滿足了紡織企業(yè)的生產(chǎn)要求。

[1] 吳軍輝.紡織加工質(zhì)量預(yù)測(cè)技術(shù)的研究與應(yīng)用[D].上海:東華大學(xué),2009.

[2] 王侃楓.基于計(jì)算智能的精梳毛紗質(zhì)量預(yù)測(cè)[D].上海:東華大學(xué),2009.

[3] 孫海蘭.紗線質(zhì)量分析與預(yù)測(cè)[D].蘇州:蘇州大學(xué),2004.

[4] 王達(dá)明.基于云計(jì)算與醫(yī)療大數(shù)據(jù)的Apriori算法的優(yōu)化研究[D].北京:北京郵電大學(xué),2015.

[5] 徐章艷,劉美玲,張師超,等.Apriori算法的三種優(yōu)化方法[J].計(jì)算機(jī)工程與應(yīng)用,2004,6(36):190-193.

[6] 陳 東.基于Apriori算法的大數(shù)據(jù)相關(guān)性分析研究[D].北京:中國(guó)地質(zhì)大學(xué)(北京),2016.

[7] 歐陽(yáng)桃紅.一種基于遺傳算法的關(guān)聯(lián)規(guī)則改進(jìn)算法[J].杭州電子科技大學(xué)學(xué)報(bào)(自然科學(xué)版),2015,9(5):79-81.

[8] 肖冬榮,楊 磊.基于遺傳算法的關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘[J].通信技術(shù),2010,1(43):205-207.

[9] 李利強(qiáng).支持精益生產(chǎn)的數(shù)據(jù)挖掘技術(shù)的研究與應(yīng)用[D].上海:東華大學(xué),2010.

Spinning Production Quality Prediction based on Improved Apriori Algorithm

XING Peng-cheng1,2,ZENG Xian-hui1,2
(1.School of Information Science and Technology,Donghua University,Shanghai 201620,China;2.Education Engineering Center of Digital Textile Technology,Shanghai 201620,China)

With the advent of the era of industrial big data,textile enterprises are accelerating transformation and upgrading to intelligent manufacturing industry.With quality prediction as the research object,intelligent textile quality prediction model based on the association rules Aproiori algorithm and I_Apriori algorithm with interest degree was presented.At the same time,aiming at the shortcomings of poor efficiency,large complexity of time and imprecise,a global optimization strategy based on genetic algorithm was proposed,and Apriori algorithm was improved and optimized.Through the experiment and analysis,the Apriori algorithm,I_Apriori algorithm and optimization algorithm were compared.The results showed that the improved algorithm was more high efficiency and precise in dealing with big data,the prediction effect had been improved significantly.

spinning production;quality prediction;Aproiori algorithm;genetic algorithm

TS104.1

A

1673-0356(2017)12-0019-04

2017-09-19

邢鵬程(1993-),男,碩士研究生,主要研究方向?yàn)閿?shù)據(jù)庫(kù)應(yīng)用技術(shù)、大數(shù)據(jù)分析,E-mail:491472180@qq.com。