馬健董輝

(亳州職業(yè)技術(shù)學(xué)院信息工程系，安徽 亳州 236800)

基于改進(jìn)FP_Growth算法在中藥提取信息中研究*

馬健董輝

(亳州職業(yè)技術(shù)學(xué)院信息工程系，安徽 亳州 236800)

中藥提取在中藥生產(chǎn)中占有十分重要地位，企業(yè)在生產(chǎn)中藥過程中，生產(chǎn)過程數(shù)據(jù)和質(zhì)量數(shù)據(jù)存在一定的問題。數(shù)據(jù)挖掘技術(shù)的出現(xiàn)及利用k－means聚類算法和改進(jìn)的FP_Growth算法對(duì)中藥生產(chǎn)過程數(shù)據(jù)進(jìn)行分析，既能為企業(yè)提高生產(chǎn)效率，降低成本，又保證產(chǎn)品的質(zhì)量。因此對(duì)中藥提取信息數(shù)據(jù)挖掘不僅是有必要的，更具有實(shí)際意義。

數(shù)據(jù)挖掘;關(guān)聯(lián)規(guī)則;中藥提取;FP－Growth算法

前言

亳州是全國著名的藥材之鄉(xiāng)，全市中藥材種植面積約70萬畝，約占全國種植面積的十分之一。亳州擁有全國規(guī)模最大、設(shè)備最先進(jìn)的中藥材專業(yè)市場(chǎng)。但是在中藥生產(chǎn)企業(yè)中，中藥企業(yè)對(duì)中藥提取的生產(chǎn)過程還存在一些問題，企業(yè)在多年的生產(chǎn)過程中積累了大量的生產(chǎn)參數(shù)數(shù)據(jù)和產(chǎn)品質(zhì)量數(shù)據(jù)，但是這些數(shù)據(jù)一直沒有得到更好的利用，至今企業(yè)對(duì)生產(chǎn)和產(chǎn)品質(zhì)量等參數(shù)的確定還在憑借操作人員的經(jīng)驗(yàn)，缺乏科學(xué)的數(shù)據(jù)分析和指導(dǎo)，同時(shí)導(dǎo)致了產(chǎn)品質(zhì)量的波動(dòng)性。

數(shù)據(jù)挖掘技術(shù)旨在通過采用專業(yè)的數(shù)據(jù)挖掘算法進(jìn)行分析，快速的從大量原始數(shù)據(jù)中提取隱含在數(shù)據(jù)之下的，人們無法直接獲取的卻又能對(duì)企業(yè)的生產(chǎn)決策和經(jīng)營決策提供幫助的信息。關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘非常重要一種類型，F(xiàn)P－Growth算法是實(shí)現(xiàn)關(guān)聯(lián)規(guī)則挖掘經(jīng)典算法，本文在分析此算法的基礎(chǔ)上，提出FP－Growth算法改進(jìn)，并用這一算法對(duì)中藥提起信息進(jìn)行分析挖掘，希望為中藥生產(chǎn)企業(yè)的發(fā)展和中藥的發(fā)展提供一定幫助。

1.關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘

1.1 關(guān)聯(lián)規(guī)則挖掘

本文通過關(guān)聯(lián)規(guī)則技術(shù)，分析過程數(shù)據(jù)和結(jié)果數(shù)據(jù)，探尋提取和濃縮過程與結(jié)果之間究竟存在怎樣的關(guān)系，從而為企業(yè)的參數(shù)優(yōu)化提供技術(shù)支持。

數(shù)據(jù)挖掘是近30年來逐步發(fā)展起來的一個(gè)新的研究領(lǐng)域，是多學(xué)科和技術(shù)相結(jié)合的產(chǎn)物，被廣泛的應(yīng)用于制造業(yè)、零售業(yè)、財(cái)務(wù)金融和醫(yī)學(xué)研究等各個(gè)領(lǐng)域，為促進(jìn)社會(huì)各方面的發(fā)展發(fā)揮重要的作用。關(guān)聯(lián)規(guī)則挖掘作為數(shù)據(jù)挖掘的眾多知識(shí)類型中最為典型的一種，在中藥學(xué)領(lǐng)域有著廣泛的應(yīng)用。

關(guān)聯(lián)規(guī)則用于表示OLTP數(shù)據(jù)庫中諸多屬性 (項(xiàng)集)之間的關(guān)聯(lián)程度，是利用數(shù)據(jù)庫中的大量數(shù)據(jù)通過關(guān)聯(lián)算法尋找屬性間的相關(guān)性。關(guān)聯(lián)規(guī)則挖掘的問題描述如下:

設(shè)I= {i1，i2，i3，…，in}是數(shù)據(jù)項(xiàng)的集合，T={T1，T2，…，Tn}是一個(gè)事務(wù)數(shù)據(jù)庫，其中每個(gè)事務(wù)T是數(shù)據(jù)項(xiàng)集I的子集即T?I，每個(gè)事務(wù)T有一個(gè)標(biāo)識(shí)符TID與之相關(guān)。如果I的一個(gè)子集X滿足X?T，則稱事務(wù)T包含項(xiàng)目集X。一個(gè)關(guān)聯(lián)規(guī)則就是形如X?Y的蘊(yùn)涵式，X?I、Y?I、X∩Y=Φ。其意義在于一個(gè)事務(wù)中某些項(xiàng)的出現(xiàn)，可推導(dǎo)出另一些項(xiàng)在同一事務(wù)中也出現(xiàn)，此處，“?”稱為“關(guān)聯(lián)”操作，X稱為關(guān)聯(lián)規(guī)則的先決條件，Y稱為關(guān)聯(lián)規(guī)則的結(jié)果。例如:中藥信息提取中，提取過程為A，固含量為B，則可用關(guān)聯(lián)規(guī)則R表示為:R:A?B。支持度 (Support)和置信度 (Confidence)是關(guān)聯(lián)規(guī)則中重要的概念，式 (1)和式 (2):

在實(shí)際應(yīng)用中，支持度和置信度均較高的關(guān)聯(lián)才可作為有用的關(guān)聯(lián)規(guī)則，稱之為最小支持度閾值 (min_sup)和最小置信度閾值 (min_conf)，min_sup表示數(shù)據(jù)項(xiàng)在統(tǒng)計(jì)意義下的最低重要性，只有滿足min_sup的數(shù)據(jù)項(xiàng)集才在關(guān)聯(lián)規(guī)則中出現(xiàn)，稱之為頻繁項(xiàng)集;最小置信度則表示關(guān)聯(lián)規(guī)則的最低可靠度。滿足大于min_sup和min_conf的規(guī)則稱為強(qiáng)規(guī)則，關(guān)聯(lián)規(guī)則挖掘的任務(wù)就是發(fā)現(xiàn)所有頻繁項(xiàng)集，挖掘出事務(wù)數(shù)據(jù)庫D中所有的強(qiáng)規(guī)則。

1.2 FP－Growth算法改進(jìn)

FP－Growth算法是韓家瑋等人提出的基于FP－Tree增長樹的著名算法，該算法在不產(chǎn)生候選集的情況下，提供了良好的頻繁模式挖掘過程，性能比Apriori算法有所提高。但FP－Growth算法隨著遞歸調(diào)用的深入，產(chǎn)生的條件FP－Tree越來越多，特別是在有共享前綴的情況下，F(xiàn)P－Growth算法非常耗時(shí)，為了解決這一問題，本文提出對(duì)FP－Growth算法的改進(jìn)，命為FP－Growth*算法。

FP－Growth*算法的思想是:減少搜索共享前綴的時(shí)間達(dá)到減少生成FP－Tree的時(shí)間，以提高挖掘效率，即在存在共享前綴的條件下，遍歷節(jié)點(diǎn)的第一個(gè)子節(jié)點(diǎn)就發(fā)現(xiàn)共享前綴。其挖掘步驟如下:

(1)頻繁1－項(xiàng)集排序:掃描事務(wù)數(shù)據(jù)庫D一次，生成頻繁1－項(xiàng)集及每個(gè)頻繁項(xiàng)集的支持度，按支持度降序排序，結(jié)果為L;

(2)事務(wù)項(xiàng)重排序:按照頻繁項(xiàng)表L的次序?qū)κ聞?wù)數(shù)據(jù)庫項(xiàng)排序，生成事務(wù)數(shù)據(jù)庫D1;

(3)事務(wù)集再排序:按照L的次序?qū)1的整個(gè)數(shù)據(jù)集再排序，即先對(duì)事務(wù)集的首列按L的次序排序，之后在此基礎(chǔ)上對(duì)事務(wù)集的次列再按L的次序排序，依次類推到數(shù)據(jù)集的終列得到排序數(shù)據(jù)集D2;

(4)構(gòu)造FP－Tree條件:創(chuàng)建以“null”為標(biāo)記的根節(jié)點(diǎn)，掃描D2，對(duì)其中每個(gè)事務(wù)調(diào)用insert_tree(P，T)過程，生成FP－Tree。

(5)挖掘FP－Tree:遞歸調(diào)用FP－Growth算法，挖掘FP－Tree，得到頻繁項(xiàng)集。

1.3 FP－Growth*算法實(shí)驗(yàn)分析

在相同的計(jì)算機(jī)軟硬件系統(tǒng)中，隨著數(shù)據(jù)集數(shù)目的增加，改進(jìn)后的算法生成FP－Tree時(shí)間明顯的減少，效率較高。根據(jù)實(shí)驗(yàn)分析，當(dāng)數(shù)據(jù)集數(shù)目較大時(shí)，采用FP－Growth*算法挖掘效率提高20%左右，如圖1所示:

圖1 FP－Growth*與FP－Growth算法生成FP－tree比較

2.用k－means算法對(duì)中藥信息提取

2.1 K－means算法

K－means算法是很典型的基于距離的聚類算法，采用距離作為相似性的評(píng)價(jià)指標(biāo)，即認(rèn)為兩個(gè)對(duì)象的距離越近，其相似度就越大。該算法認(rèn)為簇是由距離靠近的對(duì)象組成的，因此把得到緊湊且獨(dú)立的簇作為最終目標(biāo)。［2］

該算法第一步中是隨機(jī)的選取任意k個(gè)對(duì)象作為初始聚類的中心，初始地代表一個(gè)簇。該算法在每次迭代中對(duì)數(shù)據(jù)集中剩余的每個(gè)對(duì)象，根據(jù)其與各個(gè)簇中心的距離將每個(gè)對(duì)象重新賦給最近的簇。當(dāng)考察完所有數(shù)據(jù)對(duì)象后，一次迭代運(yùn)算完成，新的聚類中心被計(jì)算出來。如果在一次迭代前后，J的值沒有發(fā)生變化，說明算法已經(jīng)收斂。［2］

算法過程如下:

(1)從N個(gè)文檔隨機(jī)選取K個(gè)文檔作為質(zhì)心

(2)對(duì)剩余的每個(gè)文檔測(cè)量其到每個(gè)質(zhì)心的距離，并把它歸到最近的質(zhì)心的類

(3)重新計(jì)算已經(jīng)得到的各個(gè)類的質(zhì)心

(4)迭代2～3步直至新的質(zhì)心與原質(zhì)心相等或小于指定閥值，算法結(jié)束

具體如下:

輸入:k，data［n］;

(1)選擇k個(gè)初始中心點(diǎn)，例如c［0］ =data［0］，…c［k－1］ =data［k－1］;

(2)對(duì)于data［0］，…，data［n］，分別與c［0］…c［n－1］比較，假定與c［i］差值最少，就標(biāo)記為i;

(3)對(duì)于所有標(biāo)記為i點(diǎn)，重新計(jì)算c［i］ ={所有標(biāo)記為i的data［j］之和}/標(biāo)記為i的個(gè)數(shù);

(4)重復(fù) (2)(3)，直到所有c［i］值的變化小于給定閾值。

2.2 采用k－means對(duì)數(shù)據(jù)進(jìn)行聚類

目前企業(yè)提取生產(chǎn)的檢測(cè)指標(biāo)如下:

表2.1 當(dāng)前降壓避風(fēng)片提取生產(chǎn)的檢測(cè)指標(biāo)

設(shè)置參數(shù)聚類數(shù)目范圍為2－4，系統(tǒng)運(yùn)行后得到聚類分析的結(jié)果如下:

表2.2 k－means聚類參數(shù)G值比較分析

根據(jù)表2.2所提供的中藥提取質(zhì)檢數(shù)據(jù)的七個(gè)屬性，采用k－means聚類的初始參數(shù)進(jìn)行優(yōu)劣比較，聚類數(shù)目的參數(shù)范圍2－4，選擇G值最小值對(duì)應(yīng)的參數(shù)作為k－means聚類算法的初始參數(shù)。通過計(jì)算，如要得到的聚類越精確，那么優(yōu)質(zhì)因子goodness Index值的劃分要小，所以根據(jù)最佳聚類數(shù)據(jù)把參數(shù)代入相應(yīng)的函數(shù)，就可以得到k－means聚類結(jié)果。

表2.3 質(zhì)量檢測(cè)數(shù)據(jù)k－means聚類結(jié)果

屬性名稱 分類 最小值 最大值 聚類中心 元素個(gè)數(shù) 所占比例水煮液相對(duì)密度 (g/ml)1 1.103 1.186 1.13 17 12.32%水煮液相對(duì)密度 (g/ml)2 1.041 1.057 1.051 30 21.74%水煮液相對(duì)密度 (g/ml)3 1.058 1.095 1.067 91 65.94%噴霧干燥水分 (%)1 3.36 5.06 4.423 25 18.12%噴霧干燥水分 (%)2 5.09 6.42 5.77 80 57.97%

上表以系統(tǒng)選擇的最佳初始參數(shù)為初始參數(shù)，本文采用k－means聚類算法對(duì)七個(gè)質(zhì)檢指標(biāo)進(jìn)行聚類，得到聚類結(jié)果，用戶根據(jù)這些結(jié)果來分析更符合生產(chǎn)工藝的質(zhì)檢要求，針對(duì)某區(qū)間參數(shù)數(shù)據(jù)量最多，可將此區(qū)間作為質(zhì)檢指標(biāo)的參考值來分析數(shù)據(jù)。

3.FP－Growth算法在中藥信息提取結(jié)果

3.1 整理數(shù)據(jù)

首先我們整理過程和結(jié)果數(shù)據(jù)，集成兩個(gè)數(shù)據(jù)文件，使之成為一個(gè)數(shù)據(jù)集。本文整理的方式采用將同種批號(hào)數(shù)據(jù)每個(gè)屬性取均值和方差代表該批數(shù)據(jù)的方式，各個(gè)屬性的均值和方差與固含量數(shù)據(jù)結(jié)合起來。下面是部分結(jié)合數(shù)據(jù)表:

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

我們通過數(shù)據(jù)離散化對(duì)目前關(guān)聯(lián)規(guī)則發(fā)現(xiàn)數(shù)據(jù)進(jìn)行處理，本文采用用戶自由擬定分組數(shù)目，對(duì)各個(gè)屬性進(jìn)行等寬度劃分的方式對(duì)數(shù)據(jù)進(jìn)行輸入。

表3.1 離散化連續(xù)數(shù)據(jù)區(qū)間與符號(hào)對(duì)應(yīng)關(guān)系

3.3 結(jié)果

本文根據(jù)改進(jìn)的FP－Growth*算法，在離散化的數(shù)據(jù)表中發(fā)現(xiàn)在所有滿足要求的頻繁項(xiàng)集中得到最大頻繁集。利用改進(jìn)的FP－Growth*算法發(fā)現(xiàn)的最大頻繁集中，在改進(jìn)算法中無需生成頻繁模式基和條件模式樹，而是把事務(wù)的所有節(jié)點(diǎn)數(shù)據(jù)項(xiàng)直接存入到以HT表中各節(jié)點(diǎn)為頭指針的相鄰的單鏈表組中，不像FP_Tree樹，需要在父子節(jié)點(diǎn)中有雙向指針，節(jié)省了一半的指針域，減小的空間消耗，避免了內(nèi)存壓力，同時(shí)也僅需掃描事務(wù)數(shù)據(jù)庫兩次，且這種存儲(chǔ)結(jié)構(gòu)本身就直接蘊(yùn)涵了全部頻繁項(xiàng)目集，通過遍歷操作，可以很容易的挖掘出所有的頻繁項(xiàng)模式，挖掘效率有了顯著的提高。使關(guān)聯(lián)規(guī)則的時(shí)間減少，提高系統(tǒng)運(yùn)行的速度。

表3.2 關(guān)聯(lián)規(guī)則結(jié)果

將符號(hào)對(duì)應(yīng)實(shí)際屬性區(qū)間得到下表:

表3.3 聯(lián)結(jié)果符號(hào)轉(zhuǎn)化成實(shí)際屬性結(jié)果

通過上表我們可以看出，比較提取過程與固含量的關(guān)系時(shí)，在生產(chǎn)的批次中進(jìn)液量方差和循環(huán)溫度方差均較小時(shí)，能夠得到很好的固含量結(jié)果;比較濃縮過程對(duì)固含量關(guān)系，所有批次中濃縮液溫度和方差適中的能夠得到很好的固含量結(jié)果。

4．總結(jié)

本文回顧了關(guān)聯(lián)規(guī)則挖掘知識(shí)，在分析FP－Growth關(guān)聯(lián)算法的基礎(chǔ)上提出改進(jìn)算法，并用之于中藥提取信息中數(shù)據(jù)挖掘，以求在中藥生產(chǎn)過程中提取科學(xué)的數(shù)據(jù)，這僅是本人把數(shù)據(jù)挖掘在應(yīng)用于中藥提取信息挖掘的初步探索，希望能為為廣大中藥生產(chǎn)企業(yè)提供參考。

［1］Jiawei Han，Micheline Kamber著，范明，孟小峰 譯.數(shù)據(jù)挖掘:概念與技術(shù) (第二版)［M］.北京:機(jī)械工業(yè)出版社，2007.

［2］張建輝，K－means聚類算法研究及應(yīng)用 ［D］.武漢理工大學(xué)碩士論文，2007.

［3］朱明.數(shù)據(jù)挖掘 (第二版)［M］.合肥:中國科技大學(xué)出版社，2008.

［4］Pang－Ning Tan，Michael Steinbach，Vipin Kumer著，范明，范宏建等譯.數(shù)據(jù)挖掘?qū)д?［M］.北京:人民郵電出版社，2007.

［5］叢丹，王俊普等.基于FP－tree的模式分解算法 ［J］.計(jì)算機(jī)工程，2005，31(16):77—79.

［6］李云，蔡俊杰，劉宗田．基于量化規(guī)則格的關(guān)聯(lián)規(guī)則漸進(jìn)更新 ［J］.計(jì)算機(jī)應(yīng)用研究，2007，24(5):27—30，34.

［7］譚建豪．?dāng)?shù)據(jù)挖掘技術(shù) ［M］.北京:水利水電出版，2009.

Research of traditional Chinese medicine data mining based on improved FP－Growth algorithm

MA Jian;DONG Hui
(Department of Information Engineering，Bozhou Vocational and Technical College，Bozhou 236800，China)

Chinese medicine extraction plays a very important role in the production of traditional Chinese medicine．There are some problems in the process data and quality data from enterprises’Chinese medicine production．The emergence of data mining techniques and the use of k－means clustering algorithm and improved FP－Growth algorithm to analyze the data of traditional Chinese medicine production process，both improved enterprises productivity and reduced costs，and as well as ensure product quality．Therefore，data mining of Chinese medicine extraction is necessary and practical．

Data mining;association rules;Chinese medicine extraction;FP－Growth algorithm

TP391.1

A

1671－7406(2011)09－0017－07

2011－06－17

馬 健 (1978—)，男，安徽亳州人，主要研究方向:數(shù)據(jù)挖掘。

(責(zé)任編輯 劉洪基)