（计算机应用技术专业论文）基于约束概念格的恒星光谱数据分类规则挖掘系统.pdf

中文摘要 概念格是一种用于数据分析和知识提取的有效形式化工具，具有完备性和精确 性等特征。约束概念格是利用用户对数据集中属性的兴趣程度等作为背景知识，来 指导概念格的构造，从而使构造出的概念格结构更具有针对性和实用性。本文以国 家重大科学工程l a m o s t 项目为背景，对约束概念格的渐进式构造、基于约束概念 格的分类规则提取进行了研究，其主要研究成果如下： 第一、基于剪枝的约束概念格渐进式构造。该算法利用父子结点内涵的严格单 调关系，采用剪枝技术消除了渐进式构造过程中存在的冗余信息，即减少了新增对 象属性集与原概念格结点内涵的比较次数，从而提高约束概念格的构造效率。以恒 星光谱数据作为形式背景，实验验证了算法的正确性和有效性。 第二、基于约束概念格的分类规则提取算法。首先，将数据集中的属性分为条 件属性和分类属性，利用分类属性的不同取值将数据集分为m 个等价划分g i ( 1 i m ) ，并采用条件属性构造约束概念格；其次，自上向下扫描格约束概念格结 点，利用外延支持度阈值和划分支持度，提取出分类规则；最后，采用u c i 标准数 据集和恒星光谱数据作为形式背景，实验验证了该算法具有较高的分类正确率。 第三、在上述研究的基础上，采用v c + + 6 0 和o r a c l e9 i 作为开发工具，设计并 实现了基于约束概念格的恒星光谱分类规则挖掘原型系统。系统运行结果表明，采 用该系统挖掘出的分类规则，实现海量恒星光谱数据自动分类是可行的和有价值的。 关键词：约束概念格；剪枝；渐进式；分类规则；外延支持度；划分支持度；恒星 光谱数据 a b s t r a c t c o n c e p tl a t t i c e ，w i t hc h a r a c t e r i s t i c so fc o m p l e t e n e s sa n da c c u r a c y , i sa n e f f e c t i v et o o lf o rd a t aa n a l y s i sa n dk n o w l e d g ed i s c o v e r y t a k i n gc u s t o m e r s i n t e r e s ta b o u td a t as e ta sb a c k g r o u n dk n o w l e d g e ，a n dg u i d i n gt h ep r o c e s so f c o n s t r u c t i n gc o n c e p tl a t t i c e ，an e wc o n c e p tl a t t i c e ( c o n s w a i n e dc o n c e p tl a t t i c e ) i sp r e s e n t e d ，s ot h a tt h eu t i l i t ya n d p e r t i n e n c eo fc o n c e p tl a t t i c ec o n s t r u c t i o n a r e i m p r o v e d i nt h i sp a p e r , t h ei n c r e m e n t a lc o n s t r u c t i o na l g o r i t h ma n d c l a s s i f i c a t i o nr u l ea c q u i s i t i o na l g o r i t h mb a s e do nc o n s t r a i n e dc o n c e p tl a t t i c e a r es t u d i e db yt a k i n gl a m o s ta sb a c k g r o u n d t h em a i nr e s e a r c hw o r k sc a n b es u m m a r i z e da sf o l l o w s ： f i r s t ，a ni n c r e m e n t a lc o n s t r u c t i o na l g o r i t h mo fc o n s t r a i n e d c o n c e p t l a t t i c eb a s e do np r u n i n gi s p r e s e n t e d b ym a k i n gu s eo ft h er i g o r o u s m o n o t o n er e l a t i o nb e t w e e nf a t h e rc o n c e p t si n t e n ta n dc h i l dc o n c e p t si n t e n t ， t h er e d u n d a n ti n f o r m a t i o ni nt h ec o n s t r u c t i o np r o c e s si se l i m i n a t e db yu s i n g p r u n i n gt e c h n o l o g y , n a m e l y , t h ec o m p a r a t i v eo p e r a t i o n sb e t w e e nt h ei n t e n t s a r ed e c r e a s e d ，s ot h a tt h ee f f i c i e n c yo fc o n s t r u c t i n gt h ec o n s t r a i n e dc o n c e p t l a t t i c ei s i m p r o v e d t h ee x p e r i m e n tr e s u l t sv a l i d a t et h ec o r r e c t n e s sa n d v a l i d i t yo ft h ea l g o r i t h mb yt a k i n gt h ec e l e s t i a ls p e c t r u md a t aa st h ef o r m a l c o n t e x t s e c o n d ，ac l a s s i f i c a t i o nr u l ea c q u i s i t i o na l g o r i t h mb a s e do nc o n s t r a i n e d c o n c e p tl a t t i c ei sp r e s e n t e d f i r s t l y , t h ea t t r i b u t e si nd a t as e ta r ed i v i d e di n t o c o n d i t i o na t t r i b u t e sa n dc l a s s i f i c a t i o na t t r i b u t e s a c c o r d i n gt ot h ed i f f e r e n t v a l u e so fc l a s s i f i c a t i o n a t t r i b u t e ，t h ed a t as e ti sd i v i d e di n t oe q u i v a l e n c e p a r t i t i o ng i ( 1 i m ) a n dt h ec o n s t r a i n e dc o n c e p tl a t t i c ei sc o n s t r u t e db y u s i n gt h ec o n d i t i o na t t r i b u t e s s e c o n d l y ，s c a n n i n ga l ln o d e so ft h ec o n s t r a i n e d c o n c e p tl a t t i c ef r o mt o pt od o w nb yu s i n gt h ec o n c e p to fe x t e n ts u p p o r ta n d p a r t i t i o ns u p p o r t ，c l a s s i f i c a t i o nr u l e sa r em i n e d f i n a l l y , t h ee x p e r i m e n t r e s u l t sv a l i d a t et h ea l g o r i t h mh a st h eh i g h e rc l a s s i f i c a t i o nc o r r e c t n e s sb y t a k i n gt h eu c id a t as e t sa n ds t a rs p e c t r u md a t aa st h ef o r m a lc o n t e x t s i i i t h i r d ，o nt h eb a s i so fa b o v e ，t h em i n i n gs y s t e mo fc l a s s i f i c a t i o nr u l e s f o rs t a rs p e c t r ad a t ab a s e do nc o n s t r a i n e dc o n c e p tl a t t i c ea r ed e s i g n e da n d r e a l i z e db yu s i n gv c + + 6 0a n do r a c l e9 ia sd e v e l o p m e n tt o o l s t h er u n n i n g r e s u l t ss h o wt h a tt h ec l a s s i f i c a t i o nr u l e sm i n e d b yt h es y s t e ma r ef e a s i b l ea n d v a l u a b l ef o ra u t o c l a s s i f i c a t i o no fm a s s i v es t a rs p e c t r ad a t a k e yw o r d s ：c o n s t r a i n e dc o n c e p tl a t t i c e ；p r u n i n g ；i n c r e m e n t a lc o n s t r u c t i o n ； c l a s s i f i c a t i o nr u l e s ；p a r t i t i o ns u p p o r t ；e x t e n ts u p p o r t ；s t a rs p e c t r ad a t a i v 声明尸明 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的科研成果。对本文的研究 做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的 法律责任由本人承担。 作者签名： 墨主季 日期：幽：皇：翌 关于学位论文使用权的说明 本人完全了解太原科技大学有关保管、使用学位论文的规定，其 中包括：学校有权保管、并向有关部门送交学位论文的原件、复印 件与电子版；学校可以采用影印、缩印或其它复制手段复制并保存 学位论文；学校可允许学位论文被查阅或借阅；学校可以学术交 流为目的，复制赠送和交换学位论文；学校可以公布学位论文的全 部或部分内容( 保密学位论文在解密后遵守此规定) 。 作者签名： 曼= ! ! 圣 日期：一堡2 ：圭：望 一一 导师签名：! 盐蠢鍪 日期： 1 2 ：竺：竺 导师签名：! 彗叠釜 日期： 1 2 ：竺：竺 第一章绪论 第一章绪论 1 1 数据挖掘 近十几年来科学高速发展的同时，社会和经济都取得了很大进步。与此同时， 众多知识领域都涌现出大量数据，例如人类对宇宙世界的探索，金融行业中的巨额 交易等。因此，“数据缺乏”不再是人们面临的关键问题，如何更有效地利用这些海 量数据成为目前急迫解决的问题。计算机技术的迅猛发展推动了数据库技术的发展， 使得处理大量数据成为可能，但是随着数据量的急剧增长，目前的数据库系统不能 有效发现数据之间的关联性，同时也不能根据隐含在数据间的规律来预测未来的发 展趋势，因此导致了“数据爆炸，但是知识贫乏”的不合理现象出现。同样，传统 的统计技术也面临着极大挑战，这就急需使用一些新的方法来处理这些海量数据。 在这样的背景下，数据挖掘技术应运而生，并已在其一些应用领域中显示出了强大 的生命力。数据挖掘的蓬勃发展使得数据处理技术走向一个崭新的阶段，不仅能实 现对历史数据的查询操作，而且还能发现隐藏在数据中的未知规律，进行更高层次 的分析，便于人们能够利用这些分析结果更好地做出理想决策、预测未来的发展趋 势等。 1 1 1 数据挖掘的概念和定义 数据挖掘( 通常又被称作数据库中的知识发现) ，就是从大量数据中获取可信 的、新颖的、有效的、并能被人理解的模式的处理过程【1 1 。即，数据挖掘就是从大量 数据中提取或“挖掘”知识 2 1 。典型的数据挖掘系统具有以下主要成分：( 1 ) 数据库 或数据仓库服务器；( 2 ) 数据挖掘引擎；( 3 ) 数据库、数据仓库或其它信息库；( 4 ) 知识库；( 5 ) 图形用户界面；( 6 ) 模式评估模块【2 】。 数据挖掘的一般步骤可用图1 1 进行表示： 囡一医画寸叫垂运乎 巫一困 图1 - 1 数据挖掘的一般流程 f i g u r e1 - 1g e n e r a lf l o wo fd a t am i n i n g 1 、问题定义：根据实际情况，明确定义出亟待解决的相关问题，以准确确 定数据挖掘的目的。 2 、数据选取：选择合理的源数据库，并根据实际需求从数据库中提取出有 用的数据。源数据库的选择标准以及数据抽取的具体原则应根据特定系统的任 务来确定。 1 基丁约束概念格的恒星光谱数据分类规抛0 挖掘系统 3 、数据预处理：对从源数据库中抽取的数据进行处理，包括去除噪声、填 补空缺、删除重复记录和无效数据等，不仅使得数据前后一致，满足数据的完 整性约束，更要满足数据挖掘所提出的要求。 4 、数据挖掘：根据用户提出的需求，结合数据的特点和数据功能的类型， 选择合理算法对经过预处理的数据集进行运算处理，提取出用户所需要的知识 和规律来解决提出的实际问题。 5 、知识评估：通过特定的方式对前一阶段提取的知识和规律进行表示，经过评 估后，判断这些知识和规律是否达到用户的要求，与此同时，查询这些结果中是否 存在冗余或无关信息，并将冗余信息消除。评价过程中如果没有达到用户要求，这 时需要将整个过程回退到前面的阶段，重新调整参数或算法，直到获取到用户满意 的结果。最后将获得的结果以可视化模式或另一种用户容易理解的模式显示给用户， 并将其集成到企业的智能系统中。 1 1 2 数据挖掘的技术 常用的数据挖掘技术有：决策树、遗传算法、粗糙集、神经网络、模糊集、概 念格等【2 】。 1 、决策树：通过扫描决策树可以发现训练集中的分类知识，其核心是如何使构 造的决策树精度高、规模小。决策树中最上面的结点为决策树的起始点，称为根结 点，中间的结点称为决策结点，最终到达的是没有任何分枝的结点，称为叶子结点。 每个决策结点代表一个问题或者决策，通常对应于待分类对象的属性，每个叶子结 点代表一种可能的分类结果，其中的所有实例都是相同类型。从根结点开始，沿着 决策树自顶向下遍历，根据每个决策结点的不同输出，导致不同的分枝，依次递归 扫描，直到到达叶子结点。在构造好的决策树上通过剪去影响精度的分枝，以此来 增加决策树的准确性和构造效率。决策树的主要优点是描述简单，分类速度快， 适合大规模的数据处理。 2 、遗传算法：其思想来源于生物的自然选择与遗传的机理，在此基础上采用随 机搜索算法仿生达到全局优化的一种方法。其过程分为以下几步：第一，对需要求 解的问题进行编码，产生初始群体；第二，计算每个个体的适应程度；第三，对个 体进行染色体的复制、变叉、突变等各种处理操作，产生新个体；第四，反复重复 上述三个过程，直到得到最佳或较佳个体为止。遗传算法具有隐含并行性以及易于 和其它模型结合等特征，因此成为了数据挖掘的常用方法。但遗传算法相对比较复 杂，而且收敛于局部极小的较早收敛问题还很难解决，因此在应用中受到一定限制。 2 第一章绪论 3 、粗糙集：是一种研究不确定性知识的数学工具，由以波兰数学家p a w l a k 为代表的研究人员于1 9 8 2 年首次提出，它能针对各种不完备信息进行有效地分析和 处理，从而发现存在的未知知识，揭示潜在的规律。其主要优点是需要输入的信息 的表达空间简化，算法简单，易于操作且不需要预先给定附加信息，直接从给 定问题出发，通过不可分辨关系和不可分辨类来确定问题的近似域，从而找出内在 规律。其不足是它的数学基础是集合论，很难直接处理连续的属性。而现实的信 息表中连续属性是普遍存在的，因此连续属性的离散化成为将粗糙集理论实用 化的一个瓶颈。 4 、神经网络：是为完成分类、聚类等多种挖掘任务而采用训练来学习的非线性 预测模型，具有容错能力高、自组织自适应性强、并行处理及其强鲁棒性的特 征，因此是一种非常适合解决数据挖掘相关问题的合理方法。但该方法具有“黑 箱效应 的不足，使得人们难以理解中间的网络学习和决策过程。 5 、模糊集：模糊集是一种用精确的数学语言对模糊性进行描述的方法。在传统 的集合论中，元素与集合具有属于或者不属于的关系，其界限是清晰的。而模糊集 理论中的元素与集合之间除了这两种关系之外，元素还能属于某个或某几个集合， 其程度不同，边界是模糊的。通常模糊集理论中采用隶属度来描述事物之间的不 同关系。从精确现象发展到模糊现象，模糊数学的出现把数学的应用领域扩大了。 利用模糊集理论可以对现实生活中的不确定问题进行模糊决策、模糊评判、模 糊模式识别等。 6 、概念格：又称为形式概念分析，是1 9 8 2 年由德国的w i l l e r 首先提出的【3 j 。概 念格中每个结点是一个形式概念，由外延和内涵两部分组成。外延是拥有共同属性 的对象的集合，而内涵是对概念的描述，由概念所覆盖对象的共有属性组成。概念 格的这种结构及其相应的h a s s e 图形式，反映了一种概念上的层次结构，体现了这些 概念结点之间的泛化和特化的关系。概念格具有完备性、直观性等特点，因此成为 数据分析的一种有力工具，并已成功应用于众多领域。 1 1 3 数据挖掘的功能 数据挖掘任务一般可以分为两大类：描述和预测。描述性数据挖掘任务主要刻 画数据库中数据的一般特性，预测性数据挖掘任务则主要是通过对已有数据的推断 结果，对未来进行预测。数据挖掘的功能就是为了完成这样一些任务而指定采用的 模式类型，具体介绍以下几种类型：关联分析、聚类、分类、预测、孤立点分析等【2 j 。 1 、关联分析：是针对数据库中属性与属性之间存在的依赖关系进行的分析，可 3 基于约束概念格的恒星光谱数据分类规则挖掘系统 分为简单关联、时序关联、因果关联、数量关联等很多种。这些关系是现实世界中 事物之间的必然联系，其关系是复杂的，而且大部分事先是不知道的、潜在的、隐 藏的，需要通过对数据库中数据的关联性具体分析来获得。关联规则挖掘的目的就 是要找出数据与数据之间的隐藏的关联信息，这对现实生活中的商业决策具有重要 意义。在关联规则挖掘中，为了发现有意义的关联规则，需要定义最小支持度和最 小可信度两个参数，并给定其阈值。最小支持度是事务的属性在数据库中出现的概 率所要达到的最低限度，最小可信度是事务的属性与属性之间的紧密程度。为了使 得所挖掘出的关联规则更符合实际要求，还可以引入兴趣度、相关性等参数，来 加强关联规则的针对性和高效率。 2 、聚类：聚类就是将数据库中的事物按照相似程度进行分组，形成多个类，使 得同一类中的事物之间的差别尽可能小，而不同类之间的事物差别尽可能大。聚类 属于无指导学习，它是通过对数据的分析生成一些类标识，这些类标识没有事先定 义，也没有对实例进行事先训练，其结果是一个概念。当一组数据对象可以由一个 概念( 区别于其它概念) 来描述时，就形成一个簇，因此，又被称为概念聚类。聚 类分析可以建立宏观概念，发现数据的分布模式，以及数据各属性之间可能存 在的相互关系。通过聚类分析可以将数据库中的记录划分为一系列有意义的子集， 进而实现对数据的详细分析。 聚类技术主要以统计方法、机器学习、神经网络等方法为基础。典型的聚类方 法是基于几何距离度量的聚类方法，其中包括曼哈坦距离、欧式距离、明考斯基距 离等。为解决大型数据库或高维数据库等聚类挖掘问题，可将多种技术结合使用生 成综合性聚类方法进行探索。 3 、分类：分类与聚类正好相反，它是一种有指导的学习，需要提供训练数据集， 并对每个训练样本的数据对象预先定义类标识。分类的目的是首先学习一个分类模 型，然后通过该模型将数据库中的每条记录映射到已给定类别中。学习过程分两步： 第一建立模型，第二使用模型进行分类。建立模型是通过分析数据库中事物的属性 来构造分类模型，使用模型进行分类是在测试上述模型的准确率之后，用它对类标 识未知的对象进行分类。分类模型通常可以用分类规则、判定树、数学公式或神经 网络的形式表示。 分类的常用方法主要包括决策树、贝叶斯网络、神经网络、粗糙集、概念格等。 对于分类，主要标准是提高分类预测准确率。 4 、预测：预测是通过对历史数据的研究，找出数据之间的内在规律，推导出历 4 第一章绪论 史数据中可能存在的变化趋势，最终建立一个模型，并用这些模型对未来的未知数 据的种类及特征进行预测。预测是构造和使用模型评估无标识标本类，或评估给定 样本可能具有的属性值或值区间，可以使用线性回归、非线性回归和多元回归等预 测法预测连续值。预测通常采用预测方差来度量精确度和不确定性。 5 、孤立点分析：孤立点挖掘由一些不符合历史数据中存在的一般规律或特征的 数据对象组成，也被称为离群数据。孤立点分析是对于一个具有m 个数据点或对象 的集合，以及预期己知的孤立点数目k ，挖掘出与剩余数据明显不一致的头k 个对象。 孤立点数据挖掘问题可以分解成两个子问题：( 1 ) 确定孤立点的特征，即什么样的 数据被认为是孤立点；( 2 ) 如何找到孤立点，即采用什么样的方法来挖掘孤立点。 孤立点的挖掘方法主要是基于统计，基于距离和基于偏移三种方法。孤立点挖 掘有着广泛的应用，例如信用卡欺骗检测，不寻常信用卡使用情况的探测等。 1 1 4 数据挖掘的应用 数据挖掘技术的应用非常广泛。只要数据库有分析的价值与需求，就可利用数 据挖掘工具进行有目的的分析，其应用主要存在于金融机构和保险业、商场零售业、 制造业、通讯电信业等领域中：1 、证券公司可以利用数据挖掘技术建立预测模型， 并采用模型预测股东投资中可能存在的欺诈行为，由此来避免道德风险引起的商业 风险，从而维护证券公司的利益和权益；2 、超市商场可以通过数据挖掘找到顾客经 常购买商品的时间、类型以及商品与商品之间的联系，从而发现顾客购买商品的习 惯和爱好，从而调整商品的摆放顺序、更换商品的类型以及调整促销手段，以此提 高销售额、增强竞争力；3 、制造业中，为提高产品质量就必须对产品的生产和测试 数据进行统计，采用数据挖掘对这些统计数据进行分析，可以利用孤立点分析找出 劣质产品及其产生原因，为改善生产方式、调整生产策略提供技术支持；4 、由于电 信业的不断兴起和通信技术的发展，电信市场正迅速扩张，并且竞争越来越激烈， 使用数据挖掘可以加快效率和准确率，更好地利用资源，提高服务质量，在众多竞 争者中生存。 世界上很多知名公司运用数据挖掘技术走向了成功，这也体现了数据挖掘的强 大生命力：美国运通公司通过数据挖掘工具对客户信用卡业务的数据库进行挖掘， 制定了一系列促销活动，譬如顾客如果利用客户信用卡在相同地方购买相同或相似 产品的话，将会享受较大折扣，这样既可以吸引顾客有选择性地购买商品、增加购 买量，也可以提高信用卡的使用率；美国亚特兰大的a u t o t r a d e r c o m 网站之所以能 5 基丁约束概念格的恒旱光谱数据分类规则挖掘系统 成为世界上最大的汽车销售站点，这是因为他们运用s a s 软件工具对数据进行挖掘 分析，挖掘出了不同客户对不同汽车的喜爱程度，并收集了大量客户的服务需求， 从而改善销售方式，并不断满足客户的新需求，并设立特定服务区，为其最终成功 奠定了基础；世界上著名的金融信息服务公司r e u t e r e s 利用s p s s 的数据挖掘工具 s p s s c l e m e n t i n e ，提高了对外部搜集的数据错误的检测效率，保证了信息的正确性 和权威性。 数据挖掘的研究和应用在具有很大挑战性的同时，也具有非常广阔的前景，预 计在本世纪还会形成更大的高潮。需求推动市场是永恒的定律，数据挖掘在已满足 用户的急需后，将会有更多基于数据挖掘的决策支持软件产品问世。只有从数据中 有效地提取信息，从信息中及时地发现知识，才能更好地为人类的决策服务，数据 才能够真正成为与物质、能源相媲美的资源，信息时代才会真正到来。 1 2 概念格研究现状 概念格是德国的w i l l e r 教授在2 0 世纪8 0 年代初提出来的，目前已经在很多方 面有了研究成果，重点介绍以下几点： 1 2 1 概念格的基本概念和定义 概念格，由w i l l e r 于1 9 8 2 年首先提出【3 1 。它反映了一种概念层次关系，并且 并非局限于一般树型结构。概念格中的每个结点是一个形式概念，它由两部分组成： 内涵和外延( 内涵是概念的描述，是该概念所覆盖对象的共同特征；外延是概念所 覆盖的对象) 。另外，概念格反映了一种概念层次结构，本质上体现了实体和属性之 间的关系，概念内涵和外延的统一，通过h a s s e 图生动简洁地体现了这些概念结点 之间的泛化和特化关系。概念格因此而成为一种有效的进行数据分析和知识提取的 工具。同时，概念格也可以用于完成许多机器学习的任务。目前，已经有了一些构 造概念格的算法，并且概念格在信息检索、数字图书馆、软件工程和知识发现等方 面也已得到实际应用【4 1 。 1 2 2 概念格的构造方法 概念格的构造方法主要分为两大类：批处理算法和渐进式算法【3 ，4 】。其中，渐进 式建格体现了一种概念聚类和提升的过程，被认为是最有前途的。 1 、批处理算法根据其构造格的不同方式，可分为三类，即自顶向下算法，自底 而上算法和枚举算法【3 ，4 1 。典型算法有b o r d a t ，c h e i n ，g a n t e r ，n o u r i n e 等。批处理 算法主要的问题是不能动态地更新，当形式背景发生改变时，必须重新构造概念格， 6 第一章绪论 代价非常大，并且重复结点较多。与此相反，渐进式算法则可以随对象或属性的增 加而动态地更新概念格。 2 、渐进式算法的基本思想是将当前插入的对象或属性与已有概念格中的所有概 念结点做交运算，根据交集结果的不同采取不同的操作。渐进式构造算法可分为基 于对象和基于属性两种方法。基于对象的经典算法是g o d i n 算法【3 。5 】，国内外学者对 g o d i n 算法进行了许多改进，例如：文献 6 提出了基于索引树的概念格快速构造算 法。基于属性的典型算法有：基于属性的概念格渐进式生成算法【7 1 、a d d i n t e n t 算法【8 】 等。a d d i n t e n t 算法是一种自底向上的建格算法，只考虑格结点内涵，根据要插入对 象的属性寻找标准产生子和更新结点，然后针对标准产生子的祖先结点更新概念格， 同时结点外延随着边的更新而更新。 这两类算法各有利弊，适用于不同的形式背景，概念格构造算法的选择应该以 输入数据的特性为基础。b o r d a t 算法适用于数据量大且形式背景是稀疏的，当对象 数很小时，它比其它算法慢很多。但是，当对象数增加时，与其它算法的差距变得 越来越小，最后在大多数情况下，它总会成为最快的。所以b o r d a t 在平均密度的数 据集中运行得比较好，尤其当关系图已经构造好后。对于数据量大且形式背景稠密 时，最快的算法是自底而上的算法n o r r i s ，c b o 。g a n t e r 算法随着数据集的增加性能 降低，只对具有很少属性的数据集有显著作用。c h e i n 算法变化大，在形式背景小时， 优于渐进式算法，背景逐渐增大时，会生成很多冗余结点。g o d i n 主要适用于数据量 少且形式背景稀疏的，当形式背景逐渐稠密时，构造效率显著降低。所以在处理海 量数据时，批处理算法总体性能要优于渐进式算法【5 9 j 。 另外，还有其它一些算法的改进：利用图的深度优先遍历、数据库技术构造概 念格【1 0 1 ；结合批处理算法和渐进式算法，分别利用前者的便于并行运算的特点和后 者的时间性能好的特点，提出一种基于概念格的并行构造方法u 。 1 2 3 基于概念格的知识提取 在知识发现领域，已有不少作者讨论了从概念格上提取知识的问题，基于概念 格的知识获取主要包括获取关联规则和分类规则。目前，许多研究表明概念格是规 则提取的一种有效工具，在概念格上提取的规则具有更好的效果。规则本身是用内 涵之间的关系来描述的，而体现于相应外延集之间的包含或近似包含关系。概念格 反映了概念内涵和外延的统一，结点间关系体现了概念间泛化与例化关系，便于理 解和提取。它是规则挖掘的一个自然平台，因为它的每个结点实际上就是一个最大 项目集。 7 基于约束概念格的恒犀光谱数据分类规则挖掘系统 胡可云、胡学钢等在文献 1 2 1 3 1 中介绍了基于一般概念格的规则提取，主要依 据格结点的直接泛化来产生相应的规则；胡学钢在文献 1 4 1 中介绍了基于扩展概念格 的规则提取；王浩等在文献 1 5 1 6 中介绍了基于量化概念格的规则提取方法；谢志 鹏等在文献 1 7 1 8 】中介绍了基于一般概念格的关联规则提取方法；梁吉业、王俊红 在文献 1 9 1 中把闭项集引入到概念格结点中，扩展了格结点的结构，提出了新的有利 于规则提取的结构；李云等在文献 2 0 中提出了在量化封闭项集格上使用最小项集来 挖掘全局简洁规则；文献 1 3 1 5 1 1 2 1 2 2 将概念格应用到分类中；文献 1 3 2 3 2 4 】 介绍了提取分类和关联规则的集成算法。在实际应用中，根据原形式背景构造出的 概念格结点数目非常庞大，而且直接使用这种方法得到的规则数目也非常多，整体 上存在冗余，须进行约简。另外文献 2 5 还介绍了利用约束概念格进行离群数据挖掘 的方法，这是一个新的领域方向，需要进一步研究。此外，知识提取还实现了相关 系统：g o d i n 系统中提出了渐进式构造概念格并提取蕴涵规则；g a l o i s 系统用于浏览 检索所需资料；t o s c a n a 系统中获得了嵌套概念格，使对概念的分析更加直观、 方便【4 1 。 1 2 4 概念格的扩展 目前对一般概念格有以下几种扩展：量化概念格 16 1 ，扩展概念格【2 6 1 ，模糊概念 格【2 7 】，加权概念格2 8 1 ，粗糙概念格，约束概念格3 0 1 ，i c e b e r g 概念格3 1 1 和多维概念 槲3 2 1 。 扩展概念格在概念格中引入了等价关系，将外延相同的内涵放在一起，提出等 价内涵的概念，扩展了结点结构，并且在扩展概念格的基础上提出了约简格，简化 了扩展概念格。量化概念格首先引入等价关系，然后针对外延，将外延用对象数来 表示，这更有利于规则的挖掘。模糊概念格是基于模糊形式背景的，将“模糊”引 入概念知识系统，建立了内涵与外延之间的模糊映射，用模糊集描述模糊概念。它 把对象属性表看成属性与对象的隶属关系表，隶属度表示模糊集合中的元素属于该 集合的程度。加权概念格通过给内涵引入了一个权值w ( 0 v 匹1 ) ，来说明内涵的重 要程度，对内涵的不同重要性进行了区分，使提取出的知识更具有实际意义。粗糙 概念格针对决策背景，利用粗糙集中上、下近似集描述概念格中结点内涵所拥有的 外延，使拥有的外延具有了不确定的性质，使概念格结构具备了描述不确定性知识 的能力。i c e b e r g 概念格是由闭频繁概念组成的半格，它是按照概念支持度将概念格 划分为上、下两个部分。上部分由频繁概念构成，即i c e b e r g 概念格，下部分由非频 繁概念构成。多维概念格是针对多维序列模式挖掘应用而提出的新的数据结构，是 8 第一章绪论 对概念格和有序概念格的泛化。它是在一般概念格的基础上，由于结点的序列模式 和关联模式把概念的内涵分为任务内涵( 基内涵) 和背景内涵( 附加内涵) ，可以进 行有效的多维模式序列挖掘。 1 2 5 概念格与其它理论的融合 目前，概念格和其它理论的融合主要体现在与模糊集、粗糙集的融合等。对于原 始的形式背景，根据对象的属性具有模糊性、不确定性等特点，将概念格与模糊集、 粗糙集相结合，进行格的构造与知识提取。如：强宇等人将“模糊 概念引入概念 格，构造出模糊概念格，并从通过计算规则支持度和置信度提取不确定规n t 2 7 j ；刘 宗田提出基于容差空间的概念格构造，利用粗糙集理论中的近似空间和与概念格之 间的对应关系，提出一种基于容差近似空间的格模型一广义概念格，并描述了该模 型建立的方法及产生规则的原则【3 3 】。 1 3 本文组织安排 第一章介绍数据挖掘基本概念、技术、功能和应用，概念格研究现状。 第二章介绍一般概念格与约束概念格的基本概念及其构造算法。 第三章研究了基于剪枝的约束概念格渐进式构造，说明构造过程中确实存在 冗余信息，利用剪枝技术，消除了冗余，提高了约束概念格渐进式构造的效率。 第四章研究了基于约束概念格的分类规则提取算法，并比较般概念格和约 束概念格提取的分类规则的分类正确率，最后给出实验结果和分析。 第五章根据第四章提出的分类算法，设计并实现了基于约束概念格的恒星光 谱分类规则挖掘原型系统。 最后，作为本文的结束，对所做的研究工作进行总结，并展望了今后进一步要 做的一些工作。 9 第二章一般概念格与约束概念格 第二章一般概念格与约束概念格 2 1 一般概念格 2 1 1 基本概念 定义2 1形式背景k _ ( g ，m ，r ) 定义为一个三元组，其中g 中对象集，m 属性集，i 适 g x m 。若g e g 和m m 在关系r 中，则表示为( g ，m ) e r ，即对象g 具有属性m 。由这个 二元偏序关系可以形成一个概念格结构l 。 定义2 2 设形式背景k 构造的概念格记为l ，l 中的每个结点称为一个序偶( 称为概 念) ，记为c ( a ，b ) ，其中a p ( g ) 称为概念的外延，b p ( m ) 称为概念的内涵，由a 中 所有对象拥有的共同属性所组成，则具有这种结构的格称为一般概念格。 定义2 3 设概念格l 对于关系r 是完备的，则对于l 中的任一结点c ( a ，b ) ，其中a c _ g ， b _ m ，满足以下两个条件： ( 1 ) a = b = g e gv m e b ，g m n ；( 2 ) b = a = m mv g a ，g m n e i ( a ，b ) 关于r 满足完备性，是最大扩展的。 定义2 4 概念格l 中所有结点之间的偏序关系表示为( a 1 ，b 1 ) ( a 2 ，b 2 ) c ：a i c _ a 2 b 2 b l ，表示为 l ( g ；m ，r ) ，9 ，其中：l ( g m ，r ) 表示概念格中概念结点的集合，表示 为结点之间的偏序关系。 定义2 5 给定概念格l 中两个不同结点c l ( a 1 ，b 1 ) 署d c 2 ( a 2 ，b 2 ) ，则c l s c 2 a 1 c a 2 b 1 d b 2 ，如果c i 5 c 2 且不存在c 3 = ( a 3 , b 3 ) ，使得c 1 c 3 c 2 成立，贝 j c 2 为c l 的父结点， c l 为c 2 的子结点。 2 1 2 一般概念格的构造算法 1 、批处理构造算法 批处理算法根据构造格的不同方式，可分为三大类，即自顶向下算法，自底向 上算法和枚举算法【3 1 。 自顶向下算法，首先构造最上层结点，再向下扩展，逐层生成子结点，例如b o r d a t 的算法。自底而上算法则相反，首先构造最底部的结点，再向上扩展，逐层生成父 结点，例如c h e i n 的算法。枚举算法则是按照一定顺序首先枚举格的所有结点，然 后再连接边，即计算各结点之间的父子关系，生成h a s s e 图，如g a n t e r ，n o u r i n e 算 法。 2 、渐进式构造算法 渐进式构造算法的基本思想是 4 ，5 】：首先初始化空概念结点，然后新增对象的属 基于约束概念格的恒旱光谱数据分类规则挖掘系统 性与原概念格结点的内涵进行比较，对于比较的三种结果：交集为空、子集和交集 不为空，可以将格结点分为：不变结点、更新结点和新增结点，最后根据结点类型 的不同进行不同的操作。典型的算法有g o d i n 5 1 ，c a p i n e t o 3 4 1 和t b h o 算法【3 5 】，这里 重点介绍g o d i n 算法。 给定形式背景k = ( g m ，r ) 以及它所对应的概念格 l ( g ，m ，r ) ，9 ，在新增一个对 象x 后，更新为形式背景k = ( g v a x ，m ，r ) 所对应的概念格 l ，( q m ，r ) ，9 。对于概念 格 l ( q m ，r ) ，9 中的每个结点c ( a ，b ) ，根据结点内涵b 与新增对象x 的属性集f i x ) 之 间的关系，加入新增对象x 之后形成的新格 l ( g m ，r ) ，9 中的结点可分为三种类型： ( 1 ) 不变结点；( 2 ) 更新结点；( 3 ) 新增结点。 1 ) 若b n f ( x ) = o ，i ) i i j h = ( a ，b ) e l ( g m ，r ) ，称c 为不变结点。 2 ) 若b c f f x ) ，则将格结点更新为c k ( a u x ) ，b ) ，并加入 l7 ( g ；m ，r ) ，9 中，即 c k ( a u x ) ，b ) e l ( g m ，r ) ，称c7 为更新结点。 3 ) 若b n f f x ) o ，且3 ( ( b m f f x ) ，b n f ( x ) ) 萑l ( g , m ，r ) ，则生成新结点c7 = ( a u x ， b e e f ( x ) ) ，并) j f l ) v l ( g m ，r ) ，9 中，即c = ( a u x ) ，b m f ( x ) ) el ( g m ，r ) ，称c 为新增 结点，c 为c7 的产生结点。 2 2 约束概念格 2 2 1 基本概念 在概念格的构造过程中，结点内涵所包含的属性并非都是用户感兴趣的，同时 一些结点内涵所包含的属性在实际应用中并无意义。因此，可以利用用户对数据集 的兴趣程度，选取一些属性作为背景知识来指导构造概念格，从而使概念格的结构 更具有针对性和实用性。采用谓词逻辑表示背景知识时，首先定义好描述背景知识 的谓词，并确定每个谓词的确切含义，然后再用连接词把有关谓词连接起来，形成 一个谓词公式以表达一条完整的背景知识。 一个二维表可表示为一个n 元有序组的集合，一个集合可用一个特性谓词刻画， 所以一个n 元有序组的集合可用一个n 元特性谓词刻画。基于一阶谓词逻辑的概念格 构造中所涉及到的背景知识描述【3 0 1 为： 定义2 6 一个格结点集合g ( z ) 为一个一元谓词，表示z 是一个格结点；i m e r e s t ( z ) 为一 个一元谓词，表示z 是一个关心结点。 定义2 7c o n c e p t ( z ，x ，y ) 为一个三元谓词，表示格结点z 具有内涵x ，外延y ；i n c l u d e ( x ， y ) 为一个两元谓词，表示由某属性集y 组成内涵x 。 1 2 第二章一般概念格与约束概念格 其中内涵x 由用户关心的含有某些属性集合的知识定义为第一类背景知识，内涵 x 由用户关心的不含有某些属性集合的知识定义为第二类背景知识。 定义2 8 设p l ( z ) = v z ( ( g ( z ) a c o n c e p t ( z ，x ，y ) a i n c l u d e ( x ，y 0 ) ) - - q n t e r e s t ( z ) ) 为一个谓词公 式，p l ( z ) 表示格结点z ，如果其内涵x 是由用户关心的属性子集y o 组成的，则结点z 为关心结点。 定义2 9 设p 2 ( z ) = v z ( ( g ( z ) 入c o n c e p t ( z ，x ，y ) a ( i n c l u d e ( x ，y o ) a i n c l u d e ( x ，y 1 ) ) ) - - - q n t e r e s t ( z ) ) 为一个谓词公式，p 2 ( z ) 表示格结点z ，如果其内涵x 是由用户关心的属性子集y o 、 y l 组成的，则结点z 为关心结点。 定义2 1 0 设p 3 ( z ) = v z ( ( g ( z ) k e o n c e p t ( z ，x ，y ) a ( i n c l u d e ( x ，y o ) v i n c l u d e ( x ，y 0 ) ) - - q n t e r e s t ( z ) ) 为一个谓词公式，p 3 ( z ) 表示格结点z ，如果其内涵x 如果是由用户关心的属性子集 y o 或y l 组成的，则结点z 为关心