《偏序信息系统中基于属性优势度的一种全序化方法》由会员分享，可在线阅读，更多相关《偏序信息系统中基于属性优势度的一种全序化方法（3页珍藏版）》请在金锄头文库上搜索。
1、计算机科学2 0 0 7 V 0 1 3 4 N Q 8 A 偏序信息系统中基于属性优势度的一种全序化方法* ) A R a n k i n gM e t h o dB a s e do nA t t r i b u t eD o m i n a n c eD e g r e ei nO r d e r e dI n f o r m a t i o nS y s t e m 赵静1 - 2 曹付元2 梁吉业1 2 ( 计算智能与中文信息处理省部共建教育部重点实验室太原0 3 0 0 0 6 ) 1 ( 山西大学计算机与信息技术学院太原0 3 0 0 0 6 ) 2 A b s t r a c
2、I nt h ep a p e r ，t h ed o m i n a n c ed e g r e eo fs i n g l ea t t r i b u t ea n dt h ed o m i n a n c ed e g r e eo ft h ea t t r i b u t es e ta t e d e f i n e d T h ed o m i n a n c ed e g r e eo ft h ew h o l eo r d e r e di n f o r m a t i o ns y s t e mi sg i v e n As o r t i n gm e t h
3、 o db a s e dO nt h e d o m i n a n c ed e g r e ei sp r o p o s e di nt h ep a p e r T h ee f f e c t i v e n e s so ft h i sa p p r o a c hi si l l u s t r a t e db y 孤e x a m p l 己 K e y w o r d sR o u g hs e t s ，D o m i n a n c er e l a t i o n ，S o r t i n g ，D o m i n a n c es e g r e e 1 引言
4、信息系统作为数据的一种描述框架，广泛存在 于数据库模型、决策分析、模式识别与机器学习等领 域。粗糙集理论是P a w l a kZ c l 于1 9 8 2 年提出的一 种在信息系统框架下研究不完整、不确定知识表示 及归纳推理的学习理论，但经典粗糙集理论不能处 理具有偏好属性的信息系统，文 2 6 提出了基于 偏序关系扩展的粗糙集方法，并将其应用于偏序信 息系统中。 全序化方法是偏序信息系统中的研究热点。传 统的方法有基于权重信息的方法 7 ，为了避免权重 信息的主观性，通常这类方法需要经过复杂的计算 确定权重。因此，近年来许多学者提出了基于粗糙 集理论的全序化方法 8 叫，避免使用权重信息，
5、而 是将偏好关系用知识的形式表示出来并结合相应的 规则实现全序化。文 8 ，l o 提出了通过比较对象在 全体属性上的优势、劣势类来实现快速全序化的方 法。文l - 9 ，1 1 3 提出了进人流、离开流和净流的概念， 在将偏序信息系统转换为两两比较表的基础上计算 净流，并按净流大小对各个对象进行排序，实质上是 利用不优于对象的元素个数与优于对象的元素个数 的差值将系统中的对象排序。文 8 1 1 的方法将 对象进行排序时，在属性集上具有一致优劣关系的 对象越多，即可比较的对象越多，排序结果越好，而 当偏序信息系统中可比较的对象较少时，利用文 8 1 1 的方法对不可比较的对象排序结果较差因
6、此这类方法对偏序信息系统的要求较高。许多实际 偏序信息系统中的对象只有一少部分是可比较的， 因此，对于不可比较对象，利用文E 8 1 1 的方法进 行排序后结果不甚理想。 针对以上问题，本文提出了一种基于属性优势 度的全序化方法，分析对象在每个属性上的优劣关 系，进而确定对象在偏序信息系统中的综合优势度， 利用对象的综合优势度由高到低的顺序将偏序信息 系统全序化，实例表明该方法有较好的排序结果。 2 偏序信息系统的基本概念 一个偏序信息系统由一个四元组构成：S 一( U ， A ，V ，p ，其中，U = X t ，z z ，z 。) 为对象集，A = a 。，a ：9a - ，口。) 为属性
7、集，y = UU 为属性集值域， 并且属性值V d 有偏好次序，f t U A V 是一个 信息函数，表示对每一个a A ，z U ，f ( x ，口) 圮。 若对象z i 在属性a 上不劣于对象工j ，则有， ( 五，口) f ( x i ，口) ，若对象五在属性口上不优于对 象z j ，则有f ( x f ，口) f ( x j ，口) 。 定义1 t 1 0 设S = ( U ，A ，V ，厂) 是一个偏序信 息系统，B A ，则定义 赂= ( z f ，而) U 2I f e z f ，口) f ( x i ，口) ，( Y a B ) ( 1 ) 尺吾= ( z f ，而) U zI
8、 f ( x i ，n ) f ( x i ，n ) ，( V 口 B ) ) ( 2 ) 为S 在属性集B 上的优势关系和劣势关系。 若( z i ，z j ) R i ，则表示对象正在属性集B 上 优于对象X j ，记为霸 z ；若( z ，工，) R “则表示 * ) 本文得到国家自然科学基金( N o ：7 0 4 7 1 0 0 3 ) 、高等学校博十学科点专项科研基金f N o ：2 0 0 5 0 1 0 8 6 0 4 ) 、教育部科学技术研究重点项目( N o t 2 0 6 0 1 7 ) 、山西省蘑点实验窀开放基金( N o ：2 0 0 6 0 3 0 2 3 】和太原
9、市科技局项目f N o ：0 7 0 1 0 7 2 4 ) 的资助。赵静硕十研究乍主要研究领域：数 据挖掘、智能决策；曹付元博士研究生。主要研究领域：数据挖掘、机器学习；粱吉韭教授，博士生导师主要研究领域：粗糙集理论，数据挖 掘、人【智能等。 2 6 对象五在属性集B 上劣于对象z j ，记为五 1R ( 五，z ，) = J uI - 1 【o ，IV 口I = l ( 7 ) 为偏序信息系统中对象五在属性a 上优于对象z j 的优势度。 兄( 丑，乃) 具有如下的性质： 性质11 R ( z i ，z j ) 1 。 性质2 若f ( x i ，n ) 一M a x ( 厂( z 1 ，
10、口) ，f ( x 2 ， n ) ，f ( x 。，口) ) ，且厂( 乃，口) = M i n ( ( z l ，口) ，厂 ( J r 2 ，口) ，f ( x 。，口) ) ，则R 。( z i ，z f ) = l 。 性质3 若f ( x i ，n ) = M i n ( f ( x 1 以) ，f ( x 2 ，n ) ， ，f ( x 。，a ) ) ，且f ( a ：j ，a ) = 讹z ( 厂( a T l ，n ) 厂( 3 8 2 口) ，。( z 。，t 2 ) ) 则兄( z ，z j ) = 一1 定义6 设S = ( L ，A ，U ，厂) 为偏序信息系统，
11、定义 R 。( 嚣，工j ) R ( x i ，乃) = 型1 。矿 ( 8 ) 为偏序信息系统中对象2 7 i 在属性集A 上优于对象 z 的优势度。 R ( a T i ，z ，) 具有以下性质： 性质1 一l R ( x i ，a ：j ) 1 。 性质2z i - x j 筒R ( a ：i ，x i ) o ；2 f 以，则R ( x i ，x i ) R ( 五，x D 。 性质4 若乃 缸，则R ( a ：j ，z f ) R ( 魏，a ：D 。 定义7 设S = ( U ，A ，V ，) 为偏序信息系统， 偏序信息系统中对象的优势矩阵D = ( 口( i ，) ) 中的 任一
12、元素为 a ( i ，歹) = R ( 五，刁) ，1 i ，歹I U i ( 9 ) 定义8 设S = ( U ，A ，V ，) 为偏序信息系统， 定义 I U l R ( 五，z i ) R ( x f ) = 出话旷 ( 1 0 ) 为偏序信息系统中对象五的综合优势度。 R ( x t ) 具有如下的性质： 性质1 1 繇( z 。) 1 。 性质2 若为 z ，则R ( x i ) R ( z ，) 。 对象五的综合优势度R ( 五) 越大，则对象五越 具有优势，可以按照R ( 霸) 由大到小的顺序将对象 由优到劣排序。 4 应用实例 例1 下面给出某种打印机供应商的偏序信息 系统，其
13、中U = z 1 ，z 2 ，z 6 ，A = a l ，锄，口5 ) ( 见表1 ) 。 表1 某打印机供应商偏序信息系统表 价格 送货速度诚信度售后 产品质量 供应商 a I4 2 a 3* q 4 毛 很高很慢中差中 低快好好高 很高慢 差差 低 中慢中差中 点5 高慢好中中 高一般 中 中中 利用文 8 ，1 0 3 的方法进行排序，对象的优势矩 阵为： I 声 各对象的综合优势度R ( x ，) 为： 2 7 3 3 5 5 3 3 c；。Q啪呲。 3 3 5 5 3 3 1 8 1 8 O O n 晓 3 3 5 5 3 3 n。Q。啷呲 33O o 1 1 1 l 1 03 3
14、3 3 3 3 3 3 3 3 3 1 3 8 8 8 Q c ；n Q c ； 33 1 1 O o 1 1 l 旺 R ( z 1 ) = 0 6 1 1 ，R ( x z ) = 1 ，R ( z 3 ) = O 6 1 1 ， R ( z 4 ) = O 9 1 7 ，R ( z 5 ) = O 9 1 7 ，R ( z 6 ) = O 9 1 7 。 若“X l z f ”表示对象五比对象2 3 f 优，“工f z 52 2 62 丑 z 12 2 3 。 下面根据属性上的优势关系对表l 的数据全序 化，首先根据语义将U ( 口A ) 按由劣到优的顺序 用0 ，1 ，2 ，I UI
15、一1 来代替，表l 的偏序信息系统 转换为表2 所示的偏序信息系统，其中，属性值数值 越大表示对象在属性上越具有优势。 表2 打印机供应商偏序信息系统转换表 价格4 I送贷速度a ：诚信度巳售后a 4产品质量 供应商 a 00 101 屯 33222 毛 0l000 21lO1 1l 211 1211l 利用( 9 ) 式可以得到对象的优势矩阵为： 0 一Q 8o 1 3 3 一o 2 0 3 3 3 一o 3 o 800 9 3 3o 6o 4 6 7Q 5 一o 1 3 3 0 9 3 30一o 3 3 3 一o 4 6 7 一o 4 3 3 o 2 n 60 3 3 3Oo 1 3 3 乜l o 3 3 3 吨4 6 7o 4 6 7o 1 3 30o 0 3 3 0 3一o 5 o 4 3 3o 1一o 0 3 80 由( 1 0 ) 式计算对象五( 1 i 6 ) 的综合优势度R ( z f ) 为： R ( z 1 ) = 一O 3 0 ，R ( z 2 ) 一0 6 6 ，R ( x 3 ) = 一O 4 6 。 R ( z ) = 一O 0 6 ，R ( z 5 ) 一0 0 1 ，R ( z 6 ) 一0 0 6 。 则排序结果为：z 2 z 5 z 6 z 4 z l x s 。 通过对文E 8 ，1 0 3 的方法及本文提出的方法对例 1 的排序结果进行
