 Computer Science and Application 计算机科学与应用, 2012, 2, 271-275 http://dx.doi.org/10.12677/csa.2012.25048 Published Online December 2012 (http://www.hanspub.org/journal/csa.html) An Optimal Algorithm of Selection Books in Library Based on Rough Set and Fuzzy Set Liping Zhao1, Wenjun Liu2 1Library of Changsha University of Science and Technology, Changsha 2Department of Mathematics and Computing Science, Changsha University of Science and Technology, Changsha Email: zhlp731118@126.com, liuwjzhlp@126.com Received: Oct. 14th, 2012; revised: Oct. 24th, 2012; accepted: Nov. 11th, 2012 Abstract: Combining rough set and fuzzy set theory, an optimal decision algorithm of library to select books is put forward. During this algorithm, firstly, we construct the similarity matrix from the original information system; secondly, we classify all the programs according to fuzzy clustering; thirdly, an algorithm to choose the optimal program is put forward according to the minimum distance of weighted relative deviation. Keywords: Rough Set; Similarity Matrix; Fuzzy Set; Optimal Program 基于粗糙集与模糊集理论的图书馆最优选书算法 赵利萍 1，刘文军 2 1长沙理工大学图书馆，长沙 2长沙理工大学数学与计算科学学院，长沙 Email: zhlp731118@126.com, liuwjzhlp@126.com 收稿日期：2012 年10 月14 日；修回日期：2012 年10 月24 日；录用日期：2012 年11 月11 日 摘 要：本文将粗糙集理论与模糊集理论结合起来，给出一种图书馆最优选书算法。该算法首先从已知数据的 初始信息系统出发，计算各选书方案之间的相似度，从而构造相似矩阵，然后根据相似矩阵的传递闭包对各方 案进行聚类，并根据粗糙集理论求各属性重要性，最后利用加权综合的思想及最小距离方法选择最优买书方案。 关键词：粗糙集；相似矩阵；模糊集；最优方案 1. 引言 图书馆是社会公众文化领域的主阵地，是社会知 识信息的存储、咨询中心，也是弘扬社会主义精神文 明主旋律的重要载体。随着科技的发展，图书馆不仅 在数量上需要增加，而且图书种类也须向多样化发 展，图书馆的价值不再仅仅以其所拥有的馆藏图书的 数量来衡量，而是以它为用户提供各种形式的信息的 能力和质量来衡量。在这种新形式下，图书馆在选书 决策时，如何利用目前有限的人力、经费资源，而又 使所做决策符合读者阅读或参考，从而为广大读者提 供高质量的服务，是目前图书工作者需要认真研究和 解决的一个重要课题。 在实际过程中，由于影响选书决策的因素很多， 且大多数具有模糊性与不确定性，所以在处理这类问 题时，可以结合不确定性理论。本文就是基于这种想 法，结合粗糙集与模糊集这两种不确定性理论，给出 一种图书馆最优选书算法。 2. 预备 粗糙集理论[1]是由波兰科学家 Z. Pawlak 在1982 年提出的一种处理含糊和不确性问题的新型数学工 具。经过近三十年的发展，该理论已渗透到人工智能 Copyright © 2012 Hanspub 271  基于粗糙集与模糊集理论的图书馆最优选书算法 的各个分支，在机器学习、决策分析、过程控制、模 式识别与数据挖掘等领域取得了成功的应用[2-6]。该理 论的一个最大优点是它无须提供问题所需处理的数 据集合之外的任何先验信息，能客观有效地分析和处 理不精确、不确定与不完全数据，并从中发现隐含的 知识，揭示潜在的规律。 为了处理智能数据，粗糙集理论将知识进行符号 化，将所要研究的数据用一个信息系统的形式给出， 信息系统的基本成分是研究对象的集合，关于这些对 象的知识是通过指定对象的基本特征(属性)和它们的 特征值(属性值)来描述。信息系统的数据以关系表的 形式表示，关系表的行对应要研究的对象，列对应对 象的属性，对象的信息是通过指定对象的各属性值来 表达。 形式上， 是一类信息系统，其中 U是有限论域；A为所有属性的集合，， ,,,SUAVf a aA VV a V 是属性 a的值域； : f UA V A 是信息函数，即对于 任意的， a，有uU ,a f ua V。 对U上任意属性集 B，定义 B上的不可区分关系 如下： ind B ,,,, ,, iji j ij indBuuaBf uaf ua uu indB , 则称 与 i u j u是B不可区分的。容易证明不可区分关系 ind U上的等价关系，符号 B是 UindB(简记为 UB)表示不可区分关系 indB 在U上导出的划分， indB 中等价类称为 B基本集。 3. 聚类分析 对数据进行模糊聚类分析，一般有数据规格化、 建立模糊相似矩阵、聚类三大步。 第一步：数据规格化。在实际应用中，不同的数 据可能有不同的量纲和数量级，故在运算过程中可能 突出某数量级特别大的特性指标对分类的作用，而降 低甚至排除了某些数量级很小的指标的作用，致使对 各特性指标的分类缺乏一个统一的尺度，为了清除特 性指标单位的差别和特性指标数量级不同的影响，必 须对各指标值施行数据规格化的处理，从而使每一个 指标值统一于某种共同的数值特性范围。 设 12 ,,, n Uuuu为被分类的对象，每个对象 有m个指标描述，即对第 i个对象有 12 ,,, iii im x x1,ux(2,,in )，对应的信息系统如 表1所示。 数据规格化方法一般有[7,8]： 1) 数据标准化 ij j ij j x x x (in1,2,, m；)，其中1,2,,j 1 1n j ij i x x n ， 2 i jj 1 1n j i xx n ； 2) 均值规格化 ij ij j x x (1, 2,,in1, 2,,jm；)； 3) 中心规格化 ij ij j x xx (1, 2,,in ；)； 1, 2,,jm 4) 最大值规格化 ij ij j x x M (1, 2,,in1, 2,,jm；)，其中 12 max,, , j jj nj M xx x； 5) 极差规格化 ij j ij j j x m x M m (1,2,,in1, 2,,jm；)，其 中 12 min,, , j jj nj mxxx， 12 max,, , j jj nj M xx x； 6) 对数规格化 log ij ij x x (1, 2,,in ；)。 1, 2,,jm 第二步：构造模糊相似矩阵。建立模糊相似矩阵 的方法主要有相似系数法、距离法、贴近度法和主观 评定法。在此我们采用Hamming 距离法来构造模糊 相似矩阵，即对象 与 i u j u的相似度 1 1 1m ijik ik k rx m x 。 第三步：建立模糊等价矩阵。通过求传递闭包将 n阶模糊相似矩阵改造成为 n阶模糊等价矩阵，我们 一般采用平方法求 R的传递闭包。 Table 1. Information system 表1. 信息系统 U 1 a2 a m a 1 u11 x 12 x 1m r 2 u21 x 22 x 2m x n u1n x 2n x nm r Copyright © 2012 Hanspub 272  基于粗糙集与模糊集理论的图书馆最优选书算法 第四步：选取最佳分类阈值进行聚类。 在分类过程中，如何确定分类阈值是一个重要的 问题，在此，我们用最优分类变化率来确定分类阈值 [8]。 在等价矩阵 中，将 R R中元素 i 从大到小排列， 即12 1 k0 ，定义 i 的分类变化率 为： i C 1 1 ii iii Cnn ， 其中与分别为第 i次和第 次聚类的对象个 数。 i n1i n1i 若 max j i i CC，则认为第j次聚类的置信水平 j 为最佳值。 4. 最佳阈值 λ下的各属性权重 下面，结合模糊集与粗糙集理论，我们给出一种 求连续信息表的属性权重的方法。 输入连续信息系统 ,,,SUAVf 12 ,,, m ， ， 12 ,,, n Uuuu A aa a。 输出各属性的权重。 步骤 1 根据上述方法找出最佳分类阈值i ，即 max ij j CC，其中 1 1 j j jjj Cnn ； 步骤 2 在最佳阈值 i 下将对象进行聚类，所得 分类看做是在对象在等价关系 下的等价类； ind A 步骤 3 从A中删除属性 ( )，类似 地，在阈值 k a1,2,,km i 下将对象分类，此分类看做是在等价关 系 下的分类，若 k a ind A k aUindAUind A ，那么属性在 A中是 不可省的，属性的重要性 k a k a 1k k Uind AUind Aa aU ； 步骤 4 归一化属性重要性，得到在 i 阈值下， 属性 (k)的权重，即 k a1,2,, m 1 i im k k a w a 。 5. 图书馆最优选书方案 设 ， ,,,SUAVf 12 ,,, n Uuuu 是n个选书 方案， 12 ,,, m A aa a为对决策起重要作用的个属 性所构成的集合，则各方案可由其相应的 m个属性值 所确定，设 12 ,,, iii im uxx x( )，式 中1, 2,,inij x 表示第 i个方案的第 j个属性值，称为方案的属性 指标向量。把这 n个方案的属性指标向量作为行构成 如上述表 1所示的信息系统。 i u 在信息系统 ,,,SUAVf 中，令 0 max min jij jj xx xx ij 1, 2,, (in，)， 1, 2,,jm 其中 max1 2 max,,, j jj nj x xx x， min1 2 min,, , j jj nj x xx x， max 0 min , , jj jjj xa xxa 当属性指标 当属性指标 是正指标， 是负负指。 这里正指标是指因素指标值越大方案越优的因素指 标，负指标是指因素指标值越小方案越优的因素指 标。称 ij 为相对偏差值。称 0 j x 为属性 j a的标准值， 而称 00 0 012 ,,, m x xux为标准值向量。 由上述 nm 个相对偏差值 作为元素构成一个 模糊矩阵 ij 1 2 m m nm 11 12 21 22 12nn 叫做相对偏差矩阵。 对于给定的 n种选书方案，若这个方案的加权相 对偏差距离与标准值向量的距离最小，则我们选择这 个方案为最优选择方案。根据这种思想，我们可得如 下最优购书算法： 步骤 1 根据前面的算法确定每个属性 j a的权重 j w； 步骤 2 根据公式 2 ij 1, 2,, 0 u 01 ,m ii j j dduu w in ， 计算每个方案与标准值向量的加权相对偏差距 离； i u 步骤 3 根据最小加权相对偏差距离确定最优方 案，即若 n dk u 12 min, , , k ddd，则 选择为最优方 案。 6. 实例分析 下面我们用一个例子说明上述算法的有效性与 Copyright © 2012 Hanspub 273  基于粗糙集与模糊集理论的图书馆最优选书算法 Copyright © 2012 Hanspub 274 Table 2. Expert scoring information system 可行性。某高校图书馆计划新购一批计算机图书。计 算机科学系王老师根据多年的教学经验，结合学生的 兴趣爱好，计划从 ,,,, ,,, A BCDEFGH ,,,EFGH 3 a4 a 8类图书中选 择一类最优的图书，即选择方案是： 。按照图书价格( )、教 学 效果( )、科研价值( )、售后服务( )、学生爱好 ( )等因素来进行选取。由于影响图书的几个指标有 很强的专业性，因此采用专家主观评分法，对 8类图 书的基本情况进行打分，结果如表2所示。 ,,,,UABCD 2 a 5 a 1 a 表2. 专家打分情况信息表 U 1 a2 a3 a 4 a 5 a 1 u0.10.20.3 0.3 0.2 2 u0.30.20.4 0.2 0.1 3 u0.40.50.3 0.5 0.3 4 u0.50.30.2 0.1 0.5 5 u0.20.10.5 0.4 0.2 6 u0.30.30.5 0.5 0.3 7 u0.50.40.4 0.3 0.4 8 u0.20.20.3 0.2 0.3 由于此数据都在 0,1 之间，且量纲相同，我们选 择极差规格化，然后，根据公式 1 1 1m ijik jk k rx m x ， ij nn r R及求得它的传递闭包 分别如下： R 计算 与 i u j u之间的相似度，构造相似度矩阵 1 0.730.550.430.720.570.530.85 0.7310.48 0.470.68 0.630.60.78 0.55 0.4810.480.47 0.72 0.680.6 0.430.470.4810.250.40.67 0.58 0.72 0.68 0.47 0.2510.750.480.67 0.570.63 0.720.40.7510.63 0.62 0.530.60.68 0.67 0.48 0.6310.58 R 0.85 0.780.60.58 0.67 0.62 0.581 10.780.720.670.720.72 0.68 0.85 0.7810.720.67 0.720.720.680.78 0.720.7210.670.720.720.680.72 0.670.67 0.6710.67 0.67 0.67 0.67 0.72 0.72 0.72 0.6710.75 0.680.72 0.72 0.72 0.72 0.67 0.7510.68 0.72 0.68 0.68 0.68 0.67 0.68 0.6 R 8 1 0.68 0.85 0.780.72 0.670.72 0.72 0.681 下面，利用最优分类变化率找最佳阈值。 根据模糊等价矩阵 ，得： R 当0.85 1 时， 1 dAu2345678 ,,,,,,,Uinuuuuuuu； 当0.78 0.85 时， 234567 , ,, , ,Uindu uuuuu 18 ,,A uu； 当0.75 0.78 时， 12 ,,dAuuu834567 , ,, ,,Uin uuuuu； 当0.72 0.75 时， 12 ,,Auu u834567 ,,,,,Uinduuu uu； 当0.68 0.72 时， 123568 4 7 ,,,,,,,Uind Auuuuuuuu； 当0.67 0.68 时， 123 ,,dA uuu5678 4 ,,,,,Uinuuuuu 67 ； 当00. 时， UindA U。 由于所在对象各自成类或全部对象并入一类没 有实际意义，根据最佳分类阈值的选取方法，可得 0.72 为最佳阈值。此时 123568 4 7 ,,,,,,,Uind Auuu uuuuu； 从A中分别删除 ，在阈值 12345 ,,,,aaaaa 0.72 下，用相同的方法，可得  基于粗糙集与模糊集理论的图书馆最优选书算法 11283456 ,,,,, ,,UindAa uuuuuuuu 7 ， 212835647 ,,, ,,,,UindAauuuuu uuu ， 312583647 ,,,, ,,,UindAauu uuuuuu ， 412568 347 ,,,,, ,,UindAauu uu uuu u ， 5 12834567 ,,,,, ,,UindAauu uuuu uu ， 所以 ， (0.1875,0. 第一个图书价 格外，其 0 0.75 0.67 0.5 0.75 1235 0.75aaaa 41，可得各个属性的权重为： a 1875,0.1875 ,0 .25 ,0.1 875 )。 显然对于考虑的这些因素指标除 余都是正指标，由信息系统得 ，相对偏差矩阵为： 00.1,0.5,0.5,0.5,0.5u 0.5 0.75 0.33 0.75 1 0.75 0 0.67 0 0.5 1 0.5 1 1 0 0. 0. 0. 0. 0. 251 0 2575 0.5 0.5 0 0 0.5 1 0.25 330.5 0.25 250.75 0.67 0.75 0.5 据公式 根 52 01 , ii jij j dduu w 1,2,, 8i， 求得每种选择与标准值向量 的加权相对偏差距离 0 u 为： 1234 0.266; 0.321;0.210; 0.376;dd dd 5678 0.247; 0.162; 0.243; 0.286.dddd 因为最小，所以认为方案 6最优，即购买第 6 学技术的发展，社会对人才的要求最来越 高， 参考文献 (References) aspects of reasoning about data. Doric Publishers, 1991. 7): 3356- ]. 情报学报, 2005, 1: 91-100. 报, 2009, 32(7): 1229-1243. 6 d种书 籍最合适。 7. 小结 随着科 而图书馆的建设与发展是提高人们素质的一个重 要基础。在新形势下，各图书馆如何针对自身的特色， 选择适合读者研究需要和阅读参考的图书，是图书馆 面临的一项重要任务。本文结合模糊集与粗糙集理 论，对拟选图书根据给定的条件进行计算分析，为馆 员提供最佳选择方案，从而让馆员在有限精力的条件 下选择确定合适图书。节省了馆员的时间，同时也可 以使做出的购书决策更全面地符合实际需要。 [1] Z. Pawlak. Rough set: Theoretical drecht: Kluwer Academ [2] Y. Y. Yao, Y. Zhao. Attribute reduction in decision-theoretic rough set models. Information Sciences, 2008, 178(1 3373. [3] 胡清华, 谢宗霞, 于达仁. 基于粗糙集加权的文本分类方法 研究[J [4] 王国胤, 张清化. 不同知识粒度下粗糙集的不确定性研究[J]. 计算机学报, 2008, 31(9): 1588-1598. [5] 史忠植. 知识发现(第二版)[M]. 北京: 清华大学出版社, 2011. [6] 王国胤, 姚一豫, 于洪. 粗糙集理论与应用研究综述[J]. 计 算机学 [7] 张振良. 模糊集理论与方法[M]. 武汉: 武汉大学出版社, 2010. [8] 梁保松, 曹殿立. 模糊数学及其应用[M]. 北京: 科学出版社, 2007. Copyright © 2012 Hanspub 275 |