馬高庭　蔣萬春　申艷光

摘要：針對肉雞生產過程中的安全問題，基于改良關聯(lián)規(guī)則挖掘算法（APTPPA）建立肉雞產品質量安全預警模型。該模型以肉雞養(yǎng)殖及屠宰過程中危害分析、關鍵控制點（HACCP）的異常數(shù)據為處理對象，采用模式指導樹并行頻繁項集挖掘算法（APTPPA），構造關聯(lián)路徑樹，找尋最大頻繁項集，提取預警關聯(lián)規(guī)則，挖掘影響肉雞產品安全的因素，通過試驗驗證預警模型的有效性。

關鍵詞：肉雞產品；質量安全；預警模型；關聯(lián)規(guī)則；APTPPA；HACCP

中圖分類號： TS207.7 文獻標志碼： A

文章編號：1002-1302（2015）03-0271-04

食品安全問題的頻繁發(fā)生，引起了眾多國家的高度重視[1]。發(fā)達國家早已開始研究構建一套廣泛有效的食品安全預警模型。畜禽產品在日常養(yǎng)殖、加工過程中面臨更多更復雜的安全風險，監(jiān)管難度很大。因此國內外學者較為關注對畜禽產品質量安全預警模型的探討和研究。我國肉雞產業(yè)發(fā)展迅速，但產品品質參差不齊。如不及時改善產品質量，提高預警能力，國內肉雞產業(yè)將難以抗衡外來企業(yè)[2]。

數(shù)據挖掘在食品安全領域的應用較少，而食品安全日常事務所產生的大量時序數(shù)據非常適合做數(shù)據分析，從中可挖掘出有效的預警條目[3]。選擇合適、高效的挖掘算法對食品安全預警模型的精確度至關重要。本研究采用的關聯(lián)規(guī)則挖掘算法最早由Agrawal等提出[4]，其中以Apriori算法最為經典[5]，后續(xù)學者提出的改進算法大多以Apriori算法為基礎。由于Apriori算法存在固有缺陷，隨后Han等提出基于 FP-tree 來生成頻繁項目集的FP-growth算法[6]。近些年其他類型的關聯(lián)規(guī)則挖掘算法也相繼問世[7，8]，明顯進步于早期算法，但在食品安全領域的適用性并不理想。肉雞養(yǎng)殖、屠宰的安全因素具有多值性、傾斜性、稠密性和負相關性等特點，使傳統(tǒng)挖掘算法構建預警模型變得尤為困難。本研究針對食品安全因素的固有問題，結合HACCP管理體系，采用Association Path Tree Pattern Parallel Algorithm（APTPPA）算法構建了肉雞產品質量安全預警模型。

1 肉雞產品質量安全預警模型框架

本研究的預警模型是肉雞產品質量控制與可追溯系統(tǒng)中的一個模塊。該系統(tǒng)基于B/S架構，囊括肉雞產品安全信息的監(jiān)測、分析和追溯，能夠挖掘溯源數(shù)據庫中的異常數(shù)據，比對專家和歷史數(shù)據庫，生成有效的預警信息，并及時發(fā)出警報。肉雞產品質量安全預警模型包括信息源、比對源、挖掘分析以及預警反饋4個模塊。預警模型框架見圖1。

信息源模塊是預警模型數(shù)據的來源，以肉雞溯源系統(tǒng)在肉雞養(yǎng)殖、生產環(huán)節(jié)所收集的數(shù)據為基礎，遵循HACCP體系，選取關鍵控制點中的記錄進行預警挖掘。

比對源模塊是專家數(shù)據和歷史挖掘數(shù)據的數(shù)據源，在進行規(guī)則挖掘分析時，通常要與專家數(shù)據、歷史數(shù)據對比，再得出挖掘規(guī)則。

挖掘分析模塊是預警模型的核心，接收來自信息源的原始數(shù)據，經過對異常數(shù)據的分析，采用合適的關聯(lián)規(guī)則挖掘算法，得出具有參考價值的規(guī)則，供下一個模塊使用。

預警反饋模塊是外部獲得信息的窗口。當預警信息歸類為緊急信息時，系統(tǒng)自動通知相關人員，即刻采取措施，避免造成食品安全事件和大規(guī)模損失。該模塊還可供管理人員自主查詢預警信息，從而提高預防能力，保證肉雞產品質量，提高企業(yè)的行業(yè)競爭力。

2 肉雞產品質量安全預警模型處理流程

肉雞產品質量安全預警模型處理流程主要分為數(shù)據預處理、建立預警模型、挖掘結果檢驗3步[3]。預警模型詳細處理流程如下：

（1）進行數(shù)據預處理，并設置算法的支持度、置信度閾值。

（2）利用關聯(lián)規(guī)則挖掘算法搜索頻繁項集。

（3）對已找到的頻繁項集進行剪枝操作。

（4）判斷是否完成頻繁項集的搜索，若是則進入下一步，否則返回（2）。

（5）根據找尋到的頻繁項集生成關聯(lián)規(guī)則，并在通過規(guī)則檢驗后更新預警數(shù)據庫。

數(shù)據預處理主要是對異常數(shù)據進行邏輯轉換和分類操作。邏輯轉換針對監(jiān)測數(shù)據為連續(xù)值的情況，連續(xù)值數(shù)據無法進行關聯(lián)規(guī)則挖掘，因此要事先轉換成邏輯值。分類是保證預警模型預警等級準確的前提，不同分類的異常數(shù)據后續(xù)處理方式也不同。根據提取食品安全預警事件特征的方法，可將異常數(shù)據分為常規(guī)異常和超限異常。

超限異常是指對于各項指標集合，具有影響食品安全狀況的評價結果，它是最容易導致食品安全問題的因素[9]。

常規(guī)異常包括不規(guī)范異常、分布異常、趨勢異常。

（1）不規(guī)范異常。是指數(shù)據未按標準方式獲得，具有不可信性，報警等級較低。

建立預警模型就是把預處理后的異常數(shù)據采用APTPPA算法進行數(shù)據挖掘，找到頻繁項集，抽取關聯(lián)規(guī)則的過程。

挖掘結果檢驗即把新生成的預警規(guī)則與原有規(guī)則庫進行對比，并分析實際預警效果。如果原有庫中不存在該條規(guī)則，并且印證規(guī)則具有實際預警效果時，則將該規(guī)則更新到現(xiàn)有規(guī)則庫中。

3 基于APTPPA算法的肉雞產品質量安全預警模型

經典的Apriori算法在執(zhí)行過程中會產生大量中間項集，必須多次掃描數(shù)據庫，需要很多輔助空間結構，且要求數(shù)據為二值邏輯。本研究采用的APTPPA算法在壓縮數(shù)據的同時保證了原始數(shù)據集的基本形態(tài)，使其在多值數(shù)據、傾斜數(shù)據和負關聯(lián)規(guī)則的挖掘中比其他同類算法更加有效。APTPPA算法主要包括關聯(lián)路徑樹生成、頻繁項集挖掘和尋找最大頻繁項集3個步驟[3，10]。

3.1 關聯(lián)路徑樹生成

3.1.1 關聯(lián)路徑樹的基本思想

將事務數(shù)據庫D中每個數(shù)據項im均進行邏輯化處理會導致項數(shù)大量增加，造成維災難。為了減少項數(shù)，將項值進行標號化處理，每類項值都用標號vn表示。將標號化結果構造成樹形結構就是關聯(lián)路徑樹。以1 000組15項肉雞超限異常數(shù)據為例，標號化的數(shù)據集D如表3所示。endprint

數(shù)據集D進行邏輯化、標號化處理后，各項的值域顯著減小，內部存在較多相同的事務數(shù)據。此時為數(shù)據集D增加count屬性，對相同的事務數(shù)據進行統(tǒng)一計數(shù)，刪除冗余，得到無重復數(shù)據的數(shù)據集D′。由于沒有冗余事務，每條事務Ti包含項集的一種取值構成最大項集，其支持度計數(shù)就是事務計數(shù)counti的值。

3.1.2 構建基于樹的路徑表

數(shù)據集D′中的每個事務都是項值的組合，D′中所有事務可構成1棵關聯(lián)路徑樹，每個事務都是1條分支（圖2）。

3.2 頻繁項目集挖掘

3.2.1 按模式指導求頻繁項集

根據Apriori性質，可利用模式指導在關聯(lián)路徑樹之上找尋出頻繁項集。所謂模式即形如“xxooxxxxo”的某種排列組合，將事務中“x”位處項值忽略，而把“o”位處項值相同的事務計數(shù)并求和，就是該模式下的頻繁項集及其計數(shù)。對于非傾斜數(shù)據，在“o”增加的同時，此模式下的事務計數(shù)會銳減，從而有效收斂。對于傾斜數(shù)據，事務計數(shù)原本大于支持度閾值，模式計數(shù)退化。此時為了保證算法的快速收斂，將包含全部項的頻繁項集計數(shù)置零，再進行模式計數(shù)。還可通過設定最小支持度閾值對項集組合進行直接的剪枝操作。以1 000組15項肉雞超限異常數(shù)據為例，找到的頻繁項集如表5所示。

3.2.2 并行遞歸求頻繁項集

m個項有m個1-“o”模式（k-“o”模式指包含頻繁k項集的模式）的初始項集。并行遞歸就是在關聯(lián)路徑樹上以1-“o”模式為起始條件遞歸生成其他模式的方法。單CPU時，所有模式按1-“o”模式的生成過程逐個遞歸完成。多CPU時，每個CPU分配1個1-“o”模式，顯著提高遞歸速度。當事務計數(shù)小于遞歸閾值時，遞歸終止，算法收斂有效。

3.3 尋找最大頻繁項集

為了使挖掘結果更有意義，有必要在挖掘過程中剔除相似關聯(lián)規(guī)則， 防止重復規(guī)則出現(xiàn)。尋找最大頻繁項集是剔除相似關聯(lián)規(guī)則的一條途徑。對于APTPPA算法而言，在模式指導樹上取路徑a與其他任意路徑b進行比較，當a的“o”位包含于b中時，把b賦值給a，重復上述過程，直到不能發(fā)現(xiàn)路徑b為止。以1 000組15項肉雞超限異常數(shù)據為例，挖掘出的最大頻繁項集如表6所示。

4 試驗與分析

抽取河北某食品公司肉雞產品溯源數(shù)據庫中的1 000組15項歷史超限異常數(shù)據，在Windows 7操作系統(tǒng)下，采用Java編程語言，通過Eclipse集成平臺，驗證預警模型的有效性。將采用APTPPA與Apriori算法的肉雞預警模型進行對比試驗，驗證APTPPA算法在食品安全預警領域的應用具有高效性。

4.1 基于APTPPA算法的挖掘結果及分析

試驗參數(shù)設置如下：最小支持度=0.3，最小置信度=08，最大標號數(shù)=4，最大規(guī)則數(shù)=500。試驗后從中選取3條報警記錄如表7所示。

將上述最大關聯(lián)規(guī)則與歷史超限異常數(shù)據進行檢驗，匹配度達80%以上，超標報警也較為準確，體現(xiàn)了本研究預警模型的有效性。由以上最大關聯(lián)規(guī)則可分析出肉雞養(yǎng)殖、屠宰加工過程中的安全隱患因素，主要有：肉雞養(yǎng)殖環(huán)境中氨氣水平、可吸入顆粒物同時超標，需要對棟舍進行清理；養(yǎng)殖用水中氯化物、硝酸鹽同時超標，需要對水質進行改良；屠宰車間中氧氣濃度、氨氣水平同時超標，需要對屠宰車床進行消毒。

4.2 APTPPA與Apriori算法挖掘效率的分析

為了驗證2種挖掘算法的預警效率，采用上述1 000組15項超限異常數(shù)據分別測試APTPPA和Apriori算法預警挖掘的速度和精度并進行比較，在相同參數(shù)設置下，比較結果如表8所示。

由表8可知，在相同的規(guī)則覆蓋率下，APTPPA算法產生的規(guī)則更少，速度更快，效率更高。Apriori算法沒有結合食品安全預警信息的特點，產生較多冗余和不符合實際情況的規(guī)則。綜上所述，在肉雞產品安全預警時，基于APTPPA算法的肉雞產品質量安全預警模型比傳統(tǒng)Apriori算法預警模型更加有效。

5 總結與展望

基于關聯(lián)規(guī)則的肉雞產品質量安全預警模型采用了APTPPA算法，該算法能夠在海量復雜多變的影響因素中，挖掘出導致肉雞產品質量安全問題的要素，及時發(fā)現(xiàn)肉雞養(yǎng)殖、屠宰、加工過程中的安全隱患并預警，在實時監(jiān)控的同時有效減少和消除食品安全事故。但本研究的預警模型尚有不足，仍需進一步改進，主要體現(xiàn)在以下幾方面：關鍵控制點囊括的異常因素不夠全面；異常因素之間沒有主次之分；邏輯值分類轉換過程中沒有用到較為準確的分類算法等。

參考文獻：

[1]李 倩，張圣忠，王 芳.基于博弈分析的食品安全風險監(jiān)管策略研究[J]. 江蘇農業(yè)科學，2013，41（9）：268-270.

[2]趙金石. 我國肉雞質量追溯系統(tǒng)應用現(xiàn)狀分析[J]. 中國畜牧雜志，2011，47（8）：45-48.

[3]顧小林，張大為，張 可，等. 基于關聯(lián)規(guī)則挖掘的食品安全信息預警模型[J]. 軟科學，2011，25（11）：136-141.

[4]Agarwa R，Imielinski T，Swmai A. Mining association rules between sets to items in large databases[C]. Porceedings of ACM SIGMOD Intl Conf Management of Data，Washington DC，1993：207-216.

[5]Agrawal R，Srikant R. Fast algorithms for mining association rules in large databases[C]. 20th International Conference on Very Large Data Bases，1994：478-499.

[6]Han J，Pei J. Mining frequent patterns without candidate generation[C]. Porc 2000 ACM IGMOD Int Conf on Management of Data，SIGMOD2000，Dallas TX，2000：1-12.

[7]宋 威，楊炳儒，徐章艷，等. 基于索引數(shù)組與集合枚舉樹的最大頻繁項集挖掘算法[J]. 計算機科學，2007，34（7）：146-149.

[8]王黎明，張 卓. 基于iceberg概念格并置集成的閉頻繁項集挖掘算法[J]. 計算機研究與發(fā)展，2007，44（7）：1184-1190.

[9]翁道磊. 食品安全追溯系統(tǒng)的分析和研究[D]. 重慶：重慶大學，2008.

[10]張大為，黃 丹，嵇 敏，等. 利用模式指導樹的并行頻繁項集挖據方法[J]. 計算機工程與應用，2010，46（22）：147-150.endprint