圖像關聯規則挖掘研究

摘 要：介紹了圖像關聯規則的相關概念，描述了傳統的雙種群遺傳算法的執行過程；針對采用固定染色體交叉概率和染色體變異概率容易出現早熟、收斂速度較慢等問題，設計出了能自適應調整的染色體交叉算子和變異算子。最后將改進后的雙種群遺傳算法成功地運用到Landsat衛星遙感圖像，實現了圖像關聯規則的提取，為退耕還林決策提供了有力的依據。

關鍵詞：圖像數據挖掘； 圖像關聯規則； 自適應遺傳算法； 雙種群

中圖分類號：TP751文獻標志碼：A

文章編號：1001-3695(2009)06-2374-03

doi:10.3969/j.issn.1001-3695.2009.06.113

Research of image association rules mining

LEI Liang1，2， WANG Tong-qing1， YANG Bo2

(1.Key Laboratory of Optoelectronic Technology System Ministry of Education， Chongqing University， Chongqing 400044， China； 2. School of Electronic Information Engineering， Chongqing University of Science Technology， Chongqing 401311， China)

Abstract:

Firstly， this paper discussed definitions of image association rules and associated terms， described the process of the traditionaldoule population genetic algorithm. Secondly，proposed an new scheme that the double population genetic algorithm used the self-adaptable crossover operator and mutation operator according to the shortage of early convergence and stagnation in the traditional double population genetic algorithm based on unconvertible rate of crossover operator and mutation operator. Lastly， successfully applied the improved double populations genetic algorithm to mine the image association rules from Landsat satellite remote sensing images. It is useful for decreasing farmland to increase forest.

Key words：image data mining; image association rule; self-adaptable genetic algorithm; double populations

0 引言

隨著網絡技術的發展和計算機性能的提高，數碼相機、監視相機、衛星遙感系統的應用越來越廣泛，涌現出大量的圖像數據，對這些圖像進行自動分析以獲取大量有用知識的需求日益增加，圖像挖掘技術提供了有效的方法和技術。圖像挖掘(image mining，IM)是一種可以從大量的圖像集合中自動獲取隱含的圖像內容與模式的多學科交叉研究課題。其根本任務是從圖像底層像素特征描述中，高效地獲取高層圖像空間對象及其相互關系，以提取出圖像序列中隱含的、先前未知的、潛在有用的知識、圖像關系或其他隱含的圖像模式^[1]。它不是簡單地將數據挖掘技術引入到圖像理解領域，而是集中了數據挖掘、圖像處理、計算機視覺、圖像檢索、機器學習、模式識別數據庫和人工智能等技術，用于促進圖像內容的分析與理解。由于缺乏對IM的深刻理解及其本身存在一些理論和技術障礙，其研究進展緩慢。自2000年召開第一屆多媒體挖掘年會以來，IM尚未形成完整的理論框架和統一的技術方法，仍處于探索階段。另一方面，圖像技術的可行性帶來了圖像的爆炸性增長。許多關系數據庫也包含了多媒體信息，巨量多媒體數據的出現，必然要求檢索、分類和理解這些數據，而且，隨著擴展數據庫和對象—關系數據庫中多媒體對象的流行，人們自然希望能用相同的方法從大型數據庫中挖掘多媒體數據和關系數據的知識，生產用于從大型多媒體數據庫中發現知識的工具成為必然要求。

1 關聯規則的相關概念

關聯規則是數據挖掘的一個重要研究方向。挖掘關聯規則是指在數據庫（或圖像數據庫）

中挖掘出具有這種形式的規則：由于某些事件的發生而引起另外一些事件的發生。它在決策支持系統、專家系統和智能信息系統等各個方面起著重要的作用，并且隨著圖像數據庫應用的普及，圖像數據挖掘的應用越來越廣，在近幾年內備受人們的關注。例如，Kangkachit等人用BoSARM(business-oriented spatial association rule mining system)挖掘城市中實體間的位置關聯關系，得到了下面形式的關聯規則：有50%的建筑物既靠近海灘也靠近紀念品商店，在靠近海灘的建筑物中有80％同時靠近紀念品商店^[2]。該規則為房地產開發、旅游規劃設計、城市環境管理、城市建設規劃等部門提供了可靠的科學依據。有學者研究了圖形形狀之間的關聯關系，得到了大量形如“同時出現六邊形、正方形和圓，就一定會出現一個三角形，這個規則的發生概率是40％”的關聯規則，本規則可用于圖像的相似性檢索。

設I=｛i1，i2，…，im｝是m個不同項目的集合，即項目集，D為事務數據庫（或稱事務集），其中每個事務T是一個項目子集（TI）。如果事務T包含項目集X，表示為XT。

1）關聯規則 該規則是形如XY的邏輯蘊涵式。其中：XT，YT，并且X∩Y=。X稱做前提，Y稱做結果。有兩個因子與這條規則有關：可信度（confidence）和支持度（support）。

2）可信度 如果事務數據庫D里包含X的事務中有c%的事務同時也包含Y，那么稱關聯規則XY的置信度為c。簡單地說，可信度就是指在出現了項目集X的事務T中，項目集B也同時出現的概率有多大。

3）支持度 如果事務數據庫D中有s%的事務包含X∪Y，那么稱關聯規則XY的支持度為s。支持度描述了X和Y這兩個項目集的并集C在所有的事務中出現的概率有多大。

由于發現關聯規則的目的在于找出那些可信的并具有代表性的規則，要給定一個最小支持度閾值和一個最小可信度閾值。發現關聯規則的問題就是發現所有支持度和可信度均分別超過規定閾值的關聯規則。可信度是對關聯規則的準確度的衡量，支持度是對關聯規則重要性的衡量。因此挖掘關聯規則通常可以分兩步^[3]：

a)識別所有的頻繁項目集（frequent items，也稱做最大項目集large items），即支持度不低于用戶支持度的項目集；

b)從頻繁集中構造其信任度不低于用戶最低信任的規則。

其核心問題是發現最大項目集。發現最大項目集的過程其實就是全局的搜索過程。遺傳算法是一種全局優化算法，因此它避免了搜索過程中的局部最優。將遺傳算法用在規則的發現和提取方面能夠發現真正有用的規則。

2 改進的雙種群遺傳算法

標準遺傳算法是針對一個宏觀的種群進行選擇、交叉、變異三種操作，類似于人類進化過程，一群人隨著時間的推移而不斷進化，具備越來越多的優良品質。然而，由于他們的生長、演化、環境和原始祖先的局限性，經過相當長時間后，將逐漸進化到某些特征相對優勢的狀態。當一個種群進化到這種狀態，稱之為平衡態，這個種群的特性就不會再有很大的變化。雙種群遺傳算法是一種并行遺傳算法，它使用多種群同時進化，并交換種群之間優秀個體所攜帶的遺傳信息，以打破種群內的平衡態達到更高的平衡態，跳出局部最優。

傳統的雙種群遺傳算法在提取關聯規則時，首先建立兩個遺傳算法群體，即種群A和B，分別獨立地進行自然選擇、染色體交叉、染色體變異操作，且交叉概率、變異概率固定。當每一代運行結束以后，產生一個隨機數num，分別從A、B 中選出最優染色體和num個染色體進行雜交，以打破平衡態。但是，實驗證明^[4]，這種雙種群遺傳算法在關聯規則進行提取時，會存在如下不足：

a）兩個種群使用相同的交叉、變異算子，不利于保證兩個種群間的群體差異性。在染色體交叉重組和染色體變異時，兩個種群一般使用的是相同的交叉、變異算子。因此，需要對染色體交叉重組和染色體變異策略進行一定的改進，重新設計出一種新的染色體交叉重組和變異策略，以滿足遺傳算法中對于種群多樣性的需求。

b）隨機選取num個待交換個體，不利于保證各個種群內的物種多樣性。

c）自然選擇中采用傳統賭輪法，容易導致遺傳算法早熟。賭輪選擇在選擇中個體被選中的概率與其適應度占群體適應度總和的比例成正比。在初始化群體中，如果出現少數適應度較大的超級個體，在下一代中會得到較高的復制效率，容易在隨后進化的少數幾代內統治整個群體，同時進化開始時的選擇壓力過大也容易導致遺傳算法早熟。

針對以上不足，本文對自然選擇、染色體交叉、染色體變異和種群交叉算法進行了修改，使得交叉概率、變異概率能以種群平均適應度自適應地調整。

1）新的自然選擇改進

選擇只要適應度值大于“1”值的關聯規則，也就是只要滿足要求的規則都將保留下來。

2）新的染色體交叉概率、變異概率改進

采用自適應遺傳算法中交叉概率和變異概率能自適應調節的特點，將雙種群遺傳算法中交叉概率Pc和變異概率Pm按如下公式進行自適應調整^[5，6]：

Pc=Pc1－(Pc1－Pc2)(f′－favg)/（fmax－favg）f′≥favgPc1f′≤favg(1)

Pm=Pm1－(Pm1－Pm2)(fmax－f)/(fmax－favg)f≥favgPm1f≤favg(2)

其中：fmax代表群體中最大適應度；favg代表每代群體的平均適應度；f′代表要交叉的兩個個體中較大的適應度；f代表要變異個體的適應度；Pc1＝0.9，Pc2＝0.6，Pm1=0.1，Pm2=0.01。

這樣就相應地提高了群體中表現優良的個體的Pc和Pm，使得它們不會處于一種近乎停滯不前的狀態。因此，自適應的Pc和Pm能夠提供相對某個解的最佳Pc和Pm。改進后的染色體交叉算子和變異算子在保證群體多樣性的同時，保證遺傳算法的收斂性。

3）新的染色體變異種群交叉

將兩個種群中的最優解取出，每一代運行結束后，產生一個隨機數num，再在每個種群中隨機選取 num 個染色體，放入對方種群。

3 應用實例

本實例的圖像數據來源于文獻[7]提供的Landsat衛星ETM數據和地形高程數據(DEM)等遙感圖像數據。

遙感圖像不同于其他的數字圖像，圖像中包含了多個波段的信息。ETM 數據包含七個波段和一個全色波段，從中提取了地表植被覆蓋度和土地利用方式(本文主要利用耕地分布)類型，由DEM 提取坡度分布圖像。另外，應用USLE模型計算小流域土壤侵蝕量和侵蝕強度分布圖像。

對圖像進行預處理、特征提取后，得到人們關心的四個屬性特征數據：植被覆蓋度(coverage，C)、坡度(slope，S)、耕地分布(farm，F)和土壤侵蝕強度(eros，E)。這四個屬性特征數據的屬性值分布如表1所示。

通過挖掘這些強關聯規則，可以得到一些重要的、可用于決策的知識：

a）耕地一般導致強度侵蝕(規則4)，非耕地一般為輕度侵蝕(規則3)。

b）坡度在25°以下的地區大部分侵蝕強度較輕(規則5)。

c）植被覆蓋度在30%以上絕大部分(> 93.24 )不會產生強度侵蝕(規則1、2)。

d）非耕地只有在低植被覆蓋(<30%)和高坡度(>50°)的情況下才會與高侵蝕產生強關聯(規則20)。

e）耕地低侵蝕的必要條件為坡度<25° (規則14、17)。

f）低植被覆蓋區域一般產生強侵蝕，但如果坡度<25°，平均侵蝕強度將減弱(規則6、18、21)。

實驗證明，在傳統的雙種群遺傳算法求解關聯規則中，兩個種群使用相同的交叉、變異算子，不利于保證兩個種群間的群體差異性。而通過對染色體交叉重組和染色體變異策略進行一定的改進，重新設計出的一種新的染色體交叉重組和變異策略，能夠滿足遺傳算法中對于種群多樣性的需求。同時，這種改進后的染色體交叉算子和變異算子能夠在一定程度上保證種群內物種的多樣性，優化進化流程，從而加強算法的優化性能。

本文對改進后的雙種群遺傳算法與傳統雙種群遺傳算法的收斂性進行對比。表4 是用兩種方法分別運行500、1 000和2 000次的收斂次數。從表4可以看出，改進的雙種群遺傳算法能在較短的進化時間內自適應地調整個體的交叉率和變異率，使算法盡早跳出局部收斂，同時收斂總數比傳統算法高，收斂速度快。由此可見，這種改進的雙種群遺傳算法對于提高GA的收斂性和魯棒性是有效的，是一種有效的、穩定的、十分實用的算法。

4 結束語

大量的數字圖像為圖像挖掘技術提供豐富的研究內容的同時也提出了挑戰。目前，在國外IM已經初步應用于科學研究、醫學、生物、氣象和勘測等領域，國內也已開發出原型系統，圖像挖掘的研究與應用將向更廣闊的領域擴展。本文主要介紹了圖像關聯規則中涉及的相關概念，描述了傳統的雙種群遺傳算法實現關聯規則提取的過程，對傳統雙種群遺傳算法中存在的不足進行了改進，設計出了自適應調整的染色體交叉算子和變異算子，并成功應用于Landsat衛星ETM數據遙感圖像挖掘，提取出了植被覆蓋度、坡度、耕地分布和土壤侵蝕強度之間的關聯規則，對防治研究區內水土流失和生態環境建設提出了非常有用的決策依據。但是近年來的研究表明，在遺傳算法的實現中只考慮支持度和可信度兩個閾值是不夠的，并且還可能引起誤導；文獻[8]提出了增加興趣度這個閾值來度量關聯規則的關聯性。本文中所挖掘的關聯規則仍然只使用了可信度和支持度這兩個閾值，如何加入興趣度這個閾值來衡量本文的關聯規則也是今后要研究的問題。

參考文獻：

[1]ZHANG Ji， HSU W， LEE ML. Image mining: issues， frameworks and techniques[C]//Proc of the 2nd International Workshop on Multimedia Data Mining. 2001:13-20.

[2]孫慶先，方濤，郭達志.圖像數據挖掘中的關聯規則[J].計算機工程，2006，32(5):49-51.

[3]HAN Jia-wei， KAMBER M.數據挖掘概念與技術 [M]. 2版.范明，孟小峰，譯.北京:機械工業出版社，2007:151-154.

[4]曾凡超，朱征宇，鄧欣，等.車輛路徑問題的改進的雙種群遺傳算法[J].計算機工程與設計，2007，28(20):4998-5000.

[5]張玲，劉勇，何偉.自適應遺傳算法在車牌定位中的應用[J].計算機應用，2008，28(1):184-186.

[6]歐陽森，宋政湘，王建華，等. 一種快速收斂的遺傳算法[J].計算機應用研究， 2003，20(9):50-52.

[7]馬超飛，劉建強.遙感圖像多維量化關聯規則挖掘[J].遙感技術與應用，2003，18(4)：244-246．

[8]CHEN Guo-qing， WEI Qing. Fuzzy association rules and the exten-ded mining algorithms[J]. Information Sciences， 2002，147(1-4):201-228.