一種基于核值的粗糙集填補方法
2014-07-24 15:51:36席寧
新媒體研究 2014年8期
摘 要 利用粗糙集的知識來進行缺失數(shù)據(jù)填補的方法很多，但很多都沒有考慮到?jīng)Q策規(guī)則。文章利用核值的重要性，通過構(gòu)造可辨識矩陣，使得填補的數(shù)據(jù)更好的遵循決策規(guī)則，消除噪音數(shù)據(jù)。
關(guān)鍵詞 核值；極大完備子系統(tǒng)；可辨識矩陣
中圖分類號：TP311 文獻標識碼：A 文章編號：1671-7597（2014）08-0061-01
1 粗糙集相關(guān)知識
在現(xiàn)今社會中，各個行業(yè)都會用數(shù)據(jù)庫來保存大量的歷史數(shù)據(jù)。然而，這些數(shù)據(jù)總會在不經(jīng)意間有所缺失，可能是環(huán)境因素，也可能是人為缺失。缺失的數(shù)據(jù)都蘊含著大量寶貴有用的信息，與企業(yè)經(jīng)營成果息息相關(guān)，因此很多企業(yè)都采用數(shù)據(jù)挖掘等技術(shù)，從缺失的數(shù)據(jù)中挖掘出有價值的信息。
粗糙集理論是繼概率論，模糊集，證據(jù)理論之后的又一個處理不確定性的數(shù)學(xué)工具，其作為一種較新的軟計算方法，其被有效的運用到數(shù)據(jù)預(yù)處理中，為不完備信息的填補開辟了另一條途徑。
在基于粗糙集的屬性約簡過程中，核值才是最有用的數(shù)據(jù)。本文提出了一種基于核值的重要性的填補方法，較好的保持信息表的決策規(guī)則。
該算法主要涉及到極大完備子系統(tǒng)和可辨識矩陣等粗糙集知識，相關(guān)的定義如下。
定理1 任一信息系統(tǒng)=，若增加一條對象，構(gòu)成一個新的信息系統(tǒng)=<，，，>，其中，則的核值必是的核值。
推論 不完備信息系統(tǒng)S=
2 基于核值的ROUSTIDA算法描述
2.1 算法描述
由上述推論可以表明將不完備信息系統(tǒng)S分離成其極大完備子系統(tǒng)和待補系統(tǒng)，而的核值必是S的核值，這說明在的核值的基礎(chǔ)上引進不可分辨關(guān)系不影響S的核值。
該算法是以可辨識矩陣為基礎(chǔ)，基本流程如下。
輸入：不完備信息系統(tǒng)；
輸出：完備信息系統(tǒng)；其中，前者是條件屬性集，后者為決策屬性集；
第一步 核值化：
將分離成它的極大完備子系統(tǒng)和待補系統(tǒng)。將看作是一個獨立系統(tǒng)，建立它的核值體系，然后再將非核值的數(shù)據(jù)改為“*”，這樣就會得到一個新的系統(tǒng)，將組合成一個新的信息系統(tǒng)=<，，，>.
第二步 求矩陣，，；r=0；
第三步
1）針對所有，求得，；
2）生成
（1） 對于所有，有=，；
（2） 對于所有，對做循環(huán)；
①若=0，=*；
②否則若，則
（1）若，則；
（2）若，則；
（3）否則；
③若某一對象與多個對象存在不可分辨關(guān)系，則將此對象的缺失屬性值用其余對象的此屬性的均值填補；
第四步 決策表中對象獨立性的判斷：
1）對上述；若=0，則如存在，使=時，都有，將=*轉(zhuǎn)步驟3，否則轉(zhuǎn)2；若有（），將（）整行刪去；否則轉(zhuǎn)2；
2）若=轉(zhuǎn)步驟5；否則，計算，，，，轉(zhuǎn)到第三步；
第五步 如果有遺失值，可用其他算法處理；
第六步 結(jié)束。
2.2 算法分析
算法主要解決使ROUSTIDA算法失效的不完備數(shù)據(jù)?？梢酝ㄟ^以下圖表來說明問題。包括原始的不完備信息表，經(jīng)過步驟一得出的基于核值的不完備信息系統(tǒng)，以及最終得到的完備信息表。
表1 原始表
U a1 a2 a3 a4
1 0 1 0 1
2 * 2 1 0
3 * 0 0 0
4 0 * 1 0
5 1 0 1 2
表2 基于核值的不完備信息表
U a1 a2 a3 a4
1 0 1 0 1
2 * 2 1 0
3 * 0 0 0
4 0 1 1 1
5 1 0 1 2
表3 結(jié)果表
U a1 a2 a3 a4
1 0 1 0 1
2 0 2 1 0
3 0 0 0 0
4 0 1 1 0
5 1 0 0 2
與原ROUSTIDA算法比較，該算法能使更多的缺失項得到科學(xué)的填補，且該算法在缺失項填補過程中，基于可辨識矩陣，以核值為比較對象，這樣填補可保留更多的核值，從而使填補的值與決策規(guī)則更為貼近。同時第四步對決策表中對象獨立性的判斷，使該算法避免了應(yīng)用其他方法可能導(dǎo)致的決策規(guī)則矛盾的問題。
但該算法也存在一定的缺點：1）計算較為復(fù)雜，比原ROUSTIDA算法計算繁瑣；2）該算法僅對缺損數(shù)據(jù)較少時適用，若缺損較多，則對于初始計算極大完備子系統(tǒng)時存在的困難較大，甚至可能無法操作。
3 結(jié)論
一般的填補數(shù)據(jù)方法有時容易引起信息表內(nèi)容的沖突，本算法是基于核值的基礎(chǔ)上進行缺失數(shù)據(jù)填補的，能夠保持更多的核值，并且更好的避免了信息表的沖突，又較好的反映了信息表所蘊含的決策規(guī)則。
參考文獻
[1]Pawlak Z. Rough Sets and Fuzzy Sets. Fuzzy Sets and Systems， 1985（17）：99-102.
[2]Krysikiewicz M. Rough Set Approach to Incomplete Information System. Information Sciences， 1998（112）：39-49.
[3]王國胤.Rough集理論與知識獲取[M].西安：西安交通大學(xué)出版社，2005.
[4]張文修，吳偉志，梁吉業(yè)，等.粗糙集理論與方法[M].北京：科學(xué)出版社，2006.
[5]曾黃麟.粗糙集理論及其應(yīng)用[M].重慶：重慶大學(xué)出版社，1996.
作者簡介
席寧（1977-），女，漢族，遼寧錦州人，副教授，碩士，主要從事計算機網(wǎng)絡(luò)，數(shù)據(jù)挖掘，計算機應(yīng)用設(shè)計。
摘 要 利用粗糙集的知識來進行缺失數(shù)據(jù)填補的方法很多，但很多都沒有考慮到?jīng)Q策規(guī)則。文章利用核值的重要性，通過構(gòu)造可辨識矩陣，使得填補的數(shù)據(jù)更好的遵循決策規(guī)則，消除噪音數(shù)據(jù)。
關(guān)鍵詞 核值；極大完備子系統(tǒng)；可辨識矩陣
中圖分類號：TP311 文獻標識碼：A 文章編號：1671-7597（2014）08-0061-01
1 粗糙集相關(guān)知識
在現(xiàn)今社會中，各個行業(yè)都會用數(shù)據(jù)庫來保存大量的歷史數(shù)據(jù)。然而，這些數(shù)據(jù)總會在不經(jīng)意間有所缺失，可能是環(huán)境因素，也可能是人為缺失。缺失的數(shù)據(jù)都蘊含著大量寶貴有用的信息，與企業(yè)經(jīng)營成果息息相關(guān)，因此很多企業(yè)都采用數(shù)據(jù)挖掘等技術(shù)，從缺失的數(shù)據(jù)中挖掘出有價值的信息。
粗糙集理論是繼概率論，模糊集，證據(jù)理論之后的又一個處理不確定性的數(shù)學(xué)工具，其作為一種較新的軟計算方法，其被有效的運用到數(shù)據(jù)預(yù)處理中，為不完備信息的填補開辟了另一條途徑。
在基于粗糙集的屬性約簡過程中，核值才是最有用的數(shù)據(jù)。本文提出了一種基于核值的重要性的填補方法，較好的保持信息表的決策規(guī)則。
該算法主要涉及到極大完備子系統(tǒng)和可辨識矩陣等粗糙集知識，相關(guān)的定義如下。
定理1 任一信息系統(tǒng)=，若增加一條對象，構(gòu)成一個新的信息系統(tǒng)=<，，，>，其中，則的核值必是的核值。
推論 不完備信息系統(tǒng)S=
2 基于核值的ROUSTIDA算法描述
2.1 算法描述
由上述推論可以表明將不完備信息系統(tǒng)S分離成其極大完備子系統(tǒng)和待補系統(tǒng)，而的核值必是S的核值，這說明在的核值的基礎(chǔ)上引進不可分辨關(guān)系不影響S的核值。
該算法是以可辨識矩陣為基礎(chǔ)，基本流程如下。
輸入：不完備信息系統(tǒng)；
輸出：完備信息系統(tǒng)；其中，前者是條件屬性集，后者為決策屬性集；
第一步 核值化：
將分離成它的極大完備子系統(tǒng)和待補系統(tǒng)。將看作是一個獨立系統(tǒng)，建立它的核值體系，然后再將非核值的數(shù)據(jù)改為“*”，這樣就會得到一個新的系統(tǒng)，將組合成一個新的信息系統(tǒng)=<，，，>.
第二步 求矩陣，，；r=0；
第三步
1）針對所有，求得，；
2）生成
（1） 對于所有，有=，；
（2） 對于所有，對做循環(huán)；
①若=0，=*；
②否則若，則
（1）若，則；
（2）若，則；
（3）否則；
③若某一對象與多個對象存在不可分辨關(guān)系，則將此對象的缺失屬性值用其余對象的此屬性的均值填補；
第四步 決策表中對象獨立性的判斷：
1）對上述；若=0，則如存在，使=時，都有，將=*轉(zhuǎn)步驟3，否則轉(zhuǎn)2；若有（），將（）整行刪去；否則轉(zhuǎn)2；
2）若=轉(zhuǎn)步驟5；否則，計算，，，，轉(zhuǎn)到第三步；
第五步 如果有遺失值，可用其他算法處理；
第六步 結(jié)束。
2.2 算法分析
算法主要解決使ROUSTIDA算法失效的不完備數(shù)據(jù)?？梢酝ㄟ^以下圖表來說明問題。包括原始的不完備信息表，經(jīng)過步驟一得出的基于核值的不完備信息系統(tǒng)，以及最終得到的完備信息表。
表1 原始表
U a1 a2 a3 a4
1 0 1 0 1
2 * 2 1 0
3 * 0 0 0
4 0 * 1 0
5 1 0 1 2
表2 基于核值的不完備信息表
U a1 a2 a3 a4
1 0 1 0 1
2 * 2 1 0
3 * 0 0 0
4 0 1 1 1
5 1 0 1 2
表3 結(jié)果表
U a1 a2 a3 a4
1 0 1 0 1
2 0 2 1 0
3 0 0 0 0
4 0 1 1 0
5 1 0 0 2
與原ROUSTIDA算法比較，該算法能使更多的缺失項得到科學(xué)的填補，且該算法在缺失項填補過程中，基于可辨識矩陣，以核值為比較對象，這樣填補可保留更多的核值，從而使填補的值與決策規(guī)則更為貼近。同時第四步對決策表中對象獨立性的判斷，使該算法避免了應(yīng)用其他方法可能導(dǎo)致的決策規(guī)則矛盾的問題。
但該算法也存在一定的缺點：1）計算較為復(fù)雜，比原ROUSTIDA算法計算繁瑣；2）該算法僅對缺損數(shù)據(jù)較少時適用，若缺損較多，則對于初始計算極大完備子系統(tǒng)時存在的困難較大，甚至可能無法操作。
3 結(jié)論
一般的填補數(shù)據(jù)方法有時容易引起信息表內(nèi)容的沖突，本算法是基于核值的基礎(chǔ)上進行缺失數(shù)據(jù)填補的，能夠保持更多的核值，并且更好的避免了信息表的沖突，又較好的反映了信息表所蘊含的決策規(guī)則。
參考文獻
[1]Pawlak Z. Rough Sets and Fuzzy Sets. Fuzzy Sets and Systems， 1985（17）：99-102.
[2]Krysikiewicz M. Rough Set Approach to Incomplete Information System. Information Sciences， 1998（112）：39-49.
[3]王國胤.Rough集理論與知識獲取[M].西安：西安交通大學(xué)出版社，2005.
[4]張文修，吳偉志，梁吉業(yè)，等.粗糙集理論與方法[M].北京：科學(xué)出版社，2006.
[5]曾黃麟.粗糙集理論及其應(yīng)用[M].重慶：重慶大學(xué)出版社，1996.
作者簡介
席寧（1977-），女，漢族，遼寧錦州人，副教授，碩士，主要從事計算機網(wǎng)絡(luò)，數(shù)據(jù)挖掘，計算機應(yīng)用設(shè)計。
摘 要 利用粗糙集的知識來進行缺失數(shù)據(jù)填補的方法很多，但很多都沒有考慮到?jīng)Q策規(guī)則。文章利用核值的重要性，通過構(gòu)造可辨識矩陣，使得填補的數(shù)據(jù)更好的遵循決策規(guī)則，消除噪音數(shù)據(jù)。
關(guān)鍵詞 核值；極大完備子系統(tǒng)；可辨識矩陣
中圖分類號：TP311 文獻標識碼：A 文章編號：1671-7597（2014）08-0061-01
1 粗糙集相關(guān)知識
在現(xiàn)今社會中，各個行業(yè)都會用數(shù)據(jù)庫來保存大量的歷史數(shù)據(jù)。然而，這些數(shù)據(jù)總會在不經(jīng)意間有所缺失，可能是環(huán)境因素，也可能是人為缺失。缺失的數(shù)據(jù)都蘊含著大量寶貴有用的信息，與企業(yè)經(jīng)營成果息息相關(guān)，因此很多企業(yè)都采用數(shù)據(jù)挖掘等技術(shù)，從缺失的數(shù)據(jù)中挖掘出有價值的信息。
粗糙集理論是繼概率論，模糊集，證據(jù)理論之后的又一個處理不確定性的數(shù)學(xué)工具，其作為一種較新的軟計算方法，其被有效的運用到數(shù)據(jù)預(yù)處理中，為不完備信息的填補開辟了另一條途徑。
在基于粗糙集的屬性約簡過程中，核值才是最有用的數(shù)據(jù)。本文提出了一種基于核值的重要性的填補方法，較好的保持信息表的決策規(guī)則。
該算法主要涉及到極大完備子系統(tǒng)和可辨識矩陣等粗糙集知識，相關(guān)的定義如下。
定理1 任一信息系統(tǒng)=，若增加一條對象，構(gòu)成一個新的信息系統(tǒng)=<，，，>，其中，則的核值必是的核值。
推論 不完備信息系統(tǒng)S=，=是其極大完備子系統(tǒng)，則的核值必是S的核值。
2 基于核值的ROUSTIDA算法描述
2.1 算法描述
由上述推論可以表明將不完備信息系統(tǒng)S分離成其極大完備子系統(tǒng)和待補系統(tǒng)，而的核值必是S的核值，這說明在的核值的基礎(chǔ)上引進不可分辨關(guān)系不影響S的核值。
該算法是以可辨識矩陣為基礎(chǔ)，基本流程如下。
輸入：不完備信息系統(tǒng)；
輸出：完備信息系統(tǒng)；其中，前者是條件屬性集，后者為決策屬性集；
第一步 核值化：
將分離成它的極大完備子系統(tǒng)和待補系統(tǒng)。將看作是一個獨立系統(tǒng)，建立它的核值體系，然后再將非核值的數(shù)據(jù)改為“*”，這樣就會得到一個新的系統(tǒng)，將組合成一個新的信息系統(tǒng)=<，，，>.
第二步 求矩陣，，；r=0；
第三步
1）針對所有，求得，；
2）生成
（1） 對于所有，有=，；
（2） 對于所有，對做循環(huán)；
①若=0，=*；
②否則若，則
（1）若，則；
（2）若，則；
（3）否則；
③若某一對象與多個對象存在不可分辨關(guān)系，則將此對象的缺失屬性值用其余對象的此屬性的均值填補；
第四步 決策表中對象獨立性的判斷：
1）對上述；若=0，則如存在，使=時，都有，將=*轉(zhuǎn)步驟3，否則轉(zhuǎn)2；若有（），將（）整行刪去；否則轉(zhuǎn)2；
2）若=轉(zhuǎn)步驟5；否則，計算，，，，轉(zhuǎn)到第三步；
第五步 如果有遺失值，可用其他算法處理；
第六步 結(jié)束。
2.2 算法分析
算法主要解決使ROUSTIDA算法失效的不完備數(shù)據(jù)?？梢酝ㄟ^以下圖表來說明問題。包括原始的不完備信息表，經(jīng)過步驟一得出的基于核值的不完備信息系統(tǒng)，以及最終得到的完備信息表。
表1 原始表
U a1 a2 a3 a4
1 0 1 0 1
2 * 2 1 0
3 * 0 0 0
4 0 * 1 0
5 1 0 1 2
表2 基于核值的不完備信息表
U a1 a2 a3 a4
1 0 1 0 1
2 * 2 1 0
3 * 0 0 0
4 0 1 1 1
5 1 0 1 2
表3 結(jié)果表
U a1 a2 a3 a4
1 0 1 0 1
2 0 2 1 0
3 0 0 0 0
4 0 1 1 0
5 1 0 0 2
與原ROUSTIDA算法比較，該算法能使更多的缺失項得到科學(xué)的填補，且該算法在缺失項填補過程中，基于可辨識矩陣，以核值為比較對象，這樣填補可保留更多的核值，從而使填補的值與決策規(guī)則更為貼近。同時第四步對決策表中對象獨立性的判斷，使該算法避免了應(yīng)用其他方法可能導(dǎo)致的決策規(guī)則矛盾的問題。
但該算法也存在一定的缺點：1）計算較為復(fù)雜，比原ROUSTIDA算法計算繁瑣；2）該算法僅對缺損數(shù)據(jù)較少時適用，若缺損較多，則對于初始計算極大完備子系統(tǒng)時存在的困難較大，甚至可能無法操作。
3 結(jié)論
一般的填補數(shù)據(jù)方法有時容易引起信息表內(nèi)容的沖突，本算法是基于核值的基礎(chǔ)上進行缺失數(shù)據(jù)填補的，能夠保持更多的核值，并且更好的避免了信息表的沖突，又較好的反映了信息表所蘊含的決策規(guī)則。
參考文獻
[1]Pawlak Z. Rough Sets and Fuzzy Sets. Fuzzy Sets and Systems， 1985（17）：99-102.
[2]Krysikiewicz M. Rough Set Approach to Incomplete Information System. Information Sciences， 1998（112）：39-49.
[3]王國胤.Rough集理論與知識獲取[M].西安：西安交通大學(xué)出版社，2005.
[4]張文修，吳偉志，梁吉業(yè)，等.粗糙集理論與方法[M].北京：科學(xué)出版社，2006.
[5]曾黃麟.粗糙集理論及其應(yīng)用[M].重慶：重慶大學(xué)出版社，1996.
作者簡介
席寧（1977-），女，漢族，遼寧錦州人，副教授，碩士，主要從事計算機網(wǎng)絡(luò)，數(shù)據(jù)挖掘，計算機應(yīng)用設(shè)計。
