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