計算機科學剖析數據挖掘中的軟計算方法 推薦本站最優秀期刊：《計算機科學》由國家科技部主管，西南信息中心主辦，系“中文科技核心期刊”、“中國科技論文統計與分析用期刊”、“中國科學引文數據庫來源期刊”、“中國期刊方陣雙效期刊”。主要報導國內外計算機科學與技術的發展動態，涉及面廣的方法論與技術，和反映新苗頭、能起承先啟后作用的研究成果。內容涉及程序理論、計算機軟件、計算機網絡與信息、數據庫、人工智能、人機界面、國際會議、應用等。

　　摘 要 文章對數據挖掘中軟計算方法及應用作了綜述。對模糊邏輯、遺傳算法、神經網絡、粗集等軟計算方法，以及它們的混合算法的特點進行了分析，并對它們在數據挖掘中的應用進行了分類。

　　關鍵詞 計算機科學,數據挖掘,軟計算,模糊邏輯,遺傳算法,神經網絡,粗集

　　1 引言

　　在過去的數十年中，隨著計算機軟件和硬件的發展，我們產生和收集數據的能力已經迅速提高。許多領域的大量數據集中或分布的存儲在數據庫中[1][2]，這些領域包括商業、金融投資業、生產制造業、醫療衛生、科學研究，以及全球信息系統的萬維網。數據存儲量的增長速度是驚人的。大量的、未加工的數據很難直接產生效益。這些數據的真正價值在于從中找出有用的信息以供決策支持。在許多領域，數據分析都采用傳統的手工處理方法。一些分析軟件在統計技術的幫助下可將數據匯總，并生成報表。隨著數據量和多維數據的進一步增加，高達109的數據庫和103的多維數據庫已越來越普遍。沒有強有力的工具，理解它們已經遠遠超出了人的能力。所有這些顯示我們需要智能的數據分析工具，從大量的數據中發現有用的知識。數據挖掘技術應運而生。

　　數據挖掘就是指從數據庫中發現知識的過程。包括存儲和處理數據，選擇處理大量數據集的算法、解釋結果、使結果可視化。整個過程中支持人機交互的模式[3]。數據挖掘從許多交叉學科中得到發展，并有很好的前景。這些學科包括數據庫技術、機器學習、人工智能、模式識別、統計學、模糊推理、專家系統、數據可視化、空間數據分析和高性能計算等。數據挖掘綜合以上領域的理論、算法和方法，已成功應用在超市、金融、銀行[4]、生產企業[5]和電信，并有很好的表現。

　　軟計算是能夠處理現實環境中一種或多種復雜信息的方法集合。軟計算的指導原則是開發利用那些不精確性、不確定性和部分真實數據的容忍技術，以獲得易處理、魯棒性好、低求解成本和更好地與實際融合的性能。通常，軟計算試圖尋找對精確的或不精確表述問題的近似解[6]。它是創建計算智能系統的有效工具。軟計算包括模糊集、神經網絡、遺傳算法和粗集理論。

　　2 數據挖掘中的軟計算方法

　　目前，已有多種軟計算方法被應用于數據挖掘系統中，來處理一些具有挑戰性的問題。軟計算方法主要包括模糊邏輯、神經網絡、遺傳算法和粗糙集等。這些方法各具優勢，它們是互補的而非競爭的，與傳統的數據分析技術相比，它能使系統更加智能化，有更好的可理解性，且成本更低。下面主要對各種軟計算方法及其混合算法做系統性的闡述，并著重強調它們在數據挖掘中的應用情況。

　　2.1　模糊邏輯

　　模糊邏輯是1965年由澤德引入的，它為處理不確定和不精確的問題提供了一種數學工具。模糊邏輯是最早、應用最廣泛的軟計算方法，模糊集技術在數據挖掘領域也占有重要地位。從數據庫中挖掘知識主要考慮的是發現有興趣的模式并以簡潔、可理解的方式描述出來。模糊集可以對系統中的數據進行約簡和過濾，提供了在高抽象層處理的便利。同時，數據挖掘中的數據分析經常面對多種類型的數據，即符號數據和數字數據。Nauck[7]研究了新的算法，可以從同時包含符號數據和數字數據中生成混合模糊規則。數據挖掘中模糊邏輯主要應用于以下幾個方面：

　　(1)聚類。將物理或抽象對象的集合分組成為由類似的對象組成的多個類的過程被稱為聚類。聚類分析是一種重要的人類行為，通過聚類，人能夠識別密集的和稀疏的區域，因而發現全局的分布模式，以及數據屬性之間有趣的關系。模糊集有很強的搜索能力，它對發現的結構感興趣，這會幫助發現定性或半定性數據的依賴度。在數據挖掘中，這種能力可以幫助阻止搜到無用和微不足道的知識。研究者為此發展了模糊聚類算法，并得到了廣泛應用[8]。在高維數據挖掘中有太多的屬性要考慮，因此知識簡約就非常的必要。屬性聚類的實質就是知識簡約，所謂知識約簡，就是在保持知識庫的分類或者決策能力不變的條件下，刪除不重要的或冗余的知識，最小約簡(含有最小屬性)是人們所期望的，且約簡結果是不確定的。所以模糊聚類成為知識簡約的有力工具。

　　(2)關聯規則。數據挖掘重要的一點是關聯規則的發現，關聯規則挖掘是尋找給定數據集中屬性間的關聯。其中，布爾關聯規則考慮的是關聯的屬性在與不在的二維特征，概化關聯規則描述的是屬性的分層關系，量化關聯規則描述的是量化的屬性(既離散化的屬性)間的關聯[9]。由于使用模糊概念表示的規則更符合人的思維和表達習慣，增強了規則的可理解性，所以模糊技術已成為數據挖掘系統中的關鍵技術。文獻[10]中用模糊分類開拓了概化關聯規則。

　　(3)數據概化。概化發現是數據挖掘重要部分之一。它將大的數據集從較低的概念層抽象到較高的概念層，用可理解的信息來表達數據庫中最重要的部分，并提供給用戶。

　　大數據集的語言概化通過有效的程度來獲得，參考的標準內容在挖掘任務中。系統由概述、一致性程度真實和有效性組成。已經發現的最有興趣的語言概化并不瑣碎，卻很人性化。實際上，它并不能自動地進行概化，需要人的操作。Kacprzyk和Zadrozny[11]發展了功能依賴度，語言概化使用了自然和可理解性的詞匯，它支持模糊元素，包括屬性間模糊的、重要的相互作用。首先，用戶必須制定概化興趣度，然后系統從數據庫中獲得記錄，并計算每個概化的有效性，最后，選擇最適合的語言概化。此方法通過網絡瀏覽器已用在因特網上。模糊值、模糊聯系和語言量都通過JAVA來定義。

　　(4)Web應用。通過Web日志的挖掘，來發現用戶訪問Web頁面的模式。通過分析Web日志記錄中的規律，可以識別電子商務的潛在客戶，增強對最終用戶的Internet信息服務的質量和交付，并改進Web服務器系統的性能。還可以進一步獲得用戶訪問的附加信息(包括Web服務器緩沖區中用戶瀏覽Web頁面的序列等)，以便于做更為詳細的Web日志分析。如通過用戶訪問模式的學習改進其自身的Web站點，有助于建立針對個體用戶的定制Web服務。為了挖掘出較完全的興趣模式, 吳瑞[12]提出一種新的結構類型--FLAAT,它可發現那些被忽略的用戶瀏覽偏愛路徑。同時引進模糊集來處理停留在網頁上的時間,以形成語義術語使挖掘出的用戶瀏覽偏愛路徑更自然、更易理解。算法能準確地反映用戶的瀏覽興趣。

　　(5)圖像檢索。隨著近來由多種媒體數據構成的多媒體信息倉庫數據的增加，基于內容的圖像檢索開始活躍在這個領域。和傳統數據庫中基于精確匹配的關鍵字來檢索信息不同，基于內容的圖像檢索系統的信息是一個圖像的可視特征。如顏色、紋理、形狀等。由于檢索中查詢要求往往是根據人的主觀性所決定，因此很大程度上帶有模糊性。對于圖像紋理，習慣于用“很粗”、“中等”、“弱”這樣的一些模糊概念來描述;形狀一般用“幾何形的”、“立體形的”或“似長方形的”、“正方形的”等概念描述;顏色特征通常用“很艷”、“一般”、 “暗淡”或“大紅”、“紫紅”、“紅”這樣的模糊概念來描述。所以基于內容是圖像檢索是基于圖像的相似特征來檢索的。

　　2.2 神經網絡

　　數據挖掘的困難主要存在于三個方面：首先，巨量數據集的性質往往非常復雜，非線性、時序性與噪音普遍存在;其次，數據分析的目標具有多樣性，而復雜目標無論在表述還是在處理上均與領域知識有關;第三，在復雜目標下，對巨量數據集的分析，目前還沒有現成的且滿足可計算條件的一般性理論與方法。研究者們主要是將符號型機器學習方法與數據庫技術相結合，但由于真實世界的數據關系相當復雜，非線性程度相當高，而且普遍存在著噪音數據，因此這些方法在很多場合都不適用。

　　因為神經網絡的黑箱問題，在數據挖掘的初期并不看好，然而，神經網絡由于本身良好的魯棒性、自組織自適應性、并行處理、分布存儲和高度容錯等特性，以及它對未經訓練的數據分類模式的能力，非常適合解決數據挖掘中存在的以上問題，因此近年來越來越受到人們的關注。

　　規則抽取方法是解決“黑箱問題”的有效手段。神經網絡規則抽取的研究最早開始于80年代末。1988年，Gallant[13]設計了一個可以用if-then規則解釋推理結論的神經網絡專家系統。根據設計思想的不同，目前的規則提取方法大致可以分成兩大類，即基于結構分析的方法和基于性能分析的方法。

　　基于結構分析的神經網絡規則抽取方法把規則抽取視為一個搜索過程，其基本思想是把已訓練好的神經網絡結構映射成對應的規則。由于搜索過程的計算復雜度和神經網絡輸入分量之間呈指數級關系，當輸入分量很多時，會出現組合爆炸。因此，此類算法一般采用剪枝聚類等方法來減少網絡中的連接以降低計算復雜度。RX算法[14]首先用權衰減方法構造BP網絡(該網絡中連接權的大小反映了連接的重要程度)，然后對網絡進行修剪，在預測精度不變的情況下刪除次要連接，在對網絡進行充分簡化的條件下，對隱藏層結點的激活值進行聚類，根據不同的隱藏層結點激活值用窮舉搜索的辦法來尋找從輸入層到隱藏層和從隱藏層到輸出層的規則.

　　與基于結構分析的方法不同，基于性能分析的神經網絡規則抽取方法并不對神經網絡結構進行分析和搜索，而是把神經網絡作為一個整體來處理，這類方法更注重的是抽取出的規則在功能上對網絡的重現能力，即產生一組可以替代原網絡的規則。較有代表性的算法是Sestito等人提出的相似權值法[15]，這種方法將輸出節點添加到輸入層去與輸入節點進行比較。1994年，Craven和Shavlik[16]為神經網絡規則抽取任務下了一個定義：給定一個訓練好的神經網絡以及用于其訓練的訓練集，為網絡產生一個簡潔而精確的符號描述。在文獻[16]的基礎上，1996年，Craven和Shavlik[17]提出了TREPAN算法。該算法首先用訓練好的神經網絡對示例集進行分類，然后將該集合作為訓練集提供給決策樹學習算法，從而構造出一棵與原網絡功能接近的、使用MOFN表達式作為內部劃分的決策樹。TREPAN的計算量較低。1997年，Craven和Shavlik[18]將TREPAN用于一個噪音時序任務，即美元–馬克匯率預測，取得了比現有方法更好的效果。

　　2.3　遺傳算法

　　遺傳算法是一種基于生物自然選擇與遺傳機理的隨機搜索算法，是一種仿生全局優化方法。它是美國 Michigan大學的Holland教授于1975年首先提出的。遺傳算法中包含了5個基本要素：①參數編碼;②初始群體的設定;③適應度函數的設計;④遺傳操作設計;⑤控制參數設定。遺傳算法具有十分頑強的魯棒性、自適應性，其在解決大空間、多峰值、非線性、全局優化等復雜度高的問題時具有獨特的優勢。因此，遺傳算法在數據挖掘技術越來越顯示出其重要的地位。數據挖掘最初應用進化計算從給定的目標集中挖掘有趣的規則[19]，其強調從面向對象的數據庫中發現數據集的共有特性。遺傳算法也應用于其他方面如從多媒體數據庫中挖掘多媒體數據。遺傳算法在數據挖掘中主要應用于數據回歸和關聯規則的發現。

　　(1)回歸。除了發現可解釋的模式之外，數據挖掘的另外一個重要的任務就是預測，即通過數據庫中的一些變量發掘其超未來的趨勢值。傳統的線性回歸需要先假設這些屬性間沒有相關性，而遺傳算法則可以很好的處理有相關性的變量。Xu[20]曾設計了一個多輸入單輸出的系統，應用遺傳算法從訓練數據集中進行非線性多元回歸。

　　(2)關聯規則。遺傳學習首先創建一個由隨機產生的規則組成的初始群體。每個規則可以用一個二進制位串表示的if-than類型。通過全局搜索，形成由當前群體中最適合的規則組成新的群體。遺傳算法可以單獨用于數據倉庫中關聯規則的挖掘，還可以和其他的數據挖掘技術相結合，例如，用于進化神經網絡結構以得到結構簡單、性能優良的神經網絡結構[21];用于特征子集選擇[22];應用于決策樹、分類器和模糊規則的獲取等等。

　　2.4　粗集

　　粗集理論由波蘭邏輯學家Pawlak教授在20世紀80年代提出，是一種處理含糊和不確定問題的新型數學工具。粗集理念基于給定訓練數據內部的等價類的建立。給定現實世界數據，通常有些類不能被可用的屬性區分。粗集可以用來近似定義這種類，將問題的數據集進行劃分，然后對劃分的每一部分確定其對某一概念的支持程度：即肯定支持此概念，肯定不支持此概念，并分別用下近似和上近似集合來表示為正域、負域。它能有效地分析不精確、不一致、不完整等各種不完備的信息，還可以對數據進行分析和推理，從中發現隱含的知識和潛在的規律。同時，粗集理論在處理大數據量，消除冗余信息等方面有著良好的效果，因此廣泛應用于數據挖掘的數據預處理、規則生成等方面。

　　(1)數據約簡。粗集理論可提供有效方法用于對信息系統中的數據進行約簡在數據挖掘系統的預處理階段，通過粗集理論刪除數據中的冗余信息(屬性、對象以及屬性值等)，可大大提高系統的運算速度。文獻[23]使用粗集方法對信息系統進行屬性及屬性域的約簡，然后使用神經網絡對約簡后的數據進行分類，從而在網絡分類精度沒有明顯下降的前提下使網絡的學習速度提高到約簡前的4.72倍。

　　(2)規則抽取。與其它方法(如神經網絡)相比，使用粗集理論生成規則是相對簡單和直接的，信息系統中的每一個對象既對應一條規則。粗集方法生成規則的一般步驟為：①得到條件屬性的一個約簡，刪去冗余屬性;②冊去每條規則的冗余屬性值;③對剩余規則進行合并目前己經產生了許多基于粗集理論的方法用于從信息系統中抽取規則[ 24]。

　　粗集理論存在對錯誤描述的確定性機制過于簡單，而且在約簡的過程中缺乏交互驗證功能，因此，粗集理論與其它方法如神經網絡、遺傳算法、模糊數學、決策樹等相結合可以發揮各自的優勢，大大增強數據挖掘的效率。文獻[25]提出了一種融合粗集理論和神經網絡的數據挖掘新方法，應用于大型數據庫的分類規則挖掘。其主要思想是首先由粗糙集理論對數據庫進行初步約簡，然后借助于神經網絡在自學習過程中完成對數據庫的進一步屬性約簡，并過濾數據中的噪聲數據，最后由粗糙集理論對約簡后的數據庫進行規則抽取。粗集理論的使用提高了系統的運算速度，同時神經網絡則使產生的規則集泛化能力提高。

　　2.5　混合方法

　　綜合軟計算的主要算法可產生在并行化、容錯、自適應性和不定性管理方面更好的系統。混合系統可使許多應用中的自動化自適應系統成為現實。模糊系統的推理能力，當與神經網絡和遺傳算法的學習能力結合時，導致得到體現合理有效的認識系統(可學習和推理的系統)的新產品和新過程。Banerjee[25]利用粗糙集、神經網絡和模糊邏輯相結合的方法設計了數據挖掘系統，其中用粗糙集方法在決策表中進行約簡。而用模糊集方法挖掘出未經加工的知識，最后由神經網絡根據依賴度進行取舍。

　　3 結束語

　　目前，數據挖掘中算法和可視化的研究越來越顯得重要。因為從數據庫中很容易就可以發現大量的模式，而這些模式中很多是很顯而易見的、冗余的、無用的，或是對用戶來說沒有趣的。現在就需要能夠過濾這些模式而提供給用戶有用或有趣的模式的挖掘技術。軟計算方法包括模糊邏輯、神經網絡、遺傳算法、粗集和混合方法近來用于解決這些問題。

　　軟計算具有以低求解成本、快速的方法解決復雜問題。本文對數據挖掘中軟計算方法及應用作了一個綜合性闡述。對它們的特點進行了分析，并對它們在數據挖掘中的應用進行了分類。模糊集為這個過程中的處理不確定性提供了一個自然框架，神經網絡和粗集廣泛應用于分類和規則生成。遺傳算法應用于各種優化和搜索過程中，如優化排序和模式選擇。

　　參考文獻

　　[1] U. Fayyad and R. Uthurusamy, “Data mining and knowledge discovery in databases,” Commun. ACM, vol. 39, pp. 24–27, 1996.

　　[2] W. H. Inmon, “The data warehouse and data mining,” Commun. ACM,vol. 39, pp. 49–50, 1996.

　　[3]楊會志.數據挖掘技術的主要方法及其發展方向.河北科技大學學報[J].2000，21(3)：77-80.

　　[4] J. A. Major and D. R. Riedinger, “EFD—A hybrid knowledge statisticalbased工作system for the detection of fraud,” Int. J. Intell. Syst., vol. 7, pp.687–703, 1992.

　　[5] R. Heider, Troubleshooting CFM 56-3 Engines for the Boeing 737—Using CBR and Data-Mining, Spinger-Verlag, New York, vol. 1168, pp. 512–523, 1996. Lecture Notes in Computer Science.

　　[6] Zadeh L.，Fuzzv logic，neural network and soft computing. Communications of the ACM，1994, 37(3)：77-84.

　　[7] D. Nauck, “Using symbolic data in neuro-fuzzy classification,” inProc.NAFIPS 99, New York, June 1999, pp. 536–540.

　　[8]湯效琴，戴汝源.數據挖掘中變量聚類方法的應用研究.計算機工程與應用[J].2004，40(24)：171-173.

　　[9] 范明,孟小峰譯. 數據挖掘：概念與技術[M].北京：機械工業出版社，2001.

　　[10] Q. Wei and G. Chen, “Mining generalized association rules with fuzzy taxonomic structures,” in Proc. NAFIPS 99, New York, June 1999, pp. 477–481.

　　[11] J. Kacprzyk and S. Zadrozny, “Data mining via linguistic summaries of data: An interactive approach,” in Proc. IIZUKA 98, Fukuoka, Japan, Oct. 1998, pp. 668–671.

　　[12] 吳瑞.基于FLAAT模糊的WEB挖掘算法.武漢科技大學學報(自然科學版)[J].2005,28(3)：270-272.

　　[13] S.I.Gallant. Neural Nework Learning and Expert Systems. Cambridge, MA:MIT press, 1993.

　　[14] Rudy Setiono, Liu H. Understanding neural networks via rule extraction. In: Proc of the 14th International Joint Conference on Artificial Intelligence, Montreal, 1995. pp.480-485

　　[15] Sestito S, Dillon T. Knowledge acquisition of conjunctive rules using multilayered neural networks. International Journal of Intell Sys, 1993, 8(7): 779～805

　　[16]M.W.Craven, J,W,Shavlik . Using sampling and queries to extract rules from trained neural networks. In: Proc of the 7th Int'l Conf on Mathine Learning, New Brunswick, 1994. pp.37～45

　　[17] M.W.Craven, J,W,Shavlik. Extracting tree-structured representations of trained networks. Cambridge, MA:MIT press, 1996.

　　[18] M.W.Craven, J,W,Shavlik. Using neural networks in data mining. Future Generation Computer Systems.1997.13.pp.211-229.

　　[19]T. Ryu and C. F. Eick, “MASSON: Discovering commonalties in collection of objects using genetic programming,” in Proc. 1st Annu. Conf. Genetic Programming 1996, Stanford Univ., CA, July 28–31, 1996, pp. 200–208.

　　[20] K. Xu, Z. Wang, and K. S. Leung, “Using a new type of nonlinear integral for multiregression: An application of evolutionary algorithms in data mining,” Proc. IEEE Int. Conf. Syst., Man, Cybern., pp. 2326–2331, Oct. 1998.

　　[21]鄭志軍，林霞光.一種基于神經網絡的數據挖掘方法.西安建筑科技大學學報[J] .2000，32

　　[22]劉勇國，李學明，張偉基.于遺傳算法的特征子集選擇.計算機工程[J].2003，29

　　[23] Jelonek J，Krawiec K. Rough set reduction of attributes and their domains for neural networks[J]. Computational Intelligence.1995.11(2)：339-347.

　　[24] Kryszkiewicz M. Rules in incomplete systems[J]. Information Sciences, 1999,113(4): 271-292.

　　[25] Banerjee M. Pal K. Rough fuzzy MLP: knowledge encoding and classification[J]. IEEE Trans. Neural Networks, 2002.9:1203-1216.