第2期 张继福，等：约束概念格及其构造方法 ·37· 大尺度结构.LAMOST计划的主要目标是用来进 由表23中的实验结果可以看出，1)在相同形 行大规模光谱巡天，预计从2006年底起，每个观测 式背景下，约束概念格比一般概念格的结点数少，建 夜晚将收集2~4万条光谱的数据，LAMOST所观 格时间短.所以，利用背景知识，算法CCLA可以有 测到的光谱数据容量可达4TG1.如何利用数据挖 效地减少概念格结点数，节省概念格构造所用的时 掘技术从海量天体光谱数据中发现未知的、特殊的 间.因此，约束概念格利用用户提供的背景知识，可 天体和天体规律是值得研究和探索的新应用领域. 以降低概念格的时空复杂性.2)随着背景知识对概 在PentiumII-1.0GCPU,256MB内存，Win- 念格结点约束程度的加大，其满足约束的格结点个 dows2000操作系统，DBMS为ORACL E9i,用Vis 数和相应的建格时间将明显减低.3)由于背景知识 ual Basice6.0实现了CCLA算法.选用2500条M、 描述了用户感兴趣或不感兴趣的内涵，因此约束概 K、G、F、AB、O等类恒星光谱数据为数据集，经过 念格提高了概念格的针对性和实用性 以下预处理后构成该实验中的形式背景：1)选定间 隔为40的100个波长3510,3550，…，8330A,依 6结束语 据流量、峰宽和形状，将每个波长离散化为13种值； 在应用概念格进行知识提取时，一些概念格内 2)恒星的任意类型温度等间隔离散化为3种，7类 涵的属性组合，并非用户都感兴趣.同时，随着要处 恒星温度被离散化为21种值：3)根据恒星的光度、 理的数据量的激增，概念格的构造时间长，占用大的 化学丰度、微湍流、其他参数等间隔离散化为3种 存储空间.因此，为了提高概念格的构造效率，减少 值：4)根据恒星的物理参数，等间隔离散化为5种 建格的时间复杂度和空间复杂度，提出了一种全新 值 的概念格结构：基于背景知识的约束概念格.利用背 如果用户对恒星温度和化学分度组成的内涵感 景知识来指导概念格的构造，使构造出的概念格更 兴趣，对物理4和微湍流1组成的内涵不感兴趣，其 具有针对性和实用性.进一步工作是基于约束概念 约束概念格的结点个数和建格时间如表23所示 格的知识提取及在天体光谱数据知识发现中的应 用 表2CLA算法实验结果1 Table 2 The experiment result 1 of CCLA algorithm 参考文献： 背景知识 结点数 建格时间/s [1]WILLE R.Restructuring lattice theory:an approaches 中一般概念格) 6713 2823 based on hierarchies of concepts[A].In:Rival I ed.Or- 温度aV化学丰度2 3860 949 dered Sets[M].Dordrecht Reideal,1982. 温度a 1002 121 [2]GODIN R,MISSAOUI R.An Incremental concept for- mation approach for learning from databases [J].Theo- 化学丰度2 3351 851 retical Computer Science,1994,133(2):387-419. 温度a化学丰度2 473 71 [3]BEL EN D A,PEDRO A.Formal concept analysis as a support technique for CBR [J ]Knowledge-based Sys- 表3 CA算法实验结果2 tems,2001,14(3):163-171. Table 3 The experiment result 2 of CCLA algorithm [4]YOUNG P.Software retrieval by samples using concept 背景知识 结点数 建格时间/s analysis [J].The Journal of Systems and Computer, 中一般概念格)】 2000,54(3):179-183. 6713 2823 7物理4Vㄣ微湍流 [5]CHU S,CESNIK B.Knowledge representation and re- 16319 2760 trieval using conceptual graphs and free document self- 微湍流1 6090 2479 organisation techniques[J ]International Journal of Med- 7物理4 4122 879 ical Informatics,2001,62(2/3):121-33. 7物理4八7微湍流1 3665 732 [6]KENT R E.Rough concept analysis[A].In:Ziarko W P ed.Rough Sets,Fuzzy Sets and Knowledge Discovery 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net大尺度结构. LAMOST 计划的主要目标是用来进 行大规模光谱巡天 ,预计从 2006 年底起 ,每个观测 夜晚将收集 2～4 万条光谱的数据 ,LAMOST 所观 测到的光谱数据容量可达 4 T G [15 ] . 如何利用数据挖 掘技术从海量天体光谱数据中发现未知的、特殊的 天体和天体规律是值得研究和探索的新应用领域. 在 PentiumIII2110 G CPU , 256MB 内存 , Win2 dows2000 操作系统 ,DBMS 为 ORACL E9i ,用 Vis2 ual Basic610 实现了 CCLA 算法. 选用 2 500 条 M、 K、G、F、A 、B、O 等类恒星光谱数据为数据集 ,经过 以下预处理后构成该实验中的形式背景 :1) 选定间 隔为 40 的 100 个波长 3 510 ,3 550 , …, 8 330 A ° ,依 据流量、峰宽和形状 ,将每个波长离散化为 13 种值 ; 2) 恒星的任意类型温度等间隔离散化为 3 种 ,7 类 恒星温度被离散化为 21 种值 ;3) 根据恒星的光度、 化学丰度、微湍流、其他参数等间隔离散化为 3 种 值 ;4) 根据恒星的物理参数 ,等间隔离散化为 5 种 值. 如果用户对恒星温度和化学分度组成的内涵感 兴趣 ,对物理 4 和微湍流 1 组成的内涵不感兴趣 ,其 约束概念格的结点个数和建格时间如表 2、3 所示. 表 2 CCLA算法实验结果 1 Table 2 The experiment result 1 of CCLA algorithm 背景知识 结点数 建格时间/ s Ф(一般概念格) 6 713 2 823 温度 a ∨化学丰度 2 3 860 949 温度 a 1 002 121 化学丰度 2 3 351 851 温度 a ∧化学丰度 2 473 71 表 3 CCLA算法实验结果 2 Table 3 The experiment result 2 of CCLA algorithm 背景知识 结点数 建格时间/ s Ф(一般概念格) 6 713 2 823 ┓物理 4 ∨┓微湍流 16 319 2 760 ┓微湍流 1 6 090 2 479 ┓物理 4 4 122 879 ┓物理 4 ∧┓微湍流 1 3 665 732 由表 2、3 中的实验结果可以看出 ,1) 在相同形 式背景下 ,约束概念格比一般概念格的结点数少 ,建 格时间短. 所以 ,利用背景知识 ,算法 CCLA 可以有 效地减少概念格结点数 ,节省概念格构造所用的时 间. 因此 ,约束概念格利用用户提供的背景知识 ,可 以降低概念格的时空复杂性. 2) 随着背景知识对概 念格结点约束程度的加大 ,其满足约束的格结点个 数和相应的建格时间将明显减低. 3) 由于背景知识 描述了用户感兴趣或不感兴趣的内涵 ,因此约束概 念格提高了概念格的针对性和实用性. 6 结束语 在应用概念格进行知识提取时 ,一些概念格内 涵的属性组合 ,并非用户都感兴趣. 同时 ,随着要处 理的数据量的激增 ,概念格的构造时间长 ,占用大的 存储空间. 因此 ,为了提高概念格的构造效率 ,减少 建格的时间复杂度和空间复杂度 ,提出了一种全新 的概念格结构 :基于背景知识的约束概念格. 利用背 景知识来指导概念格的构造 ,使构造出的概念格更 具有针对性和实用性. 进一步工作是基于约束概念 格的知识提取及在天体光谱数据知识发现中的应 用. 参考文献 : [ 1 ] WILL E R. Restructuring lattice theory : an approaches based on hierarchies of concepts[ A ]. In :Rival I ed. Or2 dered Sets[ M]. Dordrecht : Reideal ,1982. [2 ] GODIN R , MISSAOU I R. An Incremental concept for2 mation approach for learning from databases [J ] . Theo2 retical Computer Science , 1994 ,133 (2) :387 - 419. [3 ]BEL EN D A , PEDRO A. Formal concept analysis as a support technique for CBR [J ]. Knowledge2based Sys2 tems ,2001 ,14 (3) :163 - 171. [4 ] YOUN G P. Software retrieval by samples using concept analysis [J ] . The Journal of Systems and Computer , 2000 ,54 (3) :179 - 183. [5 ]CHU S , CESNIK B. Knowledge representation and re2 trieval using conceptual graphs and free document self2 organisation techniques[J ]. International Journal of Med2 ical Informatics ,2001 ,62 (2/ 3) :121 - 33. [6 ] KEN T R E. Rough concept analysis[ A ]. In : Ziarko W P ed. Rough Sets , Fuzzy Sets and Knowledge Discovery 第 2 期 张继福 ,等 :约束概念格及其构造方法 · 73 · © 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net