[發明專利]一種基于類-屬性關系依賴度的數據離散化方法

無效

• 申請號: 200910219832.1
• 申請日: 2009-11-10
• 公開（公告）號: CN101702172A
• 公開（公告）日: 2010-05-05
• 發明（設計）人: 李克秋;王哲;桑雨;申嚴明
• 申請（專利權）人: 大連理工大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 大連理工大學專利中心 21200
• 代理人: 梅洪玉

技術領域

本發明屬于數據挖掘領域，涉及到機器學習中的連續屬性離散化算法，特別涉及到一種基于類-屬性關系依賴度的CAIM(Class-Attribute?InterdependenceMaximization)算法。

背景技術

過去，在數據挖掘領域中，對于離散化算法的研究通常被認為是一種輔助性工作而沒有受到應有的重視，直到近年來隨著知識發現和機器學習領域的迅速發展才引起研究人員的關注。來源于現實生活中的數據集經常會涉及到連續的數值屬性，然而目前許多的機器學習算法卻只能處理只包含離散值屬性的數據集，給機器學習的研究帶來了不便。典型的機器學習算法如決策樹、關聯規則等只能處理離散值屬性數據集。對于連續值屬性數據集，則需要在機器學習之前進行離散化處理。

隨著人們對該領域的廣泛關注和深入研究，離散化算法已經得到了很大的發展，多種基于不用離散方式的算法被提出來。下面重點介紹基于類-屬性關系依賴度的CAIM算法。

基于類-屬性依賴度(Class-Attribute?Interdependence)的算法

這類算法利用類與屬性的關系建立二維矩陣，并通過從中提取的信息來衡量類與屬性的依賴程度，從而確定合適的條件作為離散化判別式。首先1995年J.Y.Ching等人提出了CADD(Class-Dependent?Discretizer?Algorithm)算法[J.Y.Ching，A.K.C.Wong，K.C.C.Chan，Class-dependent?discretization?for?inductivelearning?from?continuous?and?mixed?mode?data，IEEE?transactions?on?pattern?analysisand?machine?intelligence，2005，17(7)：641-651]，它是一種自上而下的離散化算法。該算法沒有給出初始的劃分點集應如何確定，而且在如何進行區間的調整方面也沒有給出有效的方法，實驗表明，以cair值作為離散判別式也是不合適的，其會產生過多的區間而造成訓練過度。2004年Lukasz?A.Kurgan等人提出了CAIM(Class-Attribute?Interdependence?Maximization)算法[K.J.Cios，L.Kurgan.CAIM?discretization?algorithm[J].IEEE?transactions?on?knowledge?and?dataengineering，2004：145-153]，它是一種全局的、靜態的、自上而下的有監督離散化算法。該算法以達到類與屬性相關度最大化為目標，以caim值作為離散判別式，算法的時間復雜度為Nlog(N)，其中N為數據集中實例的個數。

相比于其它離散化算法，CAIM算法具有時間復雜度小，精度和效率相對較高的特點，但該算法存在著三個不足。首先，在離散化的過程中沒有考慮到屬性的重要性；其次，缺乏對不一致率的考慮；最后，采用caim值作為離散判別式也有其不合理之處。這常常造成信息丟失，從而影響到機器學習的精度。

發明內容

本發明要解決的技術問題是基于類-屬性關系依賴度提出一種有監督的離散化算法，使其得到的離散化結果在后繼的機器學習中達到更高的精度。

本發明的技術方案是：

(1)基于類-屬性關系依賴度的CAIM離散化改進方案。

該算法根據DSST差異相似集理論來度量屬性重要性，在考慮決策表不一致率的情況下對數據進行進一步的離散化。

一個信息系統通常可以表達為S＝<U，C，D，V，f>，這里U是研究論域(Universe)，即研究對象的集合，C∪U＝R是屬性集合，子集C稱為條件屬性集，D稱為決策屬性集，f定義一個信息函數，即f：U×R→V，它指定中U每一個對象x的屬性值。

①屬性重要性的相關定義與計算方式：

定義1.如公式(1)所示，x_i代表第i個實例，x_j代表第j個實例，則差集DS_ij代表當x_i和x_j兩個實例決策屬性不相同時，條件屬性也不相同的屬性集合。

其中*表示可取該屬性值域中的任何值。