（计算机应用技术专业论文）基于概念格的关联规则提取及其渔业应用研究.pdf

上海海洋大学学位论文版权使用授权书 学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅或借阅。本人授权上海海洋大学可以将本学位 论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或扫描等复制手段保存和汇编本学位论文。 保密 本学位论文属于 不保密 口，在年解密后适用本版权书。 学位论文作者签名：王戴牟 日期：2 d f f 年p j 月眵日 喜 f日 孝影 名 戤阵币吖 溯沙 导期借日 懒 上海海洋大学硕士学位论文 答辩委员会成员名单 上海海洋大学硕士学位论文 基于概念格的关联规则提取及其渔业应用研究 摘要 近年来，数据挖掘( d a t am i n i n g ) 引起了信息产业界的极大关注，其主要原因 是现实中存在大量数据，不能被充分使用，另一方面又存在着迫切需要将这些数 据转化为有用的信息的需求。概念格( c o n c e p tl a t t i c e ) 作为数据挖掘领域的重要分 支，在研究及应用方面已取得了很大的进展。然而，由于现实世界数据的海量、 异构和数据类型的多样性、结构的复杂性等特点，概念格应用在复杂环境下才是 近年来的新研究方向。 本文研究了一种新的概念格约简算法( r e d u c t i o na l g o r i t h m ) ，并将概念格引入 关联规则( a s s o c i a t i o nr u l e s ) ，建立了基于概念格的关联规则提取模型。通常的约 简算法主要讨论概念格的约简，而本文讨论的是基于形式背景( f o r m a lc o n t e x t ) 的约 简。本文建立了一个新模型，其主要过程包括：形式背景的约简、概念格的建立、 基于概念格的关联规则提取。该模型被应用于中西太平洋大眼金枪鱼的渔情分析。 本文分析了渔场多环境因子与单位捕鱼量之间的关联关系。利用已有历史数据， 研究并建立了一个实在的渔情概念格模式。与已报道的模型相比较，该模型提高 了提取关联规则的有效性及准确性。 本文的主要工作及结果如下： ( 1 ) 提出了一种面向形式背景的约简算法：通过分析形式背景中的对象和 属性的特征，将符合概念格约简定理的对象或属性进行约简。然后在更新后的形 式背景的基础上，建立相应的概念格。 ( 2 ) 将上述约简算法拓展到了动态形式背景的研究：在该算法中，首先提 取出原形式背景的核心属性，将新增加的形式背景看成原形式背景的增量，建立 增量后的形势背景的概念格。 ( 3 ) 根据可用的渔业数据建立形式背景。将渔业数据按照以下方式进行预 处理：对应于形式背景，渔业数据中的经纬度作为对象，环境因子与单位产量作 为属性。分别将对象进行归一化处理和统一所有属性的分辨率。经过如此标准化 上海海洋大学硕士学位论文 预处理后的数据有利于提高了处理效率以及保证了试验数据的有效性。 ( 4 ) 该模型成功应用于渔业研究中的多环境因子及单位作业次数的产量： 本文以2 0 0 4 年的大眼金枪鱼数据作为试验数据来建立现实的概念格模型，从中发 现并验证了海面高度为渔业生产中的核心属性，对大眼金枪鱼的产量及其他环境 因子的影响最大。 关键词：概念格，属性约简，关联规则，渔业应用 上海海洋大学硕士学位论文 a s s o c i a t i o nr u l e sb a s e do nc o n c e p tl a t t i c ea n di t sa p p l i c a t i o n f i s h , r , l r c h i n l s h e r i e sr e s e a r c h a b s t r a c t i nr e c e n ty e a r s ，h i g ha t t e n t i o nh a sb e e np a i df o rd a t am i n i n gi ni n f o r m a t i o n i n d u s t r y ，b e c a u s el a r g ea m o u n t so fd a t aw e r en o tb ef u l l yu s e d ，a n dm e a n w h i l em a n v u s e f u li n f o r m a t i o na n dp r a c t i c a lk n o w l e g d ea r eh i g h l yn e e d e dt ob ee x t r a c t e df r o mt h e s e d a t a c o n c e p tl a t t i c ei sa ni m p o r t a n tb r a n c ho fd a t am i n i n g ，a n di th a sr e a c h e dag r e a t a c h i e v e m e n ti nb o t hr e s e a r c ha n da p p l i c a t i o n h o w e v e r , a p p l i c a t i o no ft h i sc o n c e p t l a t t i c ei nc o m p l e xp r a c t i c e s ( e g ，l a r g ed a t aw i t hh e t e r o g e n e i t y ，d i v e r s i t ya n d c o m p l e x s t r u c t u r e ) i san e ws t u d yd i r e c t i o n i nt h i sp a p e r ，t og e ta s s o c i a t i o nr u l e so nt h eb a s i so f c o n c e p tl a t t i c ew a ss t u d i e d ， w h e r ean e wa t t r i b u t er e d u c t i o na l g o r i t h mh a sb e e nd e v e l o p p e d o u rr e d u c t i o n i s p e r f o r m e da ts t a g eo ff o r m a lc o n t e x t ，w h i l et h er e d u c t i o nw a sg e n e r a l l yh a p p e n e di n s t a g eo fc o n c e p tl a t t i c e an e wm o d e l ( r e d u c t i o na tf o r m a lc o n t e x t - - ) c o n c e p tl a t t i c e - - ) a s s o c i a t i o nr u l e s ) i st h e r e f o r ee s t a b l i s h e d ，i th a sb e e na p p l i e di nf i s h e r y ：t oa s s o c i a t et h e m u l t i e n v i r o n m e n t a lf a c t o r sa n dt h ef i s hp r o d u c t i v i t y p e rs h i p ( e g ，t u n n yf i s hi n w e s t e r na n dc e n t r a lp a c i f i co c e a n ) b yv a l i d a t i o nw i t hh i s t o r i c a lf i s h e r yd a t a , t h i sn e w m o d e lh a sb e e np r o v e dt h a ti tc a ng r e a t l yi m p r o v et h ee f f i c i e n c yo ff i n d i n ga s s o c i a t i o n r u l e sf r o ml a r g ed a t aa n de n h a n c et h ea c c u r a c yo fi t sa p p l i c c a t i o ni np r a c t i c et h a no t h e r a v a i l a b l em e t h o d s t h em a i nw o r k sa n dr e s u l t sd e s c r i b e di nt h i sp a p e ra r e i n c l u d i n g ： ( 1 ) d e v e o l p p e dar e d u c t i o na l g o r i t h mi ns t a g eo ff o r m a lc o n t e x t ：u p o nt h e c h a r a c t e r i s t i c so ft h eo b j e c ta n da t t r i b u t ei nt h ef o r m a lc o n t e x t ，t h e s e o b j e c t sa n d a t t r i b u t e st h a tf u l f i l lt h ec o n c e p tl a t t i c ea r ef i r s t l yr e d u c e d ，an e w c o n c e p tl a t t i c ei st h e n e s t a b l i s h e do nt h eb a s i so fr e f o r m e df o r m a lc o n t e x t ( 2 ) e x t e n d e dt h i sr e d u c t i o na l g o r i t h mt oad y n a m i cf o r m a lc o n t e x t ：i ns u c hc a s e s ， t h ec o r ea t t r i b u t eo fac o n c e p tl a t t i c ei sf i r s t l yf o c u s e da n dt h e ne x t r a c t e d u n d e rt h i s r e d u c t i o na l g o r i t h e mw i t hi n c r e m e n t a la t t r i b u t e ，n e wc o n c e p tl a t t i c ec a nb ef o r m e dw i t h t h ei n t e g r a t e df o r m a lc o n t e x t s ( 3 ) e s t a b l i s h e dap r a c t i c a lf o r m a lc o n t e x tw i t ht h ea v a i l a b l ef i s h e r yd a t a t h e i f i s h e r y i v 士学位论文 录 第二章概念格的理论基础1 0 2 1形式概念分析l o 2 1 1 基本概念1 0 2 1 2概念格的构造1 2 2 2概念格的属性约简1 3 2 2 1概念格属性约简的相关定义1 3 2 2 2概念格约简判定定理1 5 2 3本章小结1 5 第三章基于概念格的关联规则提取1 6 3 1概念格属性约简算法1 6 3 1 1传统的的概念格的属性约简算法1 6 3 1 2增量式的概念格的属性约简算法1 7 3 1 3基于粗糙集和增量式的概念格的属性约简实例比较1 9 3 2基于增量式约简概念格的关联规则提取2 5 3 2 1基于约简概念格的关联规则的相关概念2 5 3 2 2基于约简概念格挖掘频繁项目集2 7 3 2 3基于约简概念格的关联规则提取算法2 8 3 3本章小结3 1 第四章基于概念格的关联规则提取在渔业上的应用研究3 2 4 1渔业数据的预处理3 2 4 1 1数据处理流程3 2 4 1 2 数据来源3 3 4 1 3 数据清理3 4 4 1 4数据选择3 5 4 1 5数据评估与集成3 9 v i i l 1 2 2 3 6 7 8 8 9 r l i 4 4 2 4 4 4 4 3 4 4 4 4 4 第五章 5 1 5 2 参考文献 作者在攻 致谢 上海海洋入学硕士学位论文 第一章绪论 帚一早珀t 匕 ，各类金融企业、商业机构、教育产业、渔类产业等众多 及丰富的信息资料。“数据丰富，知识匮乏”，决策者很 出有价值的知识，这一现状促使人们产生了对数据分析工 有效地利用和处理大量的数据成为当前世界范围内所共同 中发现知识( k n o w l e d g ed i s c o v e r yi nd a t a b a s e s ，k d d ) 及其 核心技术数据挖掘( d a t am i n i n g ，d m ) 1 2 _ l 应运而生。由此产生了大量的数据 挖掘方法，如概念格、关联规则、粗糙集等。本章主要讨论了其中两种方法，概 念格和关联规则。 在哲学中，概念被理解为由外延和内涵两个部分所组成的思想单元。基于概 念的这一哲学思想，德国的r w i l l e 教授于1 9 8 2 年首先提出了形式概念分析理论【4 1 。 1 9 9 9 年由b g a n t e r 和r w i l l e 教授所著的形式概念分析一书从本质上分析了 形式背景和概念格自身的各种特点，以及概念之间的关系、概念格的分解、构造 和度量等等有关概念格的基础知识，为国内外学者研究概念格在各个领域中应用 提供了基础。根据数据集来生成概念格的过程实质上是一种概念聚类过程，它体 现了概念内涵和外延的统一，以及概念的泛化与例化关系，反映了对象和属性间 的关系，因此非常适于发现数据中潜在的概念和知识。 关联规贝j ( a s s o c i a t i o nr u l e s ) 的研究是数据挖掘中一个重要的分支，它可以发现 大量数据项集之间的潜在联系。由于在关联规则集合之上存在一种偏序关系，这 种关系可以用概念格充分表示。当基于数据集合的概念格构建之后，可以较快地 有效地来进行关联规则的发现。而且，概念格的可维护性使得在数据库发生动态 变化时，基于概念格的关联规则也易于动态更新。本文以渔业应用为背景，提出 一种面向渔业应用的新型数据挖掘方法，通过对动态渔业数据的分析处理、特殊 形式背景模型的构成、概念格的构建以及关联规则的提取等关键内容进行研究。 上海海洋人学硕十学位论文 本论文来源于国家8 6 3 项目( n o 2 0 0 7 从1 0 2 2 3 8 ) ，上海市教委基金项目( n o 0 8 y z l 2 0 ) 。 1 2 研究背景和意义 1 2 1 概念格的研究现状 概念格是应用数学的一种常用方法、知识的一种表现模型，依据知识体在内 涵和外延上的依赖或因果关系，建立概念层次结构。本质上，基于这种思想构造 的格结构以及h a s s e 图描述了对象与属性之间的联系，表明了概念之间泛化与例化 的关系。目前概念格在以下几个方面进行研究： 在概念格的构建方面：h ot b 研究了基于概念格的概念聚类算法，并实现一 些学习系统，如o s h a m 和i n c o s h a m 。在形式概念分析中，除了概念格的数学 性质外，概念格的自动构建是一个重要的研究内容。批处理算法以b o r d a t 提出的 自上而下的批处理生成算法为代表，渐进式算法以g o d i n 算法为代表。基于b o r d a t 的批算法，n j i w o u a 等提出了概念格的并行算法，给出了算法的j 下确性证明并研究 了该算法的理论复杂性。 在概念格的约简方面：建格的批处理算法b o r d a t 是通过引入一个支持度门限， 在建格过程中对于支持度小于门限的节点不予继续丌展而达到剪枝的目的。胡学 钢，王听娅提出概念格和粗糙集关系的基础上，建立了基于概念格的粗糙集合模 型表示，研究了基于概念格模型的约简和核的求解方法。 在概念格进行规则提取方面：1 9 9 4 年g o d i n r 等描述了基于概念格模型的概 念形成方法【5 j ，主要提出了从概念格中提取出蕴涵规则的算法。但是这种蕴涵规则 是一种确定性规则，不具备描述概率规则的能力和抗噪音能力。1 9 9 6 年r w i l l e 教授考虑了多形式背景下的对象和属性之间的关系，研究了在概念格框架结构下 对结构化对象所进行的概念学习和规则提取，还将学习所得到的概念和规则进行 了解释【6 1 。1 9 9 9 年n p a s q u i e r 等首先研究了关联规则的提取问题用。他们的主要提 出了用于提取确定性关联规则的d e q u e n n e g u i g l l e 基，以及用于近似关联规则的适 当基和结构基等。1 9 9 9 年王志海提出概念格的规则提取的渐进式算澍剐。2 0 0 0 年 2 _ _ _ _ _ _ _ _ _ - _ _ _ _ _ _ _ _ _ 。i - 。_ _ _ _ _ 。_ - _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ - 。1 。1 。1 。 上海海洋入学硕士学位论文 胡可云等提出利用概念格进行分类和无冗余规则的提取i 引。2 0 0 0 年谢志鹏等提出 了利用概念格的层次关系提取关联规则【1 0 l 。2 0 0 0 年刘宗田等提出利用容差关系建 立广义概念格并提取近似规则【1 1 】。2 0 0 1 年赵奕等针对概念格与r o u g h 集之间的联 系，把二者有机的结合在一起提出了r o u g h 概念格，并在此基础上提取蕴含规则 1 1 2 l 。2 0 0 2 年胡学钢等也在一般概念格的基础上提出了扩展概念格、约简概念格的 定义，并利用这些非经典概念格进行高效的规则提取【1 3 l 。 由以上可以看出，目前的概念格的关联规则提取只是单方面的考虑多形式背 景，或者概念格的层次关系，或者查找概念格的频繁项目集，没有综合的分析概 念格的各种情况。但是由于现实世界数据的海量，数据的维数巨大，而且数据可 能是不完全的、有噪声的；另外，数据挖掘面对的数据可能是异构的，或可能具 有多种数据类型和复杂性的数据结构等，因此，减小与数据挖掘任务相关的数据 库规模是一个研究途径，充分利用概念格的层次关系，同时提高关联规则挖掘算 法的效率是关联规则挖掘的研究方向。 在概念格的应用方面：概念格已成功的应用于数字图书馆及文献检索，软件 工程，知识发现等领域，并且已取得良好的经济效益和社会效益。国内也有谢志 鹏等设计了l a c s 等基于概念格的分类系统。此外，1 9 9 7 年t b h o 提出基于概念 格的概念聚类方法1 1 4 】，并实现了一些学习系统，包括o s h a m 和i n c o s h a m ，其 中i n c o s h a m 在o s h a m 系统基础上增加了渐进式学习的能力。沈夏炯【1 5 】等设 计了i s o f c a 基于概念格同构生成方法的系统，并实现了概念格的互操作及三维 可视化。 虽然，国内外的研究者们给我们提供了有关概念格的构造及其应用方面的丰 富的知识，但我们仍有必要更多的研究概念格，尤其是基于不同形式背景的概念 格在各个领域中的应用。 1 2 2 渔业应用研究现状 海洋渔业是我国农业的重要组成部分，是国民经济的一个重要产业部门【1 6 】。 自建国以来，海洋渔业就为我国解决就业、保障食物和提供优质蛋白质做出了巨 大的贡献。近年来，随着近海渔业资源的衰退，远洋渔业成为我国海洋渔业一个 3 上海海洋人学硕十学位论文 新的增长点。长期的海上作业积累了大量的有用数据，我国一些水产工作者开始 了远洋渔业鱼种的渔情预报研究工作。由于过度捕捞和环境污染，世界范围内底 层鱼类资源遭到了严重破坏，而头足类和中上层鱼类产量总体却呈上升趋势1 1 7 1 。 于是，以大洋性金枪鱼类为捕捞对象的金枪鱼渔业倍受各渔业国家的青睐，成为 不少渔业发达国家争相捕捞的对象，大眼金枪鱼因其市场价值高，一直是我国金 枪鱼船队的主要捕捞对象之一。 金枪鱼广泛分布于太平洋、中西太平洋和大西洋中低纬度的近海、外海和大 洋中。世界主要的金枪鱼的产量有6 0 - - 一7 0 来自太平洋水域，而这其中有7 6 来自 中西太平洋。中西太平洋金枪鱼渔业是一个多样性的渔业，作业方式包括围网、 竿钓、延绳钓、曳绳钓以及流网等，其中大约有5 6 的产量来自围网捕捞。分析南 太平洋论坛渔业局( f o r u mf i s h e r ya g e n c y ，f f a ) 公布的产量数据，自1 9 9 6 年中西 太平洋围网捕捞产量占金枪鱼总产量均达6 0 以上，且总体有增加的趋势，2 0 0 5 年 达6 9 。捕捞的总产量也有较大的增长，2 0 0 5 年比1 9 9 7 的产量增加了6 3 。由此看 出中西太平洋是会枪鱼围网渔业最主要的渔区，是可以获取会枪鱼最大利润的海 区。 金枪鱼围网主要来自美国、日本、韩国、中国和菲律宾。近年来，很多原来 在大西洋及东太平洋作业的大型西班牙围网船有转移至中西太平洋渔场作业的趋 势，部分渔船已在该海域作业。美国是应用金枪鱼围网捕捞技术最早的国家。 1 9 9 3 1 9 9 8 年问，美国远洋渔业研究所( p f r p ) 通过t o p e x p o s e i d o n 卫星测定海面 高度数据，揭示了亚热带i j i 锋的强度和夏威夷箭鱼沿绳钓渔场的关系。美国国家 海洋渔业服务中心( n m f s ) 将海洋遥感和地理信息系统应用于海洋渔业资源以及 渔情分析研究中，开发了一系列渔业信息系统，包括服务于阿拉斯加州的阿拉斯 加渔业信息网络( a k f i n c ) ，服务于华盛顿州、奥尔良州、加利福尼亚州的太平 洋渔业信息网络( p a c f i n ) 等。 在日本，渔业较为发达。从1 9 1 0 年至1 9 3 5 年曾开展过金枪鱼围网捕捞试验， 第二次世界大战后，再度进行金枪鱼围网试验。日本水产厅于1 9 8 0 年成立了“水 产遥感技术促进会”，目的是要将人造卫星的遥感技术应用于渔业。1 9 8 2 年f 1 本 水产厅宣布，他们利用人造卫星和电子计算机搜索秋刀鱼和金枪鱼等鱼群获得成 功。 4 上海海洋人学硕十学位论文 统计的方法，推算出各水层、水温、盐度范围的渔获率。徐丽萍在基于数据挖掘 方法的w c p o 金枪鱼围网渔情预报研究中使用一种面向粗糙集的属性化简方法 ( 利用s k o w r o n 提出的可辨识矩阵得到属性的最佳化简) ，同样对上述1 8 个因子 及产量数据进行分析，利用多元回归方法构建预测中西太平洋海域鲣鱼围网产量 的数据模型，确定强相关影响因子集。 但这些研究存在以下不足：( 1 ) 渔情作业数据及海洋环境数据的数据量虽然庞 大，但真正可以用来进行数据挖掘的数据量稀少【2 4 】；( 2 ) 目前渔情预测大部分采用 多元回归分析法，但动态的海洋环境因子不符合回归分析的前提因变量之间 独立和正态分布；( 3 ) 目前挖掘出来的知识都为静态知识f 2 5 1 ，海洋环境因子和渔场 均为动态变化，能体现环境因子和渔场间变化关系的动态知识比静态知识更为重 要。 1 2 3 研究意义 本文研究的渔业背景主要中西太平洋大眼金枪鱼的产量与环境之间的关系。 下面主要讨论中西太平洋金枪鱼的研究意义。 金枪鱼【冽及类金枪鱼经济价值高，分靠范围广，属高度洄游鱼类种群。金枪 鱼渔业一直是各渔业国家和地区，尤其是远洋渔业国家和地区发展的重点。我国 大陆自2 0 0 2 年发展金枪鱼围网渔业至今已有八年有余，参与金枪鱼围网渔业的公 司在不断增加，船组数量明显增加。金枪鱼广泛分布于太平洋、印度洋和大西洋 中低纬度的近海、外海和大洋中。 目前，中西太平洋海域商业性围网渔业迅速发展。2 0 0 3 年，在w c p o 海区作业 的金枪鱼围网船共有2 0 0 多艘【2 7 1 。由于作业成本的因素，日本、美国、韩国、中 国台湾四个主要渔业国家和地区围网渔船船队规模较之2 0 世纪9 0 年代初的鼎盛 时期都有所缩小。其中，美国围网渔船数量下降最多，其余三个国家和地区的围 网渔船数量近5 年基本保持不变。 太平洋岛国的围网渔船船队规模近几年一直处于扩张中。从2 0 0 1 年开始，新 西兰和中国大陆的围网渔船也开始进入w c p o 海区。中国大陆的围网渔船显现出较 猛的发展势头，其数量已从2 0 0 1 年的l 艘，发展到2 0 0 2 年的2 艘，2 0 0 3 年的4 6 上海海洋人学硕十学位论文 艘。至2 0 0 5 年，渔船数量已经达到了8 艘。 国外学者已经对大眼金枪鱼的分布和生理、生态进行了许多的研究和探索。 m o h f i 和t a k e d a 【3 0 l 在印度洋通过常规和深水延绳钓探捕试验，研究大眼金枪鱼的 垂直分布以及最适水温范围。m o h f i 3 1 j 利用金枪鱼延绳钓生产数据和海洋环境数据 推测大眼金枪鱼分布的最适水温范围。但目前国内对金枪鱼渔业的研究【3 2 】尚处于 初期，大多局限于对金枪鱼渔业生产技术的分析探讨或渔获产量的描述统计，有 关大眼金枪鱼渔获率与环境因子的关系的研究未见报道。因此研究中西太平洋大 眼金枪鱼的产量分布与有关环境因子的关系，对于指导渔业生产、维护资源稳定、 供我国船队在海上生产作参考，以提高大眼金枪鱼的渔获率，从而提高经济效益， 都具有重要的意义。 而且围网生产渔船搜索鱼群主要靠传统的寻鱼方式，包括：靠目视侦察、以 直升机或飞机在空中寻鱼、利用鱼探机及声纳探鱼等。除此之外还参考国外运营 商提供的关于渔场温度、盐度和叶绿素浓度分布变化情况的渔情预报，但利用该 渔情报告耗资较大。如果在作业前能对金枪鱼围网渔情作出较为准确的预报，便 能发挥其效率而获得大量的渔获。为此，研究机构和生产企业应携起手，尽早研 制出能够向渔民提供该方面信息的渔情预报软件，以服务于围网渔业生产。 因此，丌展中西太平洋海域会枪鱼围网渔情预测工作的研究是一项非常紧迫 的任务。 1 3 创新性 本文以渔业应用为背景，提出一种面向渔业应用的新型数据挖掘方法，通过 对动态渔业数据的分析处理、特殊形式背景模型的构成、概念格的构建以及关联 规则的提取等关键内容进行研究，提出基于概念格的关联规则挖掘动态知识方法， 设计并实现有效的关联规则提取方法，创建动态渔业知识与形式背景下概念格间 的映射机制等，并通过真实海洋环境和生产数据验证该方法及其关键技术的有效 性。 7 l 上海海洋人学硕十学何论文 1 4 本文主要研究内容和工作安排 1 4 1 本文主要研究工作 形式概念分析【3 3 】理论以数学化的概念和概念层次为基础，是格理论阻3 5 l 的一 个分支，可以作为数据挖掘的一个算法，用于数据分析和知识处理。概念格( g a l o i s c o n c e p tl a t t i c e ，g a l o i s 格或g c l ) 1 3 6 j 是一种基于二元关系的完备层次结构，它的每 一节点称为一个概念，每个概念由外延和内涵两部分组成，概念的外延表示属于 这个概念的所有对象的集合，而内涵则表示为这些对象所共有的属性集合。概念 格描述了对象和属性之间的关系，其哈斯图清晰地表明了概念问泛化和特化的关 系。因此，概念格具有很好的知识表示和描述知识发现问题的能力。作为数据分 析的有力工具，概念格理论已经被广泛地应用于知识发现和数据挖掘领域。 形式概念分析的核心数据结构概念格是提取规则知识【3 7 1 的一个很好的平 台，其概念格结点体现了概念内涵和外延的统一，非常适合于用来发现规则型知 识。因此，运用形式概念分析理论，结合数据库等相关背景，从大量数据中抽取 出有用的知识，如概念等，是切实可行并且是有意义的，其主要优点在于可以将 数据中( 无论是表面的还是隐含的) 内在逻辑和组织结构完整地图示化( h a s s e 图) ， 从而为分析概念数据之间的关联提供系统的可视化工具。因此，本文采用概念格 模型作为关联规则挖掘的理论工具。 所研究的主要内容如下： ( 1 ) 研究海洋遥感数据和渔业数据的预处理技术。卫星遥感在海洋渔业中的 应用研究已倍受人们关注，基于海洋遥感数据的渔情预测已逐渐成为渔业主管部 门和生产单位如何进行渔汛生产部署和管理的重要依据。但是，海洋遥感数据是 一项不确定性的渔业数据，需要预先进行相应的处理后才能进行实际模型的使用。 ( 2 ) 研究概念格的属性约简。概念格基于形式背景，形式背景中描述概念的 属性并不是同等重要，甚至某些属性是冗余的。因此针对不同的目的要求，保持 知识库分类能力不变，删除概念格中不相关或不重要的属性，在不丢失基本信息 的前提下，使知识的表示更加简化。 ( 3 ) 研究基于概念格的关联规则挖掘。概念格是完备的层次结构，因而较适 8 上海海洋人学硕十学位论文 合于关联规则挖掘，具有简捷、直观和交互性的特点。然而，由于概念格中含有 与关联规则求解无关的一些内容，以减少概念格的规模，需要采用必要的措施， 删除这些无关的部分，以提高关联规则挖掘的效率。 ( 4 ) 研究基于概念格关联规则提取在渔业数据上的应用。渔业数据是一个特 殊的形式背景，需将预处理好的数据转化为形式背景，并建立相应的概念格，然 后利用概念格的关联规则提取方法提取相应的关联规则。 1 4 2 本文内容安排 本文主要分为五章： 第一章主要讨论了本文的研究背景和意义，并提出了本文的创新性，最后简 要的介绍了本文的研究工作和内容安排。 第二章概述了本文所涉及的主要基础理论知识。主要介绍了形式概念分析， 概念格的构造、概念格的属性约简。重点介绍了概念格属性约简中约简集的结构、 约简的判定定理集属性约简算法。 第三章主要讨论和研究概念格的属性约简及应用。简要介绍了概念格约简集 的结构和判定定理，并分析了目前主要的几种概念格的属性约简算法。在此基础 上，提出了一种增量式的概念格属性约简算法。 第四章介绍了基于概念格的关联规则提取及渔业应用研究，主要建立了基于 概念格的关联规则提取的模型。分别对渔业数据进行了数据评估和数据集成，在 数据评估过程中采用了j 下交试验方法进行筛选。最后基于模型中得出的关联规则 进行了渔情预测。 第五章对本文做了一个总结，并对实验发展方向做了展望。 9 上海海洋人学硕十学位论文 第二章概念格的理论基础 形式概念分析处理的数据主要是二维表结构形式表现的模式背景，然后以概 念格为数据结构来表达对象和特征之间的联系，并以h a s s e 图的形式来实现概念格 的可视化。约简概念是扩展概念的一种简洁表示形式，保留了概念内涵中的关键 部分一基本内涵，并且通过基本内涵可以生成所有的等价内涵空间，揭示了基本 内涵间的内在关系。约简概念反映了概念简洁的表示形式，是实际应用中人们所 感兴趣的。以下主要介绍它们的相关基础知识。 2 1 形式概念分析 与传统的数据挖掘算法相比，概念格模型在半结构化和无结构的文本数据以 及w e b 数据上具有较好的效果，下面解释概念格的相关理论知识。 2 1 1 基本概念 形式概念分析依据的数学基础是序论( o r d e rt h e o r y ) 及完全格( c o m p l e t el a t t i c e ) 理论，处理的基本数据形式是以二维表结构形式表现的形式背景，然后以概念格 为数据结构来表达对象和属性之间的联系和各个概念间的泛化与例化关系，并以 h a s s e 图的形式来实现概念格的可视化。 形式背景及其概念格是概念知识的基本要素的形式化表示的，而且是一种适 当的数学结构，很多研究都是从形式背景开始的，本小节将介绍与形式背景的相 关理论知识。 定义2 1 ：( 形式背景) 一个形式背景l a d 由集合u 、a 以及它们之间的关 系组成i ，u 的元素称为对象( o b j e c t s ) ，a 的元素称为属性( a t t r i b u t e s ) 。为了表示 一个对象。和一个属性m 在关系i 中，可以写成o i i n 或( o ，m ) e l ，读成“对象。拥有属性 i i l 。 在形式背景基础上，获得形式概念( x ，b ) ，其中，x 称为概念的外延，是属于 1 0 上海海洋人学硕十学位论文 这个概念的所有对象的集合；而b 称为内涵，是所有这些对象所具有的属性( 或 特征) 集。概念是外延与内涵的统一体。这种描述实现了对概念的哲学理解的形 式化。 定义2 2 ：( 概念) 对于形式背景k ，在u 的幂集和a 的幂集之间可以定义两个 映射f 和g 如下： v o u ：，( d ) 一 d v ( x l d ) ( 2 1 ) v d a ：g ( d ) = x v d d ( x l d ) ( 2 2 ) 来自p ( u ) x p ( a ) 的二元组( o ，d ) 如果满足两个条件：o = g ( d ) 及d = f ( o ) ，则它被称 为是形式背景k 的一个形式概念，简称概念，记为c ：( o ，d ) ，其中d 和o 分别被称 为概念c 的内涵和外延。一个形式背景可能有许多概念，事实上，形式概念的数目 是形式背景大小的指数f 3 8 1 。k 的所有形式概念的集合被标记为c s ( k ) 。 所有的概念同它们之间的泛化例化关系构成一个概念格。概念格的每个节点 都是一个形式概念。概念格结构模型是形式概念分析理论中的核心数据结构。它 本质上描述了对象和特征之间的联系，表明了概念之间的泛化和例化关系，其相 应的h a s s e 图则实现了对数据的可视化。 定义2 - 3 ：( 概念格) 对于概念( o 。，d ，) 和( o ：，d ：) 。如果d 2 d l ，则形式概念( o 。，d ，) 是形式概念( 0 2 ，d 2 ) 的子概念，形式概念( 0 2 ，d 2 ) 是形式概念( o ，d 。) 的超概念，记 为( o l j d l ) s ( 0 2 d 2 ) 。关系= 为形式概念之间的序关系，通过这个关系，我们得到一个 有序集鱼( k ) = ( c s ( 均，s ) ，这是一个完全格，被称为形式背景k 的概念格，记为u k ) 。 形式背景通常用一个二维表格来表示，该二维表格是描述了对象及其特征之 间的自然分组和关系的有序集。概念格是所有形式概念在子概念和超概念下的序 集。因此，概念格可以图形化表示为其所对应的h a s s e 图。这使得给定数据背景的 概念结构变得清晰和易于理解，从而实现了概念格的可视化。每个概念用其外延 和内涵来标识，节点之间的边表示概念之间的序关系。一种简化的标识方法让每 个对象和属性只出现一次，即将每个属性标识在自上而下出现该属性的第一个节 点上，将每个对象标识在自下而上出现该对象的第一个节点上。这样从图中仍能 读出每个概念的外延和内涵，一个概念的外延由其所有子概念上标识的对象组成， 一个概念的内涵由其所有超概念上标识的属性组成。 ， 上海海洋人学硕+ 学位论文 例1 ，给定的形式背景如表2 1 所示，生成的概念格如图2 3 中所示： 表2 1 形式背景( u ，a ，i ) t a b l e2 1f o r m a lc o n t e x t ( u ，a ，i ) abcd x 1 11 01 x 2 101o x 3011o x 4 11o1 x 51000 针对表2 1 所示的形式背景( u ，八d ，u = x 。，x 2 ，x ，x 。，x ，) ，a = a ，b ，c ，d ，我们给 出其形式概念和概念格。 该形式背景总共有8 个概念： ( x 1 x 2 x 4 x 5 ，a ) ，( x l x 3 x 4 ，b ) ，( , x 2 x 3 ，c ) ，( x l x 4 ，a b ) ， ( x ：，a c ) ，( x 。，b c ) ，( u ，妒) ， ，a ) 。为方便描述与分析，我们将其简记为( 1 2 4 5 ，a ) ， ( 1 3 4 ，b ) ，( 2 3 ，0 ，( 1 4 ，a b ) ，( 2 ，a c ) ，( 3 ，b c ) ，( u ，妒) ，( 妒，a ) 。所得的概念格如图2 1 所示。 i 似。、i 1 、 ( 1 2 4 5 ，a ) ( 1 3 4 , 曲)( 2 3 ，c ) 仁 结论3 7 ：如果口彳是一个核心属性在k 中营【口】。n 【口】：= 口) 。 根据以上定义，下面讨论基于增量式的概念格的属性约简算法： 图3 1 增量式的概念格的属性约减算法 f i g3 1i n c r e m e n ta t t r i b u t er e d u c eo fc o n c e p tl a t t i c ea l g o r i t h m 算法首先考虑单个形式背景，在形式背景进行转换为对应的布尔值型，将形 式背景进行属性约简后，再将更新后的形式背景进行增量式的形式背景进行概念 格的建立。 算法做了以下几点改进： ： 上海海洋人学硕十论文 现取其中七种属性为例，如b r e a t h e si nw a t e r , h a sl e g s ，h a st e n t a c l e ，h a sh e a d ，h a s m o u t h ，h a ss h e l l ，h a se y e s 。对应的关系表如下： 表3 2一个简化水生类物种的上下文 t a b l e3 2as i m p l i f i e dc o n t e x to fa q u a t i cs p e c i e s 属 b r e a t h e s h a sh a sh a sh a sh a sh a s i n w a t e r i e g s t e n t a c l eh e a dm o u t hs h e l l e y e s 对性( a )( b )( c )( d )( e )( 置) 电) 碧 ll e e c h 2 j e l l y f i s h 土宰士 3 o c t o p u s 毫毫t 4 s c a l l o p t幸 5 s h r i m p 幸t士宰 6c r a b 幸 7f i s h 拿t ( 2 ) 数据转换： 将简化的上下文按顺序编号，其中，一个物种相当于一个对象，7 种物种相当 于7 个对象如表3 2 所示，如果将每个对象对应表中的记录，物种的特征对应表中的 属性，若物种拥有这种特征，则对应的对象拥有这种属性。其每个记录的所有属 性值是布尔型，取值为1 或0 ( 取1 表示事务中包含相对应的项，即该物种具有这种属 性；取0 表示该物种不具备这种属性) 。这样可以把物种数据库映射为一个等价的关 系数据库，生成的对象数据库的布尔型表如表3 3 所示。 表3 3一个简化的上下文转换的布尔值表 t a b l e3 3f o r m a lc o n t e x to fas i m p l i f i e db o o l e a nc o n v e r s i o n abcd ef g lloool oo 2loll lo0 3