基于FP-Growth改進(jìn)算法的輪胎質(zhì)量數(shù)據(jù)分析

李敏波 丁 鐸 易 泳

1.復(fù)旦大學(xué)軟件學(xué)院, 上海，200433 2.復(fù)旦大學(xué)上海市數(shù)據(jù)科學(xué)重點(diǎn)實(shí)驗(yàn)室, 上海，200433

0 引言

隨著工業(yè)化與信息化的深度融合，信息技術(shù)滲透到工業(yè)企業(yè)產(chǎn)業(yè)鏈的各個(gè)環(huán)節(jié)，條形碼/二維碼、RFID、工業(yè)傳感器、工業(yè)自動(dòng)控制系統(tǒng)、ERP、MES、CAD/CAM/CAE/CAI 等技術(shù)廣泛應(yīng)用于制造業(yè)，尤其是隨著互聯(lián)網(wǎng)、移動(dòng)互聯(lián)網(wǎng)、工業(yè)物聯(lián)網(wǎng)等新一代信息技術(shù)在工業(yè)領(lǐng)域的應(yīng)用，制造企業(yè)所擁有的數(shù)據(jù)日益豐富。由工業(yè)設(shè)備所產(chǎn)生、生產(chǎn)過(guò)程采集和處理的數(shù)據(jù)量遠(yuǎn)大于企業(yè)中計(jì)算機(jī)和人工產(chǎn)生的數(shù)據(jù)，企業(yè)已經(jīng)進(jìn)入“工業(yè)大數(shù)據(jù)”時(shí)代，其數(shù)據(jù)的多樣性和復(fù)雜性正以創(chuàng)紀(jì)錄的速度迅速增長(zhǎng)[1]。

工業(yè)大數(shù)據(jù)是指在工業(yè)領(lǐng)域信息化應(yīng)用中所產(chǎn)生的海量數(shù)據(jù)，是為決策問(wèn)題服務(wù)的大數(shù)據(jù)集、大數(shù)據(jù)技術(shù)和大數(shù)據(jù)應(yīng)用的總稱。由于缺少有效的分析工具以及高效的計(jì)算技術(shù)來(lái)提取有用信息，工業(yè)大數(shù)據(jù)價(jià)值還未被充分利用。對(duì)于大多數(shù)制造企業(yè)，大數(shù)據(jù)應(yīng)用仍以內(nèi)部數(shù)據(jù)為主，多數(shù)停留在擴(kuò)大數(shù)據(jù)來(lái)源與增加數(shù)量的初級(jí)階段，將生產(chǎn)數(shù)據(jù)、設(shè)備運(yùn)行數(shù)據(jù)、質(zhì)量檢驗(yàn)數(shù)據(jù)實(shí)時(shí)采集并存檔，提供數(shù)據(jù)的統(tǒng)計(jì)查詢，僅在需要時(shí)進(jìn)行數(shù)據(jù)恢復(fù)與分析，而不是像亞馬遜、谷歌、阿里巴巴等互聯(lián)網(wǎng)公司將歷史數(shù)據(jù)視為數(shù)據(jù)資產(chǎn)而用于運(yùn)營(yíng)與決策過(guò)程中。

隨著智能制造的應(yīng)用推廣，越來(lái)越多的工業(yè)企業(yè)開(kāi)始重視工業(yè)大數(shù)據(jù)的價(jià)值，圍繞產(chǎn)品研發(fā)創(chuàng)新、生產(chǎn)線監(jiān)測(cè)與預(yù)警、設(shè)備故障診斷與維護(hù)、供應(yīng)鏈優(yōu)化管理、質(zhì)量監(jiān)測(cè)預(yù)測(cè)等方面開(kāi)展工業(yè)大數(shù)據(jù)集成應(yīng)用。工業(yè)大數(shù)據(jù)面臨的挑戰(zhàn)在于挖掘歷史大數(shù)據(jù)中蘊(yùn)含的知識(shí)，但知識(shí)不是直接呈現(xiàn)在數(shù)據(jù)中，而是呈現(xiàn)在用于揭示數(shù)據(jù)的模型中[2]。YAN等[3]提出了工業(yè)大數(shù)據(jù)問(wèn)題的一種框架， 并介紹了智能制造、工業(yè)大數(shù)據(jù)帶來(lái)的挑戰(zhàn)，如可靠性與安全性。張潔等[4]提出了一種大數(shù)據(jù)驅(qū)動(dòng)的“關(guān)聯(lián)+預(yù)測(cè)+調(diào)控”決策模式，幫助企業(yè)深層次地挖掘工業(yè)生產(chǎn)規(guī)律，提供精準(zhǔn)決策。針對(duì)制造企業(yè)質(zhì)量異常數(shù)據(jù)分析，可以采用ADTree決策樹(shù)、FP-Growth[5]等算法。

本文選取輪胎行業(yè)制造大數(shù)據(jù)作為研究背景，通過(guò)整合輪胎企業(yè)各個(gè)生產(chǎn)環(huán)節(jié)的多源數(shù)據(jù)，構(gòu)建結(jié)構(gòu)化的質(zhì)量分析數(shù)據(jù)集。對(duì)質(zhì)量分析數(shù)據(jù)集進(jìn)行關(guān)聯(lián)分析挖掘，可以幫助輪胎企業(yè)發(fā)現(xiàn)產(chǎn)品制造過(guò)程中的質(zhì)量異常及其影響因素，不僅能夠精確定位質(zhì)量問(wèn)題, 而且能幫助企業(yè)改善工藝流程參數(shù)。傳統(tǒng)的FP-Growth算法存在頻繁項(xiàng)樹(shù)構(gòu)建效率低的不足，本文改進(jìn)了FP-Growth算法的頻繁項(xiàng)樹(shù)建樹(shù)策略，提升了其性能，使其適用于輪胎行業(yè)質(zhì)量大數(shù)據(jù)分析。

1 輪胎質(zhì)量數(shù)據(jù)分析

對(duì)輪胎企業(yè)來(lái)說(shuō)，其產(chǎn)品質(zhì)量控制是非常關(guān)鍵的。在輪胎制造過(guò)程中，企業(yè)積累了大量輪胎生產(chǎn)數(shù)據(jù)與輪胎檢測(cè)數(shù)據(jù)。在大數(shù)據(jù)時(shí)代，如何利用工業(yè)大數(shù)據(jù)的挖掘技術(shù)，從海量時(shí)間序列生產(chǎn)制造數(shù)據(jù)中尋找質(zhì)量傳遞的規(guī)律，實(shí)現(xiàn)產(chǎn)品質(zhì)量的有效控制與改善，是輪胎企業(yè)面臨的新難題，由此，質(zhì)量數(shù)據(jù)分析成為工業(yè)大數(shù)據(jù)的重要需求。針對(duì)采集到的輪胎生產(chǎn)過(guò)程數(shù)據(jù)，利用傳統(tǒng)概率統(tǒng)計(jì)方法以及數(shù)據(jù)挖掘算法來(lái)構(gòu)建完整的、有針對(duì)性的分析模型，可通過(guò)關(guān)聯(lián)分析找出影響輪胎質(zhì)量的關(guān)鍵因素，為后續(xù)的質(zhì)量改進(jìn)、生產(chǎn)工藝改進(jìn)提供合理的數(shù)據(jù)支持。

1.1 輪胎質(zhì)量相關(guān)數(shù)據(jù)的獲取與整合

輪胎制造過(guò)程數(shù)據(jù)是產(chǎn)品在生產(chǎn)過(guò)程中產(chǎn)生的相關(guān)數(shù)據(jù)，包括制造過(guò)程中產(chǎn)生的中間狀態(tài)，如溫度、壓力等信息，操作工位的工位/設(shè)備編號(hào)，使用工裝或夾具的編碼信息，工位/設(shè)備報(bào)警類信息，合格、不合格產(chǎn)品信息，工序加工時(shí)間，質(zhì)量檢測(cè)數(shù)據(jù)與產(chǎn)品物料追溯信息。

輪胎質(zhì)量檢測(cè)分為成品胎外觀檢測(cè)、X射線掃描、動(dòng)平衡檢測(cè)與均勻性檢測(cè)以及產(chǎn)品抽樣性能試驗(yàn)，這些檢測(cè)數(shù)據(jù)由企業(yè)MES系統(tǒng)管理。輪胎動(dòng)平衡檢測(cè)數(shù)據(jù)包括產(chǎn)品編號(hào)、各個(gè)檢測(cè)項(xiàng)目和檢測(cè)結(jié)果，動(dòng)平衡檢測(cè)結(jié)果較為重要的3個(gè)檢測(cè)指標(biāo)為BAL_RANK(上面不平衡量)、RO_RANK(靜不平衡量)與UFM_RANK(偶不平衡量)，每個(gè)指標(biāo)值對(duì)應(yīng)在1～5之間取值，只要這3個(gè)指標(biāo)中至少有一個(gè)指標(biāo)為4或5，則產(chǎn)品為不合格品。

質(zhì)量檢測(cè)數(shù)據(jù)定義如下：

insp_Data=product_id,insp_items,insp_result

式中，product_id為輪胎編號(hào)；insp_items為輪胎檢驗(yàn)項(xiàng)目；insp_result為輪胎檢測(cè)結(jié)果。

制造數(shù)據(jù)是輪胎生產(chǎn)過(guò)程中產(chǎn)生的相關(guān)數(shù)據(jù)，單工序的制造數(shù)據(jù)定義如下：

product_Data=(product_id,equip_id,proc_time,

shift,operator,proc_parameters)

其中，product_id是產(chǎn)品編號(hào)；equip_id是設(shè)備編號(hào)；proc_time是生產(chǎn)時(shí)間；shift是班組編號(hào)；operator是操作人員編號(hào)；proc_parameters是該工序的工藝參數(shù)集。

以上兩種數(shù)據(jù)可以用product_id關(guān)聯(lián)起來(lái)，形成結(jié)構(gòu)化的質(zhì)量分析數(shù)據(jù)集。

1.2 輪胎質(zhì)量數(shù)據(jù)分析方法

輪胎生產(chǎn)制造過(guò)程中產(chǎn)生的各種數(shù)據(jù)存儲(chǔ)在企業(yè)的MES、ERP、質(zhì)量檢測(cè)等不同系統(tǒng)中，這些多源異構(gòu)數(shù)據(jù)需要集中獲取并整合為結(jié)構(gòu)化數(shù)據(jù)，從而用于數(shù)據(jù)挖掘。首先使用數(shù)據(jù)采集系統(tǒng)將這些數(shù)據(jù)存儲(chǔ)在關(guān)系型數(shù)據(jù)庫(kù)中；然后利用Sqoop開(kāi)源工具配置關(guān)系型數(shù)據(jù)庫(kù)與HDFS Hive數(shù)據(jù)倉(cāng)庫(kù)之間的數(shù)據(jù)連接，以增量導(dǎo)入的方式獲取所有質(zhì)量相關(guān)數(shù)據(jù)，構(gòu)建輪胎生產(chǎn)制造數(shù)據(jù)倉(cāng)庫(kù)，實(shí)現(xiàn)數(shù)據(jù)集中管理。使用Hive數(shù)據(jù)倉(cāng)庫(kù)建立質(zhì)量檢測(cè)數(shù)據(jù)與制造過(guò)程數(shù)據(jù)多表合并的結(jié)構(gòu)化質(zhì)量分析數(shù)據(jù)集Quality_DataSet，該數(shù)據(jù)集將應(yīng)用于后續(xù)的質(zhì)量數(shù)據(jù)關(guān)聯(lián)分析。

質(zhì)量數(shù)據(jù)的分析流程見(jiàn)圖1，數(shù)據(jù)分析流程包括數(shù)據(jù)獲取與整合、數(shù)據(jù)預(yù)處理、質(zhì)量分析和分析結(jié)果整理4個(gè)階段。根據(jù)質(zhì)量分析的主題和產(chǎn)品對(duì)象SKU，使用Hive SQL查詢語(yǔ)句由Hive質(zhì)量分析數(shù)據(jù)集中生成某產(chǎn)品SKU質(zhì)量分析數(shù)據(jù)子集Quality_SubDataSet。數(shù)據(jù)預(yù)處理負(fù)責(zé)重復(fù)數(shù)據(jù)的剔除、異常數(shù)據(jù)的刪除、缺失數(shù)據(jù)的補(bǔ)全或去除處理等。

針對(duì)輪胎檢測(cè)不合格品的質(zhì)量異常，要從輪胎生產(chǎn)制造過(guò)程的“人、機(jī)、料、法、環(huán)”5個(gè)方面分析產(chǎn)品質(zhì)量的影響因素。造成輪胎質(zhì)量異常的影響因素?cái)?shù)據(jù)(包括輪胎成形與硫化過(guò)程溫度、壓力等屬性)均是一系列時(shí)序數(shù)據(jù)，對(duì)這些屬性進(jìn)一步細(xì)化，抽取其統(tǒng)計(jì)指標(biāo)作為輔助性特征，這些統(tǒng)計(jì)特征包括平均值、方差、最大值、最小值、極差等，然后添加到質(zhì)量異常數(shù)據(jù)追溯分析數(shù)據(jù)集中，作為后續(xù)關(guān)聯(lián)分析的輸入。

質(zhì)量分析分為單因素分析與多因素分析，單因素分析就是使用統(tǒng)計(jì)的方式，通過(guò)執(zhí)行Hive SQL查詢語(yǔ)句，得到單個(gè)因素(操作人員、班組、加工設(shè)備、工藝控制參數(shù)等)與產(chǎn)品不合格率的關(guān)系。對(duì)山東某輪胎公司千萬(wàn)數(shù)量級(jí)的輪胎質(zhì)量數(shù)據(jù)進(jìn)行單因素分析，可以得到以下初步結(jié)論：不同物料編碼的輪胎不合格率差異十分明顯，其中，21種物料編碼的輪胎占產(chǎn)品總數(shù)的0.7%，卻產(chǎn)生了13.3%的不合格品。單因素分析同樣能排除一些影響因素，例如，輪胎硫化班組分早、中、晚班，容易想到晚班的工人是否會(huì)因?yàn)榫Σ粷?jì)導(dǎo)致不合格率增加，但是統(tǒng)計(jì)結(jié)果表明，3個(gè)班組的平均合格率幾乎相同。

產(chǎn)品質(zhì)量的多因素分析可使用數(shù)據(jù)挖掘的方法來(lái)找到造成不良品的影響因素。本文使用FP Growth關(guān)聯(lián)分析作為輪胎質(zhì)量分析的算法，例如把輪胎生產(chǎn)過(guò)程中的硫化工序工藝參數(shù)特征值(內(nèi)溫,內(nèi)壓,模溫,板溫的最大值、最小值、平均值、方差)、硫化操作人員編號(hào)(CUR_ZJS_ID)、成形操作人員編號(hào)(ZJS_ID)、各生產(chǎn)設(shè)備編號(hào)(POT_ID,EQUIP_ID,EQUIP_CODE)、生產(chǎn)班次編號(hào)(CLASS)、生產(chǎn)車間編號(hào)(WORK_SHOP_CODE)、生產(chǎn)模具編號(hào)(MOLD_ID)、生產(chǎn)批次編號(hào)(CUR_BATCH_ID)等屬性作為FP-Growth算法的輸入，并將qualified字段設(shè)為標(biāo)記字段,該字段為1代表產(chǎn)品合格, 為2則代表產(chǎn)品不合格。FP-Growth算法將輸出一系列滿足支持度與置信度要求的關(guān)聯(lián)規(guī)則作為挖掘結(jié)果， 由于傳統(tǒng)的FP-Growth算法建樹(shù)效率較低，在輪胎質(zhì)量數(shù)據(jù)關(guān)聯(lián)分析中存在性能提升空間，故本文對(duì)FP-Growth算法進(jìn)行改進(jìn)。

1.3 輪胎質(zhì)量大數(shù)據(jù)分析平臺(tái)

輪胎制造大數(shù)據(jù)分析平臺(tái)的系統(tǒng)架構(gòu)見(jiàn)圖2，制造大數(shù)據(jù)平臺(tái)的數(shù)據(jù)來(lái)源于ERP、MES、SCADA系統(tǒng)中產(chǎn)品與工藝數(shù)據(jù)、制造過(guò)程數(shù)據(jù)、設(shè)備運(yùn)行數(shù)據(jù)以及質(zhì)量檢測(cè)數(shù)據(jù)和圖像數(shù)據(jù)。大數(shù)據(jù)平臺(tái)通過(guò)集成Sqoop框架和自定義開(kāi)發(fā)的數(shù)據(jù)轉(zhuǎn)化接口API實(shí)現(xiàn)多源異構(gòu)數(shù)據(jù)獲取并將其整合存儲(chǔ)至分布式數(shù)據(jù)文件系統(tǒng)HDFS。輪胎制造大數(shù)據(jù)平臺(tái)提供關(guān)系型數(shù)據(jù)庫(kù)、NoSQL數(shù)據(jù)庫(kù)、Hive數(shù)據(jù)倉(cāng)庫(kù)等多種數(shù)據(jù)存儲(chǔ)。

大數(shù)據(jù)平臺(tái)使用實(shí)時(shí)流式計(jì)算Storm、并行計(jì)算Spark工具進(jìn)行大數(shù)據(jù)分析算法的并行計(jì)算。平臺(tái)集成Spark MLlib中的關(guān)聯(lián)分析、時(shí)間序列預(yù)測(cè)、分類、聚類、統(tǒng)計(jì)分析等大數(shù)據(jù)分析算法以實(shí)現(xiàn)制造過(guò)程的決策分析與預(yù)測(cè)。使用數(shù)理統(tǒng)計(jì)方法對(duì)提取到的質(zhì)量關(guān)鍵變量進(jìn)行標(biāo)準(zhǔn)化、歸一化處理，構(gòu)建多源數(shù)據(jù)融合的質(zhì)量大數(shù)據(jù)模型。利用過(guò)程監(jiān)控方法及多變量統(tǒng)計(jì)控制圖技術(shù)判斷失控變量，發(fā)現(xiàn)生產(chǎn)過(guò)程質(zhì)量問(wèn)題分布規(guī)律。對(duì)質(zhì)量缺陷問(wèn)題進(jìn)行缺陷問(wèn)題分類和聚類處理。使用K-means聚類算法將連續(xù)型屬性離散化，使用FP-Growth關(guān)聯(lián)算法加載關(guān)聯(lián)分析的數(shù)據(jù)集，得到關(guān)聯(lián)規(guī)則集。

圖2 大數(shù)據(jù)分析平臺(tái)架構(gòu)Fig.2 The architecture of big data analysis platform

2 FP-Growth改進(jìn)算法

2.1 FP-Growth關(guān)聯(lián)算法

關(guān)聯(lián)分析常被用來(lái)從數(shù)據(jù)中發(fā)現(xiàn)事物、特征間頻繁出現(xiàn)的相互依賴和關(guān)聯(lián)關(guān)系。被發(fā)現(xiàn)的關(guān)系可以是事先不知道、通過(guò)數(shù)據(jù)的關(guān)聯(lián)分析才獲得的。通過(guò)對(duì)輪胎制造數(shù)據(jù)與輪胎檢測(cè)不良率數(shù)據(jù)之間的關(guān)聯(lián)分析，找出不良率較高的輪胎生產(chǎn)過(guò)程影響因素，進(jìn)而整理出輪胎質(zhì)量異常的主要影響因素關(guān)聯(lián)規(guī)則集。

在執(zhí)行關(guān)聯(lián)分析前，需要對(duì)數(shù)據(jù)集的連續(xù)型屬性進(jìn)行離散化處理。首先使用K-means聚類算法對(duì)連續(xù)型屬性進(jìn)行必要的聚類，然后基于屬性取值的內(nèi)在結(jié)構(gòu)確定每個(gè)劃分簇的劃分邊界，最后按照這樣的劃分邊界對(duì)連續(xù)型屬性進(jìn)行離散化處理。K-means的目標(biāo)函數(shù)設(shè)置為

(1)

式中，xi為第i個(gè)樣本的坐標(biāo)；μci為第i個(gè)樣本在聚類簇中的聚類中心。

通過(guò)基于聚類結(jié)果抽取出來(lái)的離散化策略將所有連續(xù)型屬性離散化之后，數(shù)據(jù)集已經(jīng)符合多因素關(guān)聯(lián)分析的輸入規(guī)范，便可以作為輸入?yún)?shù)進(jìn)行關(guān)聯(lián)分析。調(diào)用Spark MLlib的FP-Growth關(guān)聯(lián)算法，加載關(guān)聯(lián)分析的數(shù)據(jù)集，得到關(guān)聯(lián)規(guī)則集。分析關(guān)聯(lián)規(guī)則集，結(jié)合輪胎質(zhì)量故障診斷知識(shí)和工藝知識(shí)，總結(jié)和整理出輪胎質(zhì)量影響的主要因素以及工藝參數(shù)優(yōu)化規(guī)則，為產(chǎn)品質(zhì)量改進(jìn)和工藝優(yōu)化提供數(shù)據(jù)支持。

數(shù)據(jù)的關(guān)聯(lián)分析能從大規(guī)模數(shù)據(jù)中分析并挖掘出有價(jià)值的關(guān)聯(lián)性知識(shí)，主要通過(guò)關(guān)聯(lián)規(guī)則的挖掘來(lái)實(shí)現(xiàn)，它可以分為兩大步驟：頻繁項(xiàng)集的生成和關(guān)聯(lián)規(guī)則的產(chǎn)生，其中，最關(guān)鍵的就是頻繁項(xiàng)集的生成，該步驟占據(jù)了關(guān)聯(lián)規(guī)則挖掘全過(guò)程的主要花銷。常用的頻繁項(xiàng)集挖掘算法有Apriori算法、FP-Growth算法等。Apriori算法由AGRAWAL等[6]提出，該算法特點(diǎn)是先生成候選項(xiàng)集，再由候選項(xiàng)集生成頻繁項(xiàng)集，這一過(guò)程會(huì)多次掃描數(shù)據(jù)庫(kù)，故該算法效率較低。隨后出現(xiàn)了很多Apriori改進(jìn)算法，如AprioriTid算法[7]；還有基于AprioriTid算法的AprioriTidList算法[8]，它使用鏈?zhǔn)浇Y(jié)構(gòu)，取得了更好的效果。然而，候選集的生成仍是該算法本質(zhì)上難以克服的瓶頸。FP-Growth算法是HAN等[9]提出的一種具有較好性能和伸縮性的頻繁項(xiàng)集挖掘算法，其特點(diǎn)是不需要產(chǎn)生候選項(xiàng)集，并且只需掃描2次數(shù)據(jù)庫(kù)。也有一些基于FP-Growth算法的改進(jìn)算法，如凌緒雄等[10]提出的無(wú)項(xiàng)頭表的FP-Growth算法在時(shí)間效率上略有提高。余彪等[11]提出了一種MFP-tree算法，采用分塊挖掘的方式處理數(shù)據(jù)，效率也有一定的提升。在并行化方面，AISSATOU等[12]提出了基于Spark的S-FPG算法，該算法能夠更好地挖掘大數(shù)據(jù)規(guī)模下的關(guān)聯(lián)規(guī)則；ZHOU等[13]提出了一種基于MapReduce框架的FP-Growth算法的并行化改進(jìn)算法。

FP-Growth算法的具體執(zhí)行流程如下。

(1)先掃描一遍數(shù)據(jù)集，得到項(xiàng)目集中每個(gè)項(xiàng)目出現(xiàn)的次數(shù)，定義最小支持度(項(xiàng)目出現(xiàn)最少次數(shù))，刪除那些小于最小支持度的項(xiàng)目，然后將原始數(shù)據(jù)集中的條目按項(xiàng)目集中降序進(jìn)行排列。

(2)第2次掃描，創(chuàng)建頻繁項(xiàng)頭表(從上往下降序)以及FP樹(shù)。

(3)對(duì)于每個(gè)項(xiàng)目(可以按照從下往上的順序)找到其條件模式基(conditional pattern base，CPB)，遞歸調(diào)用樹(shù)結(jié)構(gòu)，刪除小于最小支持度的項(xiàng)。如果最終呈現(xiàn)單一路徑的樹(shù)結(jié)構(gòu)，則直接列舉所有組合；非單一路徑的則繼續(xù)調(diào)用樹(shù)結(jié)構(gòu)，直到形成單一路徑即可。

FP-Growth算法分為構(gòu)造樹(shù)與挖掘樹(shù)兩個(gè)部分，算法偽代碼分別如下。

FP樹(shù)的構(gòu)造算法：

輸入：原始數(shù)據(jù)庫(kù)D，最小支持度minsup

輸出：數(shù)據(jù)庫(kù)D的FP樹(shù)

掃描數(shù)據(jù)庫(kù)D，收集頻繁項(xiàng)的集合F和它們的支持度。對(duì)F按照支持度降序排序，結(jié)果為頻繁項(xiàng)頭表H;創(chuàng)建FP-樹(shù)的根節(jié)點(diǎn)R，標(biāo)記為null;

對(duì)D中每個(gè)事務(wù)Trans：

選擇 Trans 中的頻繁項(xiàng)，并按H中的次序排序。設(shè)排序后的頻繁項(xiàng)表為[p | P]，p是第一個(gè)元素，P是剩余元素的表。調(diào)用insert_tree([p|P], R)。

函數(shù)insert_tree([p|P], T)：

如果T有子節(jié)點(diǎn)N使得N.item-name = p.item-name，則N 的計(jì)數(shù)增加1;

否則創(chuàng)建一個(gè)新節(jié)點(diǎn)N將其計(jì)數(shù)設(shè)置為1，鏈接到它的父節(jié)點(diǎn)T，并且在與它同名的頻繁項(xiàng)頭表中遍歷到最后一個(gè)節(jié)點(diǎn)，添加此新節(jié)點(diǎn)N;

如果P非空，遞歸地調(diào)用函數(shù)insert_tree(P, N);

FP樹(shù)的挖掘算法：

輸入：FP樹(shù)和最小支持度minsup

輸出：頻繁模式集合

通過(guò)調(diào)用FP_growth(FP_tree, null)實(shí)現(xiàn)

if(樹(shù)含單個(gè)路徑P) then

對(duì)P中節(jié)點(diǎn)的每個(gè)組合β：

產(chǎn)生模式β∪α，支持度support=β中節(jié)點(diǎn)的最小支持度;

Else{

對(duì)樹(shù)頭部的每一個(gè)ai：

生成模式β=ai∪α，支持度support=ai.support;

構(gòu)造β的條件模式基和β的條件FP樹(shù)Treeβ

if Treeβ≠ ? then調(diào)用 FP_Growth (Treeβ, β)}

2.2 FP-Growth算法的改進(jìn)

在傳統(tǒng)FP-Growth算法中，需要利用FP-Tree構(gòu)造算法生成一個(gè)包含完整頻繁項(xiàng)信息的FP樹(shù)， 其中，F(xiàn)P樹(shù)的頻繁項(xiàng)頭表具有2個(gè)屬性：item-Name(項(xiàng)名稱)和next_Node。next_Node是一個(gè)指針，指向FP樹(shù)中具有相同 item-Name 的第1個(gè)節(jié)點(diǎn)。在此過(guò)程中，要循環(huán)調(diào)用insert_tree( )算法插入新的樹(shù)節(jié)點(diǎn)，其中，有一個(gè)步驟就會(huì)用到頻繁項(xiàng)頭表這一數(shù)據(jù)結(jié)構(gòu)，把FP樹(shù)中的每個(gè)與項(xiàng)頭表具有相同名稱的項(xiàng)進(jìn)行連接。每次執(zhí)行上述過(guò)程時(shí)都需要回到項(xiàng)頭表的同名頭節(jié)點(diǎn)，然后從頭節(jié)點(diǎn)開(kāi)始遍歷，直至最后一個(gè)同名節(jié)點(diǎn)的域，再把新的節(jié)點(diǎn)插入最后一個(gè)節(jié)點(diǎn)后，進(jìn)入項(xiàng)頭表結(jié)構(gòu)中?？梢钥闯?，項(xiàng)頭表這一數(shù)據(jù)結(jié)構(gòu)的模型會(huì)直接影響 FP-Growth 算法的性能，在數(shù)據(jù)量較大的情況下，每次都從頭節(jié)點(diǎn)遍歷到尾端然后插入，這種方法的執(zhí)行效率明顯不好，有待改進(jìn)。

為了解決上述問(wèn)題，提升算法的效率，本文提出了一種優(yōu)化后的項(xiàng)頭表數(shù)據(jù)結(jié)構(gòu)，在原有的項(xiàng)頭表結(jié)構(gòu)上添加一個(gè)新的屬性尾節(jié)點(diǎn)tail，用于記錄每一個(gè)數(shù)據(jù)項(xiàng)當(dāng)前的最后一個(gè)節(jié)點(diǎn)。通過(guò)這種新的頻繁項(xiàng)頭表數(shù)據(jù)結(jié)構(gòu)，執(zhí)行insert_tree()算法并在項(xiàng)頭表插入新節(jié)點(diǎn)時(shí)，就可以避免遍歷當(dāng)前節(jié)點(diǎn)的鏈表而導(dǎo)致算法效率不佳，直接通過(guò)tail屬性找到表尾進(jìn)行新節(jié)點(diǎn)的插入即可。在輪胎質(zhì)量數(shù)據(jù)分析中，該改進(jìn)會(huì)有更突出的效果，由于這些數(shù)據(jù)集中相同的項(xiàng)大量存在(如同一主機(jī)手會(huì)經(jīng)手大量輪胎)，同樣會(huì)出現(xiàn)在FP樹(shù)中的各個(gè)分支，故加入新的屬性尾節(jié)點(diǎn)tail記錄數(shù)據(jù)項(xiàng)的最后一個(gè)節(jié)點(diǎn)，對(duì)輪胎質(zhì)量數(shù)據(jù)分析的效率提升會(huì)起到很好的作用。

優(yōu)化后的項(xiàng)頭表數(shù)據(jù)結(jié)構(gòu)見(jiàn)表1。具體定義如下。

表1 優(yōu)化后的項(xiàng)頭表數(shù)據(jù)結(jié)構(gòu)

Public class HeadTable{

Private String item_Name;//數(shù)據(jù)項(xiàng)名稱

Private Node next_Node;//項(xiàng)頭表中的下一個(gè)同名節(jié)點(diǎn)

Private Node tail;//該項(xiàng)頭表中的最后一個(gè)同名節(jié)點(diǎn)位置

}//優(yōu)化后的項(xiàng)頭表

在執(zhí)行FP-Tree構(gòu)造算法時(shí)，利用優(yōu)化的項(xiàng)頭表，避免了繁瑣的循環(huán)遍歷操作：

If (HeadTable.tail == null)

Then

HeadTable.next_Node =新節(jié)點(diǎn);

HeadTable.tail =新節(jié)點(diǎn);

Else

HeadTable.tail.next_Node =新節(jié)點(diǎn);

HeadTable.tail =新節(jié)點(diǎn);

引入優(yōu)化后的頻繁項(xiàng)頭表后，新的FP-Tree構(gòu)造算法如下：

FP_Tree(D, minsup)

輸入：原始數(shù)據(jù)庫(kù)D，最小支持度minsup

輸出：數(shù)據(jù)庫(kù)D的FP樹(shù)

掃描數(shù)據(jù)庫(kù)D，收集頻繁項(xiàng)的集合F和它們的支持度。對(duì)F按照支持度降序排序，結(jié)果為頻繁項(xiàng)頭表H;

創(chuàng)建FP-樹(shù)的根節(jié)點(diǎn)R，標(biāo)記為null;

對(duì)D中每個(gè)事務(wù)Trans：

選擇 Trans 中的頻繁項(xiàng)，并按H中的次序排序。設(shè)排序后的頻繁項(xiàng)表為[p | P]，p是第一個(gè)元素，P是剩余元素的表。調(diào)用insert_tree([p|P], R)。

函數(shù)insert_tree([p|P], T)：

如果T有子節(jié)點(diǎn)N使得N.item-name = p.item-name，則N 的計(jì)數(shù)增加1;

否則創(chuàng)建一個(gè)新節(jié)點(diǎn)N將其計(jì)數(shù)設(shè)置為1，鏈接到它的父節(jié)點(diǎn)T，并且在與它同名的頻繁項(xiàng)頭表的tail屬性中找到當(dāng)前最末節(jié)點(diǎn)，添加此新節(jié)點(diǎn)N，并設(shè)新節(jié)點(diǎn)N為新的tail;

如果P非空，遞歸地調(diào)用函數(shù)insert_tree(P, N);

現(xiàn)有以下數(shù)據(jù)庫(kù)D，見(jiàn)表2，設(shè)最小支持度閾值為3。由該數(shù)據(jù)庫(kù)通過(guò)算法構(gòu)造得出的FP樹(shù)結(jié)果見(jiàn)圖3。

表2 數(shù)據(jù)庫(kù)D

圖3 根據(jù)優(yōu)化后的FP-Growth算法構(gòu)建的FP-TreeFig.3 The FP-Tree built based on the optimized FP-Growth algorithm

3 FP-Growth改進(jìn)算法在輪胎質(zhì)量大數(shù)據(jù)分析應(yīng)用

3.1 FP-Growth算法改進(jìn)實(shí)驗(yàn)

對(duì)改進(jìn)后的FP-Growth算法進(jìn)行以下3個(gè)實(shí)驗(yàn)。

實(shí)驗(yàn)1。不同物料編碼數(shù)據(jù)集FP樹(shù)構(gòu)造時(shí)間對(duì)比。取輪胎質(zhì)量分析數(shù)據(jù)集中物料編碼為221000 994、221003 794、221003483的3組數(shù)據(jù)作為實(shí)驗(yàn)的數(shù)據(jù)集，數(shù)據(jù)集分別包含856526、308880、157360個(gè)事務(wù)，均有35個(gè)屬性。實(shí)驗(yàn)環(huán)境為Intel(R) Xeon(R) CPU E5649@2.53 GHz，操作系統(tǒng)為3.10.0-514.26.2.el7.x86_64，4臺(tái)24G內(nèi)存計(jì)算機(jī)，通過(guò)JAVA調(diào)用Spark并連接HIVE進(jìn)行實(shí)現(xiàn)。結(jié)果見(jiàn)表3。

表3 FP-Tree構(gòu)造時(shí)間

實(shí)驗(yàn)2。不同數(shù)據(jù)量級(jí)的數(shù)據(jù)集FP樹(shù)構(gòu)造時(shí)間對(duì)比。取輪胎質(zhì)量分析數(shù)據(jù)集中的百萬(wàn)、十萬(wàn)和萬(wàn)級(jí)別的數(shù)據(jù)集，實(shí)驗(yàn)環(huán)境同實(shí)驗(yàn)1。結(jié)果見(jiàn)表4。

表4 FP-Tree構(gòu)造時(shí)間

實(shí)驗(yàn)3。優(yōu)化后的FP-Growth算法與改進(jìn)的BICA算法(一種ADTree算法)對(duì)比。取輪胎質(zhì)量分析數(shù)據(jù)集中的百萬(wàn)、十萬(wàn)和萬(wàn)級(jí)別的數(shù)據(jù)集，實(shí)驗(yàn)環(huán)境同實(shí)驗(yàn)1。結(jié)果見(jiàn)表5。

表5 改進(jìn)的FP-Growth與改進(jìn)的BICA對(duì)比

通過(guò)實(shí)驗(yàn)1的3組實(shí)驗(yàn)可以明顯看出，使用優(yōu)化后的FP-Growth算法，F(xiàn)P樹(shù)的構(gòu)造效率有了明顯提升，平均提升效率為26%；實(shí)驗(yàn)2對(duì)比分析了不同數(shù)量級(jí)下的FP-Growth算法執(zhí)行情況，改進(jìn)后的算法平均效率提升也在20%以上，并且數(shù)據(jù)集的數(shù)量級(jí)越大，算法效率提升越快；實(shí)驗(yàn)3選取了輪胎質(zhì)量數(shù)據(jù)分析的另一個(gè)基于ADTree的優(yōu)化算法進(jìn)行比較，從實(shí)驗(yàn)結(jié)果可以看出，在算法執(zhí)行的時(shí)間方面，兩者的差距并不明顯，但使用ADtree算法進(jìn)行數(shù)據(jù)分析時(shí)，最終只能得到一個(gè)二分樹(shù)，利用該二分樹(shù)的每一個(gè)節(jié)點(diǎn)與分支進(jìn)行分析，才能得出輪胎質(zhì)量相關(guān)的一些結(jié)論，有時(shí)ADtree得出的二叉樹(shù)并不能包含全面結(jié)果，會(huì)遺漏部分屬性的影響；而FP-growth算法挖掘給出的是一條條關(guān)聯(lián)規(guī)則，只要給出確定的支持度與置信度，就能得到符合要求的全部規(guī)則，沒(méi)有遺漏；通過(guò)關(guān)聯(lián)規(guī)則，能夠更加直觀與清晰地看出屬性間的關(guān)聯(lián)關(guān)系，進(jìn)行進(jìn)一步的分析也更加方便。

3.2 FP-Growth關(guān)聯(lián)分析結(jié)果

通過(guò)FP-Growth算法得出的關(guān)聯(lián)規(guī)則能夠幫助我們進(jìn)行輪胎質(zhì)量異常數(shù)據(jù)的分析。以物料編碼為221003 794的數(shù)據(jù)集為例，該數(shù)據(jù)集的可用樣本數(shù)為308 880, 其中，質(zhì)檢合格數(shù)為306 471, 不合格數(shù)為2 409, 不合格率約0.78%。實(shí)驗(yàn)設(shè)置支持度為300，置信度為1.5%。根據(jù)FP-Growth算法的挖掘結(jié)果, 使用Hive數(shù)據(jù)庫(kù)對(duì)質(zhì)量數(shù)據(jù)進(jìn)行回查, 查詢挖掘出的關(guān)聯(lián)規(guī)則中的頻繁項(xiàng)對(duì)產(chǎn)品不合格率的影響。共挖掘出45個(gè)頻繁項(xiàng)集，24條關(guān)聯(lián)規(guī)則。因篇幅有限，僅給出部分結(jié)果進(jìn)行展示。FP-Growth算法挖掘得出的一些頻繁項(xiàng)集見(jiàn)表6。

表6 頻繁項(xiàng)集

以下是通過(guò)關(guān)聯(lián)規(guī)則進(jìn)一步分析的過(guò)程：

cur_BATCH_ID=20 161 206ZJS_ID=20 070 488 952==>hege=2 380

cur_BATCH_ID=20161206 1264 ==>hege=2 401

以上兩條規(guī)則說(shuō)明，批次是20 161 206產(chǎn)出的1264件產(chǎn)品中，不合格的有401件，占比約31.72%，遠(yuǎn)高于平均不合格率0.78%。這1 264件產(chǎn)品中，經(jīng)手成型主機(jī)手20 070 488的952件產(chǎn)品更是有380件不合格，不合格率為40%。剩余312件產(chǎn)品有21件不合格，不合格率約為6.73%，也遠(yuǎn)高于平均不合格率。由此得出結(jié)論：需要更加關(guān)注成型主機(jī)手20 070 488與批次20 161 206。

如該主機(jī)手與設(shè)備的關(guān)系：

POT_ID=314ZJS_ID=20070488 2582 ==>hege=2 412

POT_ID=36ZJS_ID=20070488 6151 ==>hege=2 394

以上兩條規(guī)則顯示，產(chǎn)品經(jīng)手成型主機(jī)手20 070 488，并且在POT_ID為314和36的硫化蒸鍋上生產(chǎn)時(shí)，不合格率分別約為15.96%與6.41%。

這兩臺(tái)硫化蒸鍋的平均不合格率也被算法挖掘出來(lái)：

POT_ID=314 11690 ==>hege=2 552

POT_ID=36 21570 ==>hege=2 463

POT_ID為314的硫化蒸鍋生產(chǎn)的產(chǎn)品，不合格率約4.72%，而POT_ID為36的硫化蒸鍋相應(yīng)的不合格率約2.15%，均比該型號(hào)產(chǎn)品的平均不合格率高。由于這兩個(gè)硫化蒸鍋生產(chǎn)的部分產(chǎn)品之前有經(jīng)過(guò)成型主機(jī)手20 070 488的操作，故排除后再做分析，POT_ID為314的硫化蒸鍋不合格率約1.54%，POT_ID為36的硫化蒸鍋不合格率約0.45%，甚至比平均不合格率還要低，故可以排除POT_ID為36的硫化蒸鍋的影響。

限于篇幅，此主機(jī)手與生產(chǎn)工藝參數(shù)相關(guān)的一些規(guī)則不再列出。由此可見(jiàn)，通過(guò)關(guān)聯(lián)規(guī)則，可以很方便地對(duì)輪胎質(zhì)量影響因素進(jìn)行嚴(yán)謹(jǐn)?shù)姆治?，從而做出合理的猜測(cè)與推論。

4 結(jié)語(yǔ)

針對(duì)現(xiàn)有頻繁模式增長(zhǎng)(FP-Growth)算法存在FP樹(shù)建樹(shù)性能較低的問(wèn)題，本文提出了一種改進(jìn)的FP-Growth算法，在原有的頻繁項(xiàng)頭表基礎(chǔ)上新增一個(gè)tail屬性，加速FP-Tree構(gòu)建。實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的FP-Growth算法能夠有效提高輪胎質(zhì)量異常數(shù)據(jù)的關(guān)聯(lián)分析效率，并且適用于大數(shù)據(jù)量的數(shù)據(jù)挖掘。通過(guò)關(guān)聯(lián)分析產(chǎn)生的頻繁項(xiàng)集分析，能夠找出影響輪胎質(zhì)量的生產(chǎn)制造過(guò)程重要因素，幫助企業(yè)改善工藝流程和精益生產(chǎn)，降低產(chǎn)品不良率，提升產(chǎn)品質(zhì)量。