雙數(shù)組窮舉法挖掘醫(yī)藥銷售數(shù)據(jù)庫頻繁集

摘 要: 為了挖掘醫(yī)藥銷售數(shù)據(jù)庫頻繁集，采用雙數(shù)組窮舉算法DAEA。該算法主要使用兩個數(shù)組和窮舉算法，實現(xiàn)挖掘醫(yī)藥銷售數(shù)據(jù)庫的頻繁集功能。該算法的優(yōu)點是只需對醫(yī)藥銷售數(shù)據(jù)庫進行數(shù)據(jù)預(yù)處理就可以直接挖掘該數(shù)據(jù)庫的頻繁集，無需把醫(yī)藥銷售數(shù)據(jù)庫轉(zhuǎn)換成相應(yīng)的事務(wù)數(shù)據(jù)庫。根據(jù)DAEA算法，開發(fā)了醫(yī)藥銷售數(shù)據(jù)庫頻繁集挖掘系統(tǒng)，使用該系統(tǒng)挖掘醫(yī)藥銷售數(shù)據(jù)庫的頻繁集，挖掘的結(jié)果與實際相吻合，說明該算法是可行的和有效的。關(guān)鍵詞:數(shù)據(jù)挖掘; 關(guān)聯(lián)規(guī)則; 頻繁集; 雙數(shù)組; 窮舉法

中圖分類號:TN911-34; TP301.6 文獻標(biāo)識碼:A

文章編號:1004-373X(2010)18-0066-03

Mining of Frequent Itemsets of Medicine Sale Database Using Double

Array and Exhaust Algorithm

XUE Xiang-yang

(Weinan Vocational and Technical College，Weinan 714000， China)

Abstract: The double array and exhaust algorithm (DAEA) is adopted to mine frequent itemsets of medicine sale database. The function of mining medicine sale database frequent itemsets is accomplished by the algorithm which mainly uses two arrays and exhaust algorithm. The advantages of this algorithm is that the frequent itemsets of the medicine sale database can be directly mined only by the data preprocessing of the medicine sales database but there is no necessity to convert the relevant transaction database into the corresponding transaction database. The mining system of medicine sale database frequent itemsets was developed on the basis of DAEA. This system was successfully used to mine the frequent itemsets of medicine sales database. The results is identical with the actual one. The experimental results demonstrate that it is feasible and effective.Keywords: data mining; association rule; frequent itemset; double array; exhaust algorithm

收稿日期:2010-04-27

隨著數(shù)據(jù)庫技術(shù)的成熟和數(shù)據(jù)庫管理系統(tǒng)的廣泛應(yīng)用，人們己經(jīng)在商業(yè)、政府和科學(xué)等領(lǐng)域的數(shù)據(jù)庫內(nèi)積累了大量的歷史數(shù)據(jù)，激增的數(shù)據(jù)背后隱藏著許多重要的信息，然而過去由于缺乏挖掘數(shù)據(jù)背后隱藏知識的手段，導(dǎo)致了“數(shù)據(jù)豐富，但信息貧乏”的現(xiàn)象[1]，即所謂“數(shù)據(jù)爆炸”。所謂數(shù)據(jù)挖掘，就是從大量、不完全、有噪聲、模糊、隨機的實際應(yīng)用數(shù)據(jù)中提取隱含在其中的、人們事先不知道的、但又是潛在有用的信息和知識的過程[2]。簡單地說，數(shù)據(jù)挖掘就是從大量的數(shù)據(jù)中提取或者“挖掘”知識[3]。目前，數(shù)據(jù)挖掘的主要研究領(lǐng)域可分為分類、預(yù)測、聚類、關(guān)聯(lián)規(guī)則等方面。關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘研究的一個重要分支，它是數(shù)據(jù)挖掘眾多知識類型中最為典型的一種，有著極其重要的應(yīng)用價值。挖掘關(guān)聯(lián)規(guī)則過程可以分解為以下兩個子過程:首先找出存在于事務(wù)數(shù)據(jù)庫中的所有頻繁項集;其次利用頻繁項集生成關(guān)聯(lián)規(guī)則。從第一步可以看出是從事務(wù)數(shù)據(jù)庫中挖掘頻繁集的，也就是說挖掘頻繁集之前，必須把一般的數(shù)據(jù)庫轉(zhuǎn)換成事務(wù)數(shù)據(jù)庫。針對這個問題，提出一種挖掘頻繁集的新算法DAEA，利用該算法可以直接挖掘醫(yī)藥銷售數(shù)據(jù)庫的頻繁集，而無需把醫(yī)藥銷售數(shù)據(jù)庫轉(zhuǎn)換成事務(wù)數(shù)據(jù)庫。

1 關(guān)聯(lián)規(guī)則的相關(guān)定義

關(guān)聯(lián)規(guī)則的挖掘問題可以形式化描述為[4-5]:

定義1 項目(Item):交易數(shù)據(jù)庫中的一個屬性字段，每個字段有一定的取值范圍。對一超級市場，項目一般是指一次交易中的一個物品。

定義2 交易(Transaction):某個客戶在一次交易中發(fā)生的所有項目的集合。

定義3 項目集(Itemset):包含若干個項目的集合，簡稱項集。

定義4 k-項集:對于項集X，如果X中包含有k個項目，則X稱為k-項集。例如:項集X={a，b}就是一個2-項集。

定義5 支持數(shù):k-項集的出現(xiàn)次數(shù)簡稱為k-項集的支持數(shù)，簡記為count。

定義6 最小支持數(shù)(minimum support):由用戶定義衡量支持數(shù)的一個閾值，表示項目集在統(tǒng)計意義上的最低重要性，記作minsup。

定義7 頻繁項目集:如果k-項集支持數(shù)滿足預(yù)定義的最小支持數(shù)，則k-項集是頻繁項集。若某一項目m滿足最小支持數(shù)的要求，則稱m為頻繁項目，所有頻繁項目的集合稱為頻繁1-項集，記為L1滿足最小支持數(shù)要求的k-項集稱為頻繁k-項集，所有頻繁k-項集的集合記為Lk。

挖掘關(guān)聯(lián)規(guī)則的步驟大體可以分成以下兩步[6]:首先找出所有的頻繁項集;其次在找出頻繁項集的基礎(chǔ)上產(chǎn)生強關(guān)聯(lián)規(guī)則。關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘首先由Agrawal，Imiehski和Swami提出，經(jīng)典的關(guān)聯(lián)規(guī)則發(fā)現(xiàn)方法即Apriori算法[7]由Agrawal和Srikant提出，其產(chǎn)生頻繁項集的基本思想由連接和剪枝[8-10]兩個步驟完成。本文提出產(chǎn)生頻繁集的算法也分兩個步驟:首先統(tǒng)計各項集的支持數(shù)，其次是根據(jù)設(shè)置的最小支持數(shù)產(chǎn)生頻繁集。

2 雙數(shù)組窮舉算法

本文提出的算法如下:

步驟1:定義2個數(shù)組;定義統(tǒng)計變量，并為其賦零值。

步驟2:打開數(shù)據(jù)庫表。統(tǒng)計1個顧客1天內(nèi)購買藥品的種類(該顧客購買的藥品種類由若干個記錄組成，1種藥品1條記錄)并把其藥品名稱賦給數(shù)組1的每一個元素。

步驟3:利用窮舉法判斷數(shù)組1各元素的取值，然后根據(jù)各元素的取值，把其值賦給數(shù)組2的相應(yīng)元素。(數(shù)組2第一元素放置銷售排名第一的藥品名稱，數(shù)組2的第二個元素放置銷售排名第二的藥品名稱，其余以此類推)。

步驟4:利用統(tǒng)計變量，統(tǒng)計各項集的支持數(shù)。

步驟5:給數(shù)組1和數(shù)組2的每一個元素賦空字符串。

步驟6:返回第2步，統(tǒng)計下一個顧客1天內(nèi)購買藥品的種類，如此循環(huán)直到數(shù)據(jù)庫掃描結(jié)束。

步驟7:當(dāng)數(shù)據(jù)庫掃描完成時，根據(jù)設(shè)置的最小支持數(shù)，輸出頻繁1-項集，頻繁2-項集，…，頻繁n-項集。

由于該算法用到兩個數(shù)組，并且在步驟3中運用窮舉法判斷數(shù)組1中各元素的取值，所以把該算法命名為雙數(shù)組窮舉算法(double array exhaust algorithm)。算法中兩個數(shù)組的大小由研究藥品種類的多少決定，這里不可能研究所有種類的藥品，而且顧客在購買時也不可能購買所有的藥品種類，其購買的藥品種類是有限的，所以要選擇有限的藥品種類來研究。例如，要挖掘6種藥品之間的頻繁集，數(shù)組的大小就定義為6，數(shù)組1和數(shù)組2就各有6個元素，在數(shù)組1中每個元素的取值就有6種可能，對每個元素就用這6種可能來判斷，然后，根據(jù)判斷的結(jié)果，把其值賦給數(shù)組2相應(yīng)的元素。這樣統(tǒng)計完一個顧客購買的藥品種類后，數(shù)組2的第一元素放置銷售排名第一的藥品名稱，數(shù)組2的第二個元素放置銷售排名第二的藥品名稱，以此類推。這樣數(shù)組2中各元素放置的藥品名稱就是有序的，有利于編程統(tǒng)計各項集的支持數(shù)。一個客戶統(tǒng)計完后，接著統(tǒng)計下一個顧客購買的藥品名稱，統(tǒng)計各項集的支持數(shù)，如此循環(huán)，直到數(shù)據(jù)庫掃描結(jié)束。

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

3.1 選擇要研究的藥品種類

鄭重聲明，選擇的數(shù)據(jù)庫來自陜西省渭南市某藥品批發(fā)公司2008年3月的銷售記錄數(shù)據(jù)庫。

由于藥品的種類很多，不可能挖掘所有藥品的頻繁集，只能有選擇地挖掘一小部分藥品種類之間的頻繁集。那么，挖掘哪些藥品之間的頻繁集意義比較大，顯然是銷售金額多的或是利潤比較大的藥品。本文選擇銷售金額排名前6名的藥品作為挖掘?qū)ο?，挖掘它們之間的頻繁集。對該數(shù)據(jù)庫匯總、按降序排序，得到銷售金額排名前6名的藥品是:醒脾開胃顆粒、阿莫西林膠囊、小5%糖、先鋒五號、菌必治和小鹽水。將這6中藥品作為研究對象，挖掘它們的頻繁集。

3.2 屬性子集的選擇

該藥品的銷售記錄數(shù)據(jù)庫共28個字段，即28個屬性。由于要研究的是顧客在購買藥品時所研究的6種藥品有那些同時出現(xiàn)，所以在這28個字段中，絕大部分字段是不需要的，要反映是哪個顧客購買的，肯定要有“單位編號”該字段，在該醫(yī)藥銷售數(shù)據(jù)庫中每個購買單位的編號是惟一的，同時也要有“商品名稱”和“日期”這兩個字段。這樣只保留了3個字段，其余25個字段刪除掉。

3.3 數(shù)據(jù)抽取

在2008年3月的陜西省渭南市某醫(yī)藥批發(fā)公司的銷售數(shù)據(jù)庫中，購買的1種藥品就是1條記錄，換句話說，顧客1次購買了n種藥品就有n條記錄。本文只研究6種藥品，其他藥品不在研究之列，因此把要研究的6種藥品的記錄抽取出來放在另外一個表中(該操作由SQL語句完成)。這樣抽取出來的記錄就組成一個只有要研究的6種藥品的新的、精簡的藥品銷售數(shù)據(jù)庫表。經(jīng)過以上步驟，轉(zhuǎn)換好的數(shù)據(jù)庫表如表1所示。

原表總的記錄個數(shù)為15 531，經(jīng)過數(shù)據(jù)抽取后，減少記錄個數(shù)14 662，新表的記錄個數(shù)剩下869個，這樣在挖掘頻繁集的時候，就能大大減少掃描新數(shù)據(jù)庫的次數(shù)，對提高挖掘頻繁集的效率幫助很大。

表1 數(shù)據(jù)抽取后的表

單位編號商品名稱日期

XS450菌必治/頭孢曲松鈉針2008-03-11

XS450阿莫西林膠囊2008-03-11

XS666小鹽水2008-03-11

XS666小5%糖2008-03-11

XS666阿莫西林膠囊2008-03-11

XS922阿莫西林膠囊2008-03-11

XS922菌必治/頭孢曲松鈉針2008-03-11

XS519菌必治/頭孢曲松鈉針2008-03-11

XS699小鹽水2008-03-11

XS699小5%糖2008-03-11



4 算法性能試驗

根據(jù)提出的算法，利用Visual Basic 6.0及SQL語言開發(fā)了一個醫(yī)藥銷售數(shù)據(jù)庫頻繁集挖掘系統(tǒng)。運行該系統(tǒng)，設(shè)置好最小支持數(shù)為9后，挖掘出的最大頻繁集如圖1所示。

圖1 頻繁3-項集

5 結(jié) 語

用雙數(shù)組窮舉算法挖掘頻繁集的結(jié)果與設(shè)置的最小支持數(shù)有關(guān)，但前提是要先統(tǒng)計出各項集的支持數(shù)。經(jīng)驗證，用雙數(shù)組窮舉算法統(tǒng)計出來的支持數(shù)與實際情況相吻合。因此，該算法是可行的、有效的。

參考文獻

[1]羅可，蔡碧野.數(shù)據(jù)挖掘及其發(fā)展研究[J].計算機工程與應(yīng)用，2002(14):182-184，232.

[2]邵峰晶，于忠清.數(shù)據(jù)挖掘原理與算法[M].北京:中國水利水電出版社，2003.

[3]HAN Jia-wei， KAMBER Micheline. 數(shù)據(jù)挖掘:概念與技術(shù)[M].范明，孟小峰，譯.2版.北京:機械工業(yè)出版社，2008.

[4]AGRAWA Rakesh， IMIELINSKI Tomass，SWAMI Arun. Mining association rules between sets of items in large database[M]//Proc. of the ACM SIGMOD Conference on Management of Data. Washington，DC: ACM，1993:207-216.

[5]AGRAWAL Rakesh， SRIKANT Ramakrishnan. Fast algorithms for mining association rules[M]. IBM: San Jose，CA: Almaden Research Center， 1995.

[6]王艷.數(shù)據(jù)挖掘中關(guān)聯(lián)規(guī)則算法的研究[D].成都:西南交通大學(xué)，2004.

[7]RYMON R. Search through systematic set enumeration[C]//Proceeding of Third International Conference on Principles of Knowledge Representation and Reasoning.[S.l.]: TICPKRR， 1992:539-550.

[8]Agarwal C C ，Yu P S. Online generation of association rules[C].Proceeding of the International Conference of Data Engineering. Orlando，F(xiàn)lorida: [s.n.]， 1998:402-411.

[9]侯兵.關(guān)聯(lián)規(guī)則挖掘算法研究[D].成都:西南交通大學(xué)，2006.