趙京勝，張 鵬，孫宇航

（青島理工大學(xué) 通信與電子工程學(xué)院，山東 青島266033）

0 引 言

Apriori算法是一種反復(fù)迭代的算法，針對(duì)該算法的固有缺陷，Brin等人曾提出了DIP（dynamic itemset counting）改進(jìn)方法，利用動(dòng)態(tài)評(píng)估項(xiàng)集支持度來減少對(duì)數(shù)據(jù)庫掃描的次數(shù)；Park等人提出了基于散列桶計(jì)數(shù)的方法，提高了頻繁集的發(fā)現(xiàn)效率；Agrawal等提出了壓縮掃描事務(wù)項(xiàng)的方法，有效縮短了掃描無效事務(wù)項(xiàng)的時(shí)間［1］。這些改進(jìn)方法大多局限于數(shù)據(jù)結(jié)構(gòu)為樹的形式，很少涉及矩陣結(jié)構(gòu)的應(yīng)用。近幾年矩陣結(jié)構(gòu)作為Apriori算法改進(jìn)過程中的另一焦點(diǎn)，效果顯著。

針對(duì)聚類K－Means算法聚類過程中類內(nèi)和類間距離的研究，李永森等提出了距離代價(jià)函數(shù)，綜合了類內(nèi)和類間距離函數(shù)；張逸清等在算法的目標(biāo)函數(shù)中加入了一個(gè)新的數(shù)據(jù)項(xiàng)，用于衡量其它鄰近聚類中心與當(dāng)前聚類中心的距離平方和［2］。盡管目前對(duì)K－Means算法的改進(jìn)方案眾多，但缺少對(duì)初始聚類中心點(diǎn)選取方面的研究，而初始聚類中心點(diǎn)的選取很大程度上影響了后續(xù)聚類過程的效率。

本文基于數(shù)據(jù)挖掘算法的改進(jìn)和對(duì)傳統(tǒng)數(shù)據(jù)管理系統(tǒng)的功能拓展，以經(jīng)典Apriori算法和K－Means算法分析為基礎(chǔ)，證實(shí)了改進(jìn)算法的實(shí)際應(yīng)用效果，并以經(jīng)典信息管理技術(shù)為支撐，搭建了一套面向人口收入數(shù)據(jù)的數(shù)據(jù)挖掘管理系統(tǒng)，以提升數(shù)據(jù)管理能力和分析效率。

1 關(guān)聯(lián)Apriori算法的研究與改進(jìn)

1.1 關(guān)聯(lián)Apriori算法分析

設(shè)I＝ ｛i1，i2，…，im｝是一個(gè)項(xiàng)目集合，D 表示數(shù)據(jù)庫事務(wù)集，TI；A、B 為集合T 中的項(xiàng)集，關(guān)聯(lián)規(guī)則為：AB，其中AI、BI且A∩B＝。文獻(xiàn)［3］給出了支持度、置信度等相關(guān)的定義。

Apriori算法作為經(jīng)典關(guān)聯(lián)規(guī)則挖掘算法，其核心原理為：首先按照逐層搜索的迭代方式，通過Lk－1的自連接產(chǎn)生候選K－項(xiàng)集的集合，記作Ck，多次掃描數(shù)據(jù)庫后從Ck中尋找支持度不低于用戶設(shè)定的最小支持度閾值的項(xiàng)集；然后從頻繁項(xiàng)目集中構(gòu)造不低于用戶設(shè)定的最小置信度閾值的規(guī)則。算法能較準(zhǔn)確有效地生成頻繁項(xiàng)集，其主要缺點(diǎn)為［4，5］：

（1）候選集Ck的不斷產(chǎn)生使得連接項(xiàng)集越來越多，龐大的計(jì)算量延緩了算法運(yùn)行效率。

（2）多次掃描數(shù)據(jù)庫，冗余候選集增加了掃描次數(shù)，提高了對(duì)I／O 負(fù)載的要求。

1.2 關(guān)聯(lián)Apriori算法改進(jìn)

基于矩陣刪列的改進(jìn)型MA－Apriori算法，旨在解決原算法無效候選集的產(chǎn)生導(dǎo)致算法效率低下的問題。

（1）將數(shù)據(jù)庫映射為0－1矩陣［］m×n，表示為

其中，行m 代表I 中的項(xiàng)，列n 代表D 中的事務(wù)，若矩陣中的元素IiDj（i＜＝m，j＜＝n）＝0則表示事務(wù)庫D 中第j個(gè)事務(wù)不含I 項(xiàng)集合的第i項(xiàng)。

（2）由頻繁－1－項(xiàng)集產(chǎn)生候選項(xiàng)集2，設(shè)［IiD1］和［IiD2］（i＝1，2，……m）是L1中的兩個(gè)可連接項(xiàng)集，判斷［IiD1］［IiD2］的內(nèi)積值與最小支持計(jì)數(shù)的大小，若其值不低于最小支持計(jì)數(shù)，保留這對(duì)項(xiàng)集組合作為頻繁－2－項(xiàng)集L2的項(xiàng)集，否則，不予考慮作為L2的項(xiàng)集。其中，列［IiD1］與矩陣其它列做n－1次內(nèi)積，保證不產(chǎn)生重復(fù)內(nèi)積過程，除去列［IiD1］外，列［IiD2］與矩陣剩余列做n－2 次內(nèi)積，以此類推，直至矩陣中所有列均和其它不同列做過內(nèi)積運(yùn)算并保留內(nèi)積結(jié)果不低于最小支持計(jì)數(shù)的組合項(xiàng)集。最后，保留下來的組合項(xiàng)集生成為頻繁－2－項(xiàng)集。

由（K－1）－項(xiàng)集分裂后所得的（K－2）－項(xiàng)集中所包含的項(xiàng)在 （K－2）－項(xiàng)集的出現(xiàn)頻率必須滿足K－2次。當(dāng)候選集Ck（K≥4）中某項(xiàng)不滿足K－項(xiàng)集分裂后在上一級(jí)K－1－項(xiàng)集中的出現(xiàn)頻率K－1，那么，為減少后續(xù)矩陣計(jì)算的冗余度，刪掉當(dāng)前矩陣中事項(xiàng)出現(xiàn)頻率低于項(xiàng)目集所包括項(xiàng)個(gè)數(shù)的事物列。

（3）算法繼續(xù)到K－項(xiàng)集時(shí)，如果頻繁集Lk所包含的頻繁項(xiàng)目數(shù)小于K＋1，則算法中止，不必再進(jìn)行K＋1項(xiàng)目集的運(yùn)算。因?yàn)閷?duì)于K＋1 項(xiàng)目集，一定有K＋1 個(gè)K項(xiàng)目子集。

MA－Apriori算法的流程如圖1所示。

圖1 MA－Apriori算法流程

為驗(yàn)證算法的有效性，采用UIC 機(jī)構(gòu)提供的國外人口收入數(shù)據(jù)。原始數(shù)據(jù)共32561條記錄，以二維表形式存儲(chǔ)。每條記錄11個(gè)屬性：工作性質(zhì)、受教育程度、受教育時(shí)間、婚姻狀況、職業(yè)、家庭角色、人種、性別、工作時(shí)間、所處國家和薪資范疇，其中受教育時(shí)間和工作時(shí)間為數(shù)值型，剩余屬性均為字符串。

圖2 實(shí)例應(yīng)用效果對(duì)比

由算法運(yùn)行結(jié)果可知，改進(jìn)前后算法最終生成的關(guān)聯(lián)規(guī)則是一致的，包括以下規(guī)則：

薪資＞50K＝＝＞男性置信度1.0

薪資＜＝50K＝＝＞工作時(shí)間40小時(shí)置信度0.75

工作時(shí)間40小時(shí)＝＝＞薪資＜＝50K 置信度0.75

男性＝＝＞薪資＞50K 置信度0.6

1.3 Apriori算法和MA－Apriori算法的性能分析

Apriori算法在時(shí)間上的消耗主要是由連接產(chǎn)生的項(xiàng)目集個(gè)數(shù)和掃描上一頻繁項(xiàng)集中項(xiàng)集的次數(shù)所引起的。候選項(xiàng)集的產(chǎn)生是呈指數(shù)增長的，例如104個(gè)1－頻繁項(xiàng)目集可能產(chǎn)生項(xiàng)目集近107個(gè)的2－候選集［6］。

MA－Apriori算法基于矩陣形式，事務(wù)矩陣中0、1以位方式進(jìn)行存儲(chǔ)，減少了內(nèi)存占用，隨著計(jì)算次數(shù)的增加數(shù)據(jù)量逐漸減少，而且針對(duì)多維數(shù)據(jù)效果更加明顯。而列之間的與運(yùn)算等同于有效的剪枝，運(yùn)算本身所具有的計(jì)算特性簡化了候選集的產(chǎn)生過程，使得候選項(xiàng)集的數(shù)量相應(yīng)減少，由圖2可以看出候選集和頻繁集產(chǎn)生的階段性結(jié)果，其中，Apriori算法生成候選集3的項(xiàng)集并沒有成為頻繁集L3中的項(xiàng)集，可見這一步的計(jì)算無效，改進(jìn)后的MAApriori算法在生成頻繁集L2后立即停止運(yùn)行，避免了無效候選集產(chǎn)生。改進(jìn)后的MA－Apriori算法在時(shí)間和空間上都有了一定的優(yōu)化。

2 聚類K－Means算法的研究與改進(jìn)

2.1 聚類K－Means算法分析

聚類是在預(yù)先不知道分類數(shù)目的情況下，將數(shù)據(jù)集劃分成若干不同的類，使得類內(nèi)數(shù)據(jù)對(duì)象盡可能相似，類間盡可能相異。其中較為常用的一種基于距離的算法是KMeans算法［3，7］。

設(shè)X 為包含n 個(gè)對(duì)象的數(shù)據(jù)集合，那么X＝｛X1，X2，X3，……Xn｝，從X 中任意選取K 個(gè)對(duì)象作為初始聚類中心集合，記為Z，則Z＝｛Z1，Z2，Z3……Zk｝且滿足k≤n。通過K 個(gè)初始中心對(duì)數(shù)據(jù)集合X 進(jìn)行K 個(gè)劃分，每一個(gè)劃分代表一個(gè)簇，利用兩點(diǎn)間距離公式來計(jì)算初始聚類中心與數(shù)據(jù)集合X 對(duì)象間的距離，按計(jì)算結(jié)果將對(duì)象分配到距離最近的組。于是，數(shù)據(jù)集合X 經(jīng)劃分后得到K 個(gè)聚類簇記作C，C＝｛C1，C2，C3……Ck｝。不斷更新聚類中心點(diǎn)，直到聚類中心點(diǎn)不再發(fā)生改變，最終得到最優(yōu)的聚類中心點(diǎn)C’＝｛C1’，C2’，C3’……Ck’｝。

K－Means算法作為經(jīng)典的聚類算法，其明顯的不足是聚類沒有指明初始化均值的方法，常用的隨機(jī)選取聚類初始點(diǎn)存在不確定性。

2.2 聚類K－Means算法改進(jìn)

針對(duì)K－Means算法隨機(jī)選取對(duì)象作初始聚類中心的缺陷進(jìn)行改進(jìn)，提出一種基于確定初始聚類中心點(diǎn)的算法IM－K－Means，算法流程如圖3所示。

圖3 IM－K－Means算法流程

（1）設(shè)X＝｛X1，X2，X3，……Xn｝為包含n 個(gè)對(duì)象的數(shù)據(jù)集合，對(duì)X 中的數(shù)據(jù)進(jìn)行升序排序，從X 集合中依次取出｛X1，X2｝放入集合N1，｛X3，X4｝放入集合N2……直至X集合中的所有對(duì)象都被取出，則得到K 個(gè)存放原數(shù)據(jù)集中兩個(gè)對(duì)象的集合N ＝｛｛N1｝、｛N2｝……｛Nk｝｝。因無法保證X 集合中數(shù)據(jù)個(gè)數(shù)的奇偶性，因此，將n－2（k－1）對(duì)象放入到最后一個(gè)分組Nk。

K 個(gè)集合存放著數(shù)據(jù)集合X 中距離最近的兩個(gè)數(shù)據(jù)對(duì)象，這樣的分類很大程度上避免了隨機(jī)選取的不確定性，保證了K 個(gè)初始聚類中心在選取過程中數(shù)據(jù)空間均勻分布，避免了初始聚類中心存在集中取點(diǎn)的可能性。

（2）對(duì)集合N 中的每個(gè)集合求均值，所得結(jié)果記為Ci（i＝1，2，……k），Ci＝｛C1，C2，C3……Ck｝，刪去集合中重復(fù)的對(duì)象后即為初始聚類中心點(diǎn)，然后按照原算法計(jì)算中心點(diǎn)均值直至準(zhǔn)則函數(shù)收斂。

將IM－K－Means算法用于本文實(shí)例，使用32561 組樣本數(shù)據(jù)來驗(yàn)證兩種算法的聚類效果。圖中橫軸代表測(cè)試數(shù)據(jù)個(gè)數(shù)，縱軸代表工作時(shí)間值，算法對(duì)比結(jié)果如圖4和圖5所示。

圖4 K－Means應(yīng)用實(shí)例聚類效果

圖5 IM－K－Means應(yīng)用實(shí)例聚類效果

2.3 K－Means算法和IM－K－Means算法的性能分析

根據(jù)K－Means算法的執(zhí)行過程可知，通過對(duì)n 個(gè)對(duì)象到k 個(gè)聚類中心點(diǎn)的擇取過程需要k×n 次距離計(jì)算，而將樣本分配到最近的類中并不斷計(jì)算類中樣本平均值直至不再發(fā)生變化，經(jīng)歷t次迭代。所以，K－Means算法的時(shí)間復(fù)雜度至少為O（knt）。

IM－K－Means算法在原算法基礎(chǔ)上增加了對(duì)樣本排序的過程，采用性能較穩(wěn)定的堆排序，時(shí)間復(fù)雜度為O（nlog2n）。設(shè)樹深度為h，則n個(gè)結(jié)點(diǎn)的完全二叉樹深度為log2（h＋1），重建堆時(shí)結(jié)點(diǎn)比較次數(shù)：2［log2（n－1）＋log2（n－2）＋…log22］＜2nlog2n。盡管樣本排序增加了算法復(fù)雜度，但排序后的兩兩相鄰元素存放一組，類內(nèi)距離接近最小值，由此生成的初始聚類中心點(diǎn)與最終聚類中心點(diǎn)的確定過程縮短，歐式距離的計(jì)算次數(shù)為（n－2）×k，迭代次數(shù)一定小于t次。

對(duì)人口收入數(shù)據(jù)中的工作時(shí)間進(jìn)行測(cè)試，對(duì)比算法迭代次數(shù)的性能差異，測(cè)試結(jié)果如圖6所示。

圖6 算法迭代次數(shù)對(duì)比

3 基于數(shù)據(jù)挖掘改進(jìn)算法的人口收入管理系統(tǒng)

為提高數(shù)據(jù)管理系統(tǒng)的性能，搭建了基于數(shù)據(jù)挖掘算法的人口收入管理系統(tǒng)，將MA－Apriori算法和IM－KMeans算法作為數(shù)據(jù)挖掘技術(shù)平臺(tái)，采用JSP＋Tomcat6.0＋MySQL技術(shù)實(shí)現(xiàn)［8］。系統(tǒng)功能框架圖如圖7所示。

3.1 Ma－Apriori算法在系統(tǒng)中的實(shí)現(xiàn)

傳統(tǒng)管理系統(tǒng)增加數(shù)據(jù)挖掘的關(guān)聯(lián)規(guī)則分析，在提升系統(tǒng)算法效率的同時(shí)成為專家探究各屬性間關(guān)聯(lián)情況，獲取隱藏規(guī)律的有效手段［9］。

MA－Apriori算法的平臺(tái)化實(shí)現(xiàn)主要功能有：可手動(dòng)設(shè)置最小支持度和最小置信度，查看在不同支持度和置信度情況下所輸出的關(guān)聯(lián)規(guī)則情況；關(guān)聯(lián)規(guī)則表以Excel表輸出，便于專家書面分析研究。圖8 結(jié)果是以最小支持度為0.22，最小置信度0.8計(jì)算所得，共產(chǎn)生11條強(qiáng)關(guān)聯(lián)規(guī)則。

圖7 系統(tǒng)整體功能框架

圖8 關(guān)聯(lián)規(guī)則

由規(guī)則置信度對(duì)應(yīng)的相關(guān)聯(lián)屬性可知婚姻狀況對(duì)薪資的影響程度是非常強(qiáng)烈的，據(jù)雜志《今日美國》刊登的一篇關(guān)于美國未婚男女收入調(diào)查顯示，在美國366所中等規(guī)模城市中，年齡在22－30歲之間、單身無子女的女性平均年收入為27K，同年齡段的未婚男性平均年收入為24K；相對(duì)婚姻狀況，受教育程度對(duì)薪資的影響程度次之。據(jù)教育專家的一些看法，所受教育等級(jí)的不同是導(dǎo)致收入差異的根本原因，美國高中畢業(yè)后選擇上大學(xué)的女性幾乎達(dá)到3／4，相比之下，男性約為2／3，而且大學(xué)畢業(yè)后繼續(xù)深造的女性要比男性高出1.5倍，與規(guī)則分析相近。

3.2 IM－K－Means算法在系統(tǒng)中的實(shí)現(xiàn)

將IM－K－Means算法應(yīng)用在人口收入管理系統(tǒng)中，針對(duì)大量原始數(shù)據(jù)散亂無序的狀況，按屬性條件進(jìn)行聚類分析，實(shí)現(xiàn)對(duì)人口收入信息的高效整合與組織［10］。圖9、圖10以受教育時(shí)間為例對(duì)原始數(shù)據(jù)聚為兩類，設(shè)置受教育時(shí)間最大值為16.0，最小值為0.5進(jìn)行聚類。

圖9 第一類聚類結(jié)果

圖10 第二類聚類結(jié)果

第一類為受教育時(shí)間16—9 年，對(duì)應(yīng)受教育程度為Doctorate（博士）—HS－grad（高中），共有28308條數(shù)據(jù)。在基本信息管理中按薪資范疇＞50K 條件查詢，共有117條結(jié)果，而受教育程度在HS－grad（高中）之上的人數(shù)占84%，可以說明第一類聚類程度的集中性，類內(nèi)之間的相近。據(jù)美國聯(lián)邦調(diào)查局的一項(xiàng)報(bào)告表明，成人學(xué)歷水平的高低以收入差異作為主要體現(xiàn)方式之一，已獲取高中以上學(xué)歷的成人收入是未獲取高中文憑的四倍，獲取碩博學(xué)位的成人年均收入為79946 元，而持有學(xué)士學(xué)位者的年均收入為54689元。

第二類受教育程度為8—1年，對(duì)應(yīng)受教育程度為12th（初中）—Preschool（學(xué)前教育），主要覆蓋受教育程度不高的人群，共有4342條數(shù)據(jù)。同樣在基本信息管理中查找，該受教育程度所對(duì)應(yīng)薪資范疇＜＝50K 的人數(shù)占薪資范疇為＜＝50K 總?cè)藬?shù)的78%，聚類效果明顯，第二類與第一類對(duì)比收入水平存在顯著差異。據(jù)聯(lián)邦普查局調(diào)查報(bào)告表明，在美國沒有完成高中教育的人，年收入僅19915 元；具有學(xué)士或碩士學(xué)歷者，只有51.4%的人年薪少于50K美元［10，11］。

根據(jù)系統(tǒng)運(yùn)行結(jié)果和官方調(diào)查報(bào)告對(duì)比可知，MAApriori算法和IM－K－Means算法在系統(tǒng)中的實(shí)際應(yīng)用效果良好，提高了數(shù)據(jù)分析效率。

4 結(jié)束語

針對(duì)傳統(tǒng)數(shù)據(jù)管理系統(tǒng)的局限性，數(shù)據(jù)挖掘技術(shù)與應(yīng)用系統(tǒng)的結(jié)合是一個(gè)可供研究的方向。在算法改進(jìn)的過程中，針對(duì)Apriori算法在候選集產(chǎn)生過程中存在的不足，提出優(yōu)化有效候選集產(chǎn)生的MA－Apriori算法，改進(jìn)了數(shù)據(jù)集的存儲(chǔ)方式，增加了判斷條件，提高了頻繁項(xiàng)集生成的準(zhǔn)確性；針對(duì)K－Means算法初始聚類中心點(diǎn)隨機(jī)選取的不確定性，提出的IM－K－Means算法，調(diào)整了初始聚類中心點(diǎn)的選取方法，縮短了尋找最優(yōu)聚類中心點(diǎn)的時(shí)間，提高了算法效率。在系統(tǒng)實(shí)現(xiàn)方面，雖然系統(tǒng)運(yùn)行良好，但在系統(tǒng)搭建的過程中仍存在一些有待優(yōu)化、擴(kuò)展的地方，嵌入系統(tǒng)的聚類算法在實(shí)現(xiàn)聚類功能時(shí)，耗時(shí)過長，這也是在算法改進(jìn)階段未能注意到的問題，可以考慮運(yùn)用其它聚類思想對(duì)算法進(jìn)行進(jìn)一步的改進(jìn)。

［1］ZHANG Fengyun.Brief analysis of associative rule and Apriori algorithm ［J］.Computer Knowledge and Technology，2010，6 （22）：6268－6269 （in Chinese）.［張鳳云.淺析關(guān)聯(lián)規(guī)則及其Apriori算法 ［J］.電腦知識(shí)與技術(shù)，2010，6 （22）：6268－6269.］

［2］WU Suhui，CHENG Ying，ZHENG Yanning，et al.Survey on K－Means algorithm ［J］.New Technology of Library and Information Service，2011，205 （5）：28－30 （in Chinese）. ［吳夙慧，成穎，鄭彥寧，等.K－Means算法研究綜述 ［J］.現(xiàn)代圖書情報(bào)技術(shù)，2011，205 （5）：28－30.］

［3］Han Jiawei，Micheline Kamber，Jian Pei.DATA MINING concepts and techniques［M］.Beijing：China Machine PRESS，2012：50－496.

［4］Trnka，Andrej.Market basket analysis with data mining methods［C］／／Networking and Information Technology，2010：446－450.

［5］JI Xiyu，HAN Qiuming，LI Wei，et al.Data mining technology application examples［M］.Beijing：China Machine Press，2009：20－30（in Chinese）.［紀(jì)希禹，韓秋明，李微，等.數(shù)據(jù)挖掘應(yīng)用實(shí)例［M］.北京：機(jī)械工業(yè)出版社，2009：20－30.］

［6］WANG Xiaojun.Study of data mining based on Apriori algorithm ［C］／／Software Technology and Engineering.2nd International Conference on Knowledge Discovery and Data Mining，2010：400－403.

［7］Kalavathy R.KDD and data mining ［C］／／Information and Communication Technology in Electrical Sciences，2007：1105－1110.

［8］CHEN Jian.Design of college hospital management system based on JSP and MySQL ［J］.Computer and Information Technology，2011，19 （16）：48－49 （in Chinese）.［陳健.基于JSP和MySQL的高校校醫(yī)院管理管理系統(tǒng)的設(shè)計(jì) ［J］.電腦與信息技術(shù)，2011，19 （16）：48－49.］

［9］HUANG Min.The design and implementation of community census information management system ［D］.Xi’an：University of Electronic Science and Technology of China，2011：24－30（in Chinese）.［黃敏.社區(qū)人口普查信息管理系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn) ［D］.西安：電子科技大學(xué)，2011：24－30.］

［10］LIU Na.The application of data mining algorithm based on MapReduce to national census system ［D］.Beijing：Capital University of Economics and Business，2011：47－49 （in Chinese）.［劉娜.基于MapReduce的數(shù)據(jù)挖掘算法在全國人口系統(tǒng)中的應(yīng)用 ［D］.北京：首都經(jīng)濟(jì)貿(mào)易大學(xué)，2011：47－49.］

［11］USA Today.Women earn far less than men ［EB／OL］.http：／／news.sinovision.net／portal.php.