（计算机应用技术专业论文）机会发现算法及其应用研究.pdf

d e n g r e s e a r c ho nc h a n c e d i s c o v e r ya l g o r i t h m a n di t sa p p l i c a t i o n c a n d i d a t e ：x uy u e z h u s u p e r v i s o r ：p r o f l i ud a x i n a c a d e m i cd e g r e ea p p l i e df o r ：d o c t o ro fe n g i n e e r i n g s p e ci a lit y ：c o m p u t e ra p p li e dt e c h n o l o g y d a t eo fs u b m i s s i o n ：d e c e m b e r ，2 0 0 9 d a t eo fo r a le x a m i n a t i o n ：m a r c h ，2 0 1 0 u n i v e r s i t y ：h a r b i ne n g i n e e r i n gu n i v e r s i t y 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由 作者本人独立完成的。有关观点、方法、数据和文献的引用己在 文中指出，并与参考文献相对应。除文中已注明引用的内容外， 本论文不包含任何其他个人或集体已经公开发表的作品成果。对 本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 作者( 签字) ：毛；缈了 日期：j 毋fd 年弓月6 日 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文门在授予学位后即可口在授予学位1 2 个月后口 解密后) 由哈尔滨工程大学送交有关部门进行保存、汇编等。 作者( 签字) ：捌扑弋导师( 签字) ：专叫卉坳乙7 日期：沙l0 年! 月，b 日沙l o 年岁月i 6 日 。 7 摘要 机会发现( c h a n c ed i s c o v e r y ) 是一个新的研究课题。机会发现的主要研 究内容是如何能从数据样本中发现对决策a g e n t 具有重要作用的偶发的或隐 藏的事件或情形。 通过对目前机会发现算法研究的分析和归纳，本文从机会发现算法发现 的机会事件出现在数据样本集和未出现在数据样本集的两个角度出发，分析 了相应经典算法的优缺点，提出了一些新的思想和算法，同时对机会发现的 形式化描述以及系统架构也作了相应的研究。 本文主要从以下几个方面作了研究： ( 1 ) 研究了机会的形式化描述方法。本文引入并拓展了模态逻辑，并基 于模态逻辑给出了逻辑语言l d k 。，利用l d k 。对机会进行了形式化描述。为 了更好的刻画机会的概念与特性，给出了逻辑语言l d k 。的可判定性和可满 足性算法证明过程，进一步说明逻辑语言l d k a 的有效性。 ( 2 ) 研究了出现在给定数据集中的机会发现算法。主要是对出现在给定 数据集中的，具有重要作用且出现频度小，但未被注意的那些事件或情形的 发现。利用小世界网络理论指导算法优化，有效提升算法的精确度和性能。 ( 3 ) 研究了未出现在给定数据集中的隐藏机会发现算法。主要是对未出 现在给定数据集中，同时与数据集中现有事件密切关联的具有重要作用的隐 藏事件或情形的发现，这种事件或情形的发现能够更好地去理解和解释现有 现象。引入加温退火法原理使得算法适用范围增大，同时提高了可解释的隐 藏事件的比例。 ( 4 ) 研究了机会发现系统架构。将智能a g e n t 技术引入了机会发现系统 架构中，在保留了机会发现经典的双螺旋模型的优点的同时，为系统更好地 实现提供了可行性方案，并可有效地提高系统的执行效率。 本文以专利说明书应用领域为背景，建立专利文献的情形图模型，并分 别去发现出现在样本集中和未出现在样本集中的候选机会，可将这种候选机 会当作一种创业机会加以应用，从而验证了上述机会发现算法与架构的合理 性、可行性及其优势。 哈尔滨t 稗人学博十学何论文 关键词：机会发现；算法设计；模念逻辑；小世界网络；加温退火法；智能 a g e n t 机会发现算法及其戍用研究 暑i i 宣i i i i i i i i ；i i i i i 宣置n , , - - i i i i 置i i ；i i i i i i i i i a b s t r a c t c h a n c ed i s c o v e r yi san e wr e s e a r c ha r e a i ti si m p o r t a n tt ot h er e s e a r c h c o n t e n to fc h a n c ed i s c o v e r y , w h i c hi sh o wt od i s c o v e re v e n t so rs c e n a r i o st h e s e a r ei m p o r t a n tt od e c i s i o na g e n tb u tr a r eo rh i d d e nf r o md a t as e t b yt h ea n a l y s i sa n dg u d yo ft h ee x i s t i n gc h a n c ed i s c o v e r ya l g o r i t h m s ， a d v a n t a g e sa n dd i s a d v a n t a g e so ft h ec l a s s i c a la l g o r i t h m sa r ea n a l y s e da n dn e w i d e a sa n da l g o r i t h m sa r ep r o p o s e di nt h i sp a p e r t h ef o r m a ld e s c r i p t i o no fc h a n c e d i s c o v e r ya n dt h es y s t e ma r c h i t e c t u r ea r e a l s og i v e ni nt h i sp a p e r t h em a i nr e s e a r c h e so ft h i sp a p e ra r eo nt h ef o l l o w i n g ： ( 1 ) r e s e a r c ho nt h ef o r m a ld e s c r i p t i o no fc h a n c ed i s c o v e r y t h em o d a ll o g i c i si n t r o d u c e da n de x t e n d e d ，a n dt h el o g i c a ll a n g u a g el d k ab a s e do nm o d a ll o g i c i sg i v e n t h ec h a n c ed i s c o v e r yi sd e s c r i b e db yu s i n gt h el d k al a n g u a g ea l s e i n o r d e rt og e tt h eb e a e rd e s c r i p t i o no ft h ec o n c e p ta n dc h a r a c t e r i s t i c so fc h a n c ea n d c h a n c ed i s c o v e r y , d e c i d a b i l i t ya n ds a t i s f i a b i l i t yp r o o f p r o c e d u r eo ft h el o g i c a l l a n g u a g el d k a i sg i v e n ，a n dt h ev a l i d i t yo fl d k ai sc l a r i f i e df u r t h e r ( 2 ) r e s e a r c ho nd i s c o v e r ya l g o r i t h mo fr a r ee v e n t s t h em a i nc o n t e n to f t h i s r e s e a r c hi sh o wt od i s c o v e rt h er a r ea n ds i g n i f i c a n te v e n t sf r o mt h eg i v e nd a t as e t o p t i m i z ea l g o r i t h mb ys m a l lw o r l dn e tt h e o r y ；i te f f e c t i v e l y e n h a n c e st h e a c c u r a c ya n dp e r f o r m a n c eo fa l g o r i t h m ( 3 ) r e s e a r c ho nd i s c o v e r ya l g o r i t h mf o rh i d d e ne v e n t s t h em a i nc o n t e n to f t h i sr e s e a r c hi sh o wt od i s c o v e rt h eh i d d e na n ds i g n i f i c a n te v e n t sf r o mt h eg i v e n d a t as e t t h e s eh i d d e ne v e n t sc a ng i v et h eb e t t e rw a yt ou n d e r s t a n da n di n t e r p r e t e x i s t i n gp h e n o m e n a b yi n t r o d u c i n gh e a t a n n e a l i n gt h e o r y , i ti n c r e a s e st h es c o p e o fa l g o r i t h ma p p l i c a t i o n ，a tt h es a m et i m e ，i n c r e a s e st h ep r o p o r t i o no fe x p l a i n a b l e h i d d e ne v e n t s ( 4 ) r e s e a r c ho nt h es o f t w a r ea r c h i t e c t u r e t h ei n t e l l i g e n ta g e n tt e c h n o l o g y i si n t r o d u c e di n t oc h a n c ed i s c o v e r ya r c h i t e c t u r e w h i l er e t a i n i n gt h ea d v a n t a g e s o fd o u b l eh e l i xm o d e l ，t h es y s t e mi m p l e m e n t a t i o np l a ni sp r o v i d e d i nt h i s p a p e r , p a t e n ts p e c i f i c a t i o n s ，a s t h ea p p l i c a t i o nb a c k g r o u n d ，t h e i r s c e n a r i og r a p hm o d e li se s t a b l i s h e d b a s e do nt h i ss c e n a r i og r a p hm o d e l ，c h a n c e 哈尔滨t 程大学博十学何论文 w h i c hi sr a r eo rh i d d e ni nt h ed a t as e ti sd i s c o v e r e d t h i sc h a n c ec a nb er e g a r da s t h eo p p o r t u n i t yf o rp i o n e e r i n gan e wc a u s e ，a n dt h eu n i q u ea d v a n t a g e so fc h a n c e d i s c o v e r ya l g o t i t h m sa n da r c h i t e c t u r ea r ec l a r i f i e d k e yw o r d s ：c h a n c ed i s c o v e r y ；a l g o r i t h md e s i g n ；m o d e ll o g i c ；s m a l lw o r l d n e t ；h e a t a n n e a l i n g ；i n t e l l i g e n ta g e n t rj 第l 章绪论一1 1 1 研究目的和意义1 1 2 机会发现概述3 1 2 1 机会的概念3 1 2 2 机会的特性3 1 2 3 机会发现与相关技术的关系4 1 3 国内外研究现状5 1 4 创业机会7 1 5 论文的组织结构与研究内容8 第2 章机会发现相关研究1 1 2 1 机会的形式化描述1 1 2 1 1 基于溯因推理的机会形式化描述1 1 2 1 2 基于l m 4 。的机会形式化描述1 3 2 2 机会发现算法1 3 2 2 1 机会发现理论1 3 2 2 2 机会发现几种重要算法1 4 2 3 机会发现系统模型2 4 2 3 1 发现过程描述2 4 2 3 2 双螺旋模型2 6 2 3 3 层次模型2 7 2 4 本章小结2 8 第3 章基于模态逻辑的机会形式化描述3 0 3 1 问题的提出3 0 3 2 基于模态逻辑的机会形式化描述3 0 3 2 1 模态逻辑31 3 3 2 逻辑语言l d k 。3 2 3 3 3 可判定性及满足性证明3 6 哈尔滨吲琵火学博十学位论文 3 3 4 机会形式化描述4 0 3 3 本章小结4 2 第4 章基于小世界网络的机会发现算法4 3 4 1 问题的提出4 3 4 2 相关研究基础4 4 4 2 1k e y g r a p h 算法4 4 4 2 2 小世界网络理论4 7 4 3 基于小世界网络的机会发现算法5 0 4 3 1 基于信息增益的权重描述方法5 1 4 3 2 关联图中边集优化方法5 4 4 3 3 基于偏好分布的重要词汇确定方法5 6 4 3 4 基于小世界网络的机会选定方法5 9 4 4 仿真实验与结果分析6 1 4 4 1 数据集描述6 1 4 4 2 参数及评价标准设置6 1 4 4 2 结果对比分析6 2 4 5 算法在科技专利说明书中的应用6 4 4 6 本章小结6 8 第5 章基于加温退火法的隐藏机会发现算法6 9 5 1 问题的提出6 9 5 2 相关研究基础6 9 5 2 1 数据结晶化算法7 0 5 2 2 加温退火算法7 3 5 3 基于加温退火法的隐藏机会发现算法7 4 5 3 1 算法思想7 4 5 3 2 基于加温退火法的隐藏机会发现算法7 5 5 3 3 算法描述7 6 5 4 仿真实验与结果分析8 0 5 4 1 数据集描述8 0 用研究 8 ( ) ；：2 5 5 算法在科技专利说明书中的应用8 4 5 6 本章小结8 7 第6 章基于智能a g e n t 的机会发现系统架构8 8 6 1 问题的提出8 8 6 2 基于智能a g e n t 的机会发现系统构架8 8 6 2 1 系统架构9 0 6 2 2 智能a g e n t 的任务描述9 0 6 2 3 系统架构与双螺旋模型的对比9 3 6 3 智能a g e n t 间的通信模型和合作协议9 4 6 3 1a g e n t 通信模型9 4 6 3 2a g e n t 合作协议9 5 6 3 3a g e n t 消息机制9 5 6 4 本章小结9 8 结论9 9 参考文献1 0 1 攻读博士学位期间发表的论文和取得的科研成果1 11 致 谢1l3 个人简历1 1 4 1 | 第1 章绪论 1 1 研究目的和意义 第1 章绪论 世界是普遍联系的整体，这种联系就是指一切事物的本质和现象之间都 有着千丝万缕的关系，它们之问相互影响、相互制约以及相关依赖。也就是 说，世界上任何一个事物或是现象都不能孤立地存在着，都必然存在于与某 些相关事物和现象的联系当中。这种对系统未来结果造成影响的事件的事前 判定变得尤为重要。例如：上个世纪8 0 年代，日本神户附近发生了一系列的 小地震，人们没有意识到这是什么含义，也没有意识到会带来什么危害，其 实这是由于神户地区的地壳承受的压力过大造成的，终于在1 9 9 5 年，在神户 发生了7 2 级地震，造成了非常巨大的损失。如果当初人们意识到小震和大 震的联系，那么这样的灾难所带来的损失会大大减少。这就说明，对事物之 间的联系的发现有着非常重要的作用。 这种导致系统结果受到明显波动的事件也可以用现有技术利用预测方法 进行判断其对系统结果的影响力的大小。目前来说，对重要事件的发现多数 基于数据挖掘中的预测技术，这种技术可以解决系统预测问题，但其前提是 必须拥有大量数据样本可供分析处理。但有时实际系统中可能在少数数据出 现时，其中就存在可对系统未来有着至关重要作用的事件，如何将其提取出 来，是当前需要着手解决的问题。尤其在对于没有任何历史数据可以利用的 情况下，如何去发现这样的联系并对其加以利用更是引起各领域专家的关注。 对那些低频度的重要事件不但不应该将其看作是数据样本中的噪音，而且更 应该关注这些事件对未来决策的重要性。 “机会发现”( c h a n c ed i s c o v e r y ，简称c d ) 就是在这样一个应用环境下， 由日本学者o h s a w a 于2 0 0 0 年提出的【1 ，2 】，他是基于多学科中的共同问题 环境的动态不确定性对a g e n t ( 或人) 的决策的影响而提出的一个新的 概念，以期通过对机会发现的理论和相关技术的研究，为多领域能够提供一 个新的解决思路和可以替代的解决方法。“机会 ( c h a n c e ) 指的是一个对决 哈尔滨r 程大学博十学位论文 策支持有重要影响的事件或情形，这种事件或情形町能是机遇( o p p o r t u n i t y ) 也可能是风险( r i s k ) 。其中，机遇能够对决策起着促进作用，而风险则是能 够对决策起着抑制作用。因此，机会的本质，不管是机遇还是风险，都是引 起未来发生重要变化的因素。 当这种机会是罕见的且其重要性被忽视时，机会发现是指对机会的重要 性的理解和解释。那些有益的机会将促使其发生，而那些风险则要对其采取 预防性措施。机会发现是一个过程1 3 1 ，即学习和解释一个事件何以成为机会 的过程。机会发现的目标不仅仅是预测未来，而更为重要的是改变未来。机 会发现提供了一种手段，使得人们能够在未来继续生存并且得到更好的发展。 由于机会发现试图解决的问题是多个学科共同关注的问题，涉及了很多 领域长期以来遇到的瓶颈性问题，因此一经提出就引起了来自不同领域的研 究者的注意，并且越来越受到重视。2 0 0 0 年召开了第一次关于机会发现的国 际研讨会，主要议题是机会的定义、机会发现的应用、人物行为分析、复杂 系统分析以及机会发现的逻辑基础等。至今为止每年都召开机会发现相关的 国际研讨会【4 】，每次会议的研究主题都围绕着如何发现机会及管理运用机会。 已有的工作包含机会发现对具体应用领域的需求分析，讨论较多的领域包括 网络信息挖掘【5 , 6 , 7 , 8 , 9 , 1 0 】、自然灾害模拟【1 1 , 1 2 , 1 3 , 1 4 】、商业机遇发现【1 5 , 1 6 , 1 7 , 1 8 , 1 9 】、 企业破产预防【2 0 2 1 2 2 1 、医护应用2 3 2 4 , 2 5 , 2 6 , 2 7 1 和教学效果促进【2 8 , 2 9 1 等方面3 0 1 。 总的来说，机会发现作为一个全新的研究领域，越来越多的学者表现出 对它的兴趣，也开始逐步开展了相关研究。对机会发现算法的研究可以提高 对事件的敏感度，从而会发现并利用机遇或者规避风险的发生。因此，进行 机会发现算法的研究以及在专业领域中的应用研究具有重要的理论意义和现 实意义。 本文所进行的机会发现算法研究的对象是文本数据，期望在文本数据中 发现具有重要性的偶发事件，即在文本数据中出现频度小或隐藏的但具有很 高重要性的词语。本文数据可以看作是由多个句子所构成，每个句子又由词 语构成。词语分为对文本语义有贡献的词语和无意义词语两种，本文关注是 有意义的词语。而文本数据涉及的范围不仅是一篇文章，其它的一些记录信 息也可以作为文本数据对待。例如，医生诊断的处方，每个处方都可以作为 一个句子，处方中的各组成部分可以作为词语。另如，消费者的购买记录也 2 第1 辛绪论 可以作为文本数据来对待，一次购买记录看作一个句子，记录中的商品看作 一个词语。这样本文所讨论并展开研究工作的是这样情况的文本数据。在这 样数据集中，为了简化理解和便于实践，将词语看作是事件或情形，那么在 此前提下，此时的机会指的是在文本数据中的具有重要作用的稀少词语，机 会发现是对于这样的词语发现和解释的一个过程。 1 2 机会发现概述 1 2 1 机会的概念 所谓机会就是这样一些事件或情形【3 l 】，它们在特定时间里在特定环境下 在特定领域中对于人或a g e n t 的决策起着重要作用，这种作用有可能是对决 策有好的作用，也有可能对决策起到相反的作用。无论机会对决策的作用是 促进还是抑制，机会都具有这个“对决策具有重要作用 的特性。此外，强 调了机会的稀少性和不易被注意的特性，也从另一个侧面描述了机会不一定 能从以往的经验模式中得出。 1 2 2 机会的特性 现有的机会发现相关文献都仅能表述机会的各个特性1 3 2 】，如下归纳。 ( 1 ) 重要性( 影响性) 首先明确的是机会是指包含一些特定意义的事件或情形，这些事件或情 形可以加速或减缓另一些事件或情形的发生，进而影响整个系统的决策，也 就是说对整个系统有着很重要意义。该事件或情形的执行能导致系统最终结 果的实现速度，甚至实现结果的优劣。重要性是机会的重要特性之一，也正 因为其对系统至关重要，也是研究机会发现的意义所在。 ( 2 ) 稀少性 稀少性意味着机会事件的出现频率不高，不是一个高概率事件，不能通 过以往的传统的规划方法来进行刻画这种事件或情形。对于一个高概率事件， 尽管可能它的影响很大，但是由于人们事先有对它有所意识，所以可能对它 所能造成的意外影响就会小的多。然而，由于机会具有稀少这样的特性，才 3 哈尔滨t 稃大学博十学何论文 使得人们识别和利用机会变得凼难，未能识别出而所带来的意外影响相对来 说会更大，这样使得发现机会变得具有重要的意义。 ( 3 ) 不确定性 机会对于系统决策有着重要的影响，但这种影响不可能能够利用现有技 术来准确预测机会的影响，也就是说，影响是具有局限性的，机会事件对目 标的影响结果是不确定的，即有可能按照预期方式促进决策的执行，但也有 可能导致决策的失败。 ( 4 ) 时效性 对于一个特定的机会事件来说，它可能在某个特殊的时间内有效，过了 某个时刻，所谓的机会可能已经失去了意义。比如，地震预报在震前尤为重 要，过了某个时刻，即地震发生后，这个震前特定事件就没有了重要的意义。 因此，如何在一个有限的时间内发现机会，并加以利用也是一个非常重要的 问题。 ( 5 ) 可控性 被称为是机会的事件或情形，是可以改变未来系统状态或决策的事件或 情形。该事件或情形被捕捉后，可以对其加以利用，使其能够使情况向好的 方向发展或避免向坏的方向发展。而且机会必须要做到这一点，若一个完全 不可控的事件，可以认为不是机会。 1 2 3 机会发现与相关技术的关系 1 、机会发现与人工智能 机会发现与人工智能有着密切的关系。人工智能p 3 j 随着应用的需求的不 断增多，原来静态的条件不能满足需要，取而代之的是对于动态环境的描述 以及相应的研究，应运而生的是多a g e n t 系统。 多a g e n t 系统具有自主性、分布性、协调性，并具有自组织能力、学习 能力和推理能力【3 4 】。采用多a g e m 系统解决实际应用问题，具有很强的鲁棒 性和可靠性，并具有较高的问题求解效率。多a g e n t 系统在表达实际系统时， 通过各a g e n t 间的通信、合作、互解、协调、调度、管理及控制来表达系统 的结构、功能及行为特性。在实际应用中常用的是多a g e n t 系统，将各种具 有不同能力的a g e n t 结合起来，通过它们之间的相互作用，既分工又协作， 4 弋 。 第1 章绪论 共同解决f 、口j 题。 这里每一个a g e n t 都有着自己独立的信念和工作意图。这种情况下，在 机会发现理论中，发现对a g e n t 有着促进和抑制作用的事件可能给人工智能 的研究带来一种新的思路和方法。与此同时，人工智能中的一些成熟的理论 和技术对于机会的发现等问题也是具有可借鉴的作用。 2 、机会发现与知识发现 机会发现与知识发现的本质区别一直是机会发现提出来以后存在争议的 问题。有的研究学者认为机会发现所有解决的问题，知识发现也能够进行处 理，并且知识发现经过多年的实践，发展出了一系列相对比较成熟的理论和 技术。 o h s a w a 认为机会发现是一个不同于传统的知识发现的一个新的课题。这 是因为，传统的知识发现技术使用过程中，存在一个前提，就是已经存在了 一个庞大的数据仓库的基础上【35 。然而，机会发现则强调的是在少量数据样 本中，在没有历史数据可以利用的前提下，如何去发现对未来的决策具有重 要作用的事件或情形。尤其是对于出现频度低未被注意的事件的发现。 机会发现与知识发现有着以下方面的不同： ( 1 ) 知识发现是在数据集当中识别出有效的最终可理解的模式，是对数 据及数据之间关系的一种静态描述。而机会发现是对事件及其结果的动态刻 画，是对未来行为的选择和向导，也就是说，机会发现的本质就是建立在a g e n t 的目标基础上的关系的描述。 ( 2 ) 知识发现本质上得到的是对于历史知识的解释性结论。即使存在预 测的描述，那也是建立在有这种模式的历史资料的基础上总结出来的。而机 会发现要处理的很多数据是没有任何或者很好的历史资料的前提下，是属于 一个全新的事件。 当然，不能否认的是知识发现和机会发现在作用上有着很多的相似性， 而且知识发现的成熟技术对机会发现也是有这很好的借鉴作用。 1 3 国内外研究现状 经过从概念提出至今的近十年时间里，机会发现和机会管理( c h a n c e 5 哈尔滨一f ：秤大学博十学位论文 d i s c o v e r ya n dc h a n c em a n a g e m e n t ，简称c d & c m ) 的研究还处于起步阶段， 自2 0 0 0 年起，每年都要进行机会发现& c m 相关研究内容的国际会议，每年 基于知识的智能工程系统( k e s ) 大会上都有机会发现相关的专题研讨会。 除了机会发现概念的提出者o h s a w a 在带领的团队逐年都在进行深层度研究， 中国科学技术大学3 6 , 3 7 , 3 8 , 3 9 】、哈尔滨工程大学 4 0 , 4 1 , 4 2 】等大学也在进行机会发现 的研究工作。目前，机会发现已成为具有潜力的研究技术，其研究内容主要 包括以下几个方面。 1 机会发现系统模型 随着机会发现的影响力在学术界的日益扩大，如何去构建一个机会发现 系统，如何能够正确表述机会发现过程开始得到专家的关注。在现有的知识 发现过程【4 3 1 基础上，针对机会发现的需要提出了双螺旋模型【删，层次模型【6 】 等。架构的形式不同，但是各种架构模型都对机会发现过程中的人机交互特 性均有描述。对目前模型存在缺乏可实践性的缺陷，需要对问题进行思考并 深入研究。研究内容为如何构建更好的可以描述机会发现过程的架构，并且 结合当前其它学科成熟技术为系统的实现提出可行性方案。 2 机会的形式化描述 形式化描述提供了强有力的分析和抽象能力，具有与实现的细节无关性 等特点。现有的形式化描述未能达到共识，因此，如何将机会概念以及特征 进行抽象是机会发现的研究内容之一。虽然机会形式化描述工作有了很大进 剧4 5 , 4 6 , 4 7 , 4 8 1 ，如何定义机会的本质特征，如何对机会发现各阶段进行形式化 描述，如何实现从形式化描述的抽象层到带有应用领域特性的具体层转换， 这些都仍然是值得深入研究的问题。 3 机会发现算法的研究与设计 机会发现算法是本领域研究的重要内容之一。算法考虑的是如何将出现在 数据样本q b f 4 9 , 5 0 , 5 1 1 和未出现在数据样本【5 2 , 5 3 , 5 4 1 t 扣的机会找到，并尽可能多的找 到符合机会特征的事件或情形。现在有的机会发现算法的研究主要针对于确 认发现的是机会，而没有过多地关注如何更有效、更便捷地发现机会性 能上的提高为机会发现提出了新的挑战。如何在算法中更完整的表述机会特 性，在发现过程中对此特性进行关注，是机会发现算法需要完善的地方，也 是值得深入研究的问题。 6 1 k ：i lhl 第1 章绪论 机会 机会发现的提出是由于其有着很广泛的应用领域，更为显著的应用是在 经济领域中商业机遇的发现，也可具体化为创业机会的发现。即如何研究创 业机会的选定。机会的识别与开发是创业过程的开端，被认为是创业研究的 中心问题。本文是将创业机会的发现作为机会发现算法的应用对象，进而说 明机会发现具有重要的现实意义。现将创业机会简单描述如下。 创新与创业是推动经济发展与社会进步的主要力量之一。随之而来的创 业研究从2 0 世纪8 0 年代开始，日益受到各国政府和学者们的普遍关注。创 业是一个跨越多学科领域的复杂现象，对此研究的基础理论比较宽泛，包括 管理学理论、心理学理论、社会学理论、经济学理论等等。 创业机会的出现往往是因为环境的变动、市场的不协调或混乱、信息的 滞后、领先或缺口，以及各种各样的其他因素的影响的。机会观本身还缺乏 一个清晰的概念和理论基础用以解答上述问趔”j 。也就是说，在一个自由的 企业系统中，当行业和市场中存在变化着的环境、混乱、混沌、矛盾、落后 与领先、知识和信息的鸿沟，以及各种各样其他真空时，创业机会就产生了， 如技术革新，消费者偏好的变化，法律政策的调整，等等。总的来说，以上 几种因素可归纳为技术机会、市场机会和政策机会三类创业机会。 技术机会，即主要源自新的科技突破和社会的科技进步，由技术变化带 来的创业机会。通常情况下，技术上的任何变化，或者多种技术的组合，都 可能给创业者带来某种商业机会。具体表现在三个方面：( 1 ) 新技术代替i e l 技术。当在某一个领域中出现了新的技术突破和技术，并且它们足以代替某 些旧技术的时候，创业机会就随之而来了。( 2 ) 实现新功能、创造新产品的 新技术的出现。这本身就意味着给创业者带来新的商机。( 3 ) 新技术带来的 新问题。有些新技术的出现对人类都既有利也有弊的两面性，即在给人类带 来生活质量上的提高的同时，也会给人类带来某些新的问题。这就会迫使人 们为了消除新技术带来的某些弊端，再去开发新的技术并使其商业化，这就 会带来新的创业机会。 市场机会，即市场变化产生的创业机会。一般来看，主要有以下四类： 7 卜i i 哈尔滨丁程大博十学何论文 ( 1 ) 市场上出现了与经济发展阶段有关的新需求。( 2 ) 当期市场供给缺陷产 生的新的商业机会。( 3 ) 先进国家( 或地区) 产业转移带来的商业机会。( 4 ) 从中外比较中寻找差距，差距中往往隐含着某种商机。 政策机会，即政府政策变化所赐予创业者的商业机会。随着经济发展、 科技变革等，政府必然也要不断调整自己的政策，而政府政策的某些变化， 就可能给创业者带来新的商业机会。 其中，政策机会和市场机会有着很多的人为因素，是不可通过计算机来 辅助来进行完成发现的。只有技术创新机会，可以通过计算机辅助来完成。 对于现有的专利说明书中创新技术进行分析可以从中发现创业机会，也就是 说，试图从专利说明书中发现常人未曾发现的潜在特性，进而可以占领先机， 抓住创业机会，为创业开辟一条可行的道路。即，当前关注技术机会中的技 术创新方面，旨在发现创新特性给出相应的创业机会，供更多的企业去选择 并对其进行商业化推广。 在本文中，创业机会特指技术创新机会。从实际意义上说，机会发现的 研究为了发现创业机会提供了一种很好解决方案。 1 5 论文的组织结构与研究内容 本文主要围绕机会发现展开研究。包括基于模态逻辑的机会形式化描述、 基于小世界网络的机会发现算法、基于加温退火法的隐藏机会发现算法，以 及基于智能a g e n t 的机会发现系统架构。图1 1 给出了本文的组织结构。 本文共分6 章，各章的内容简单概括如下： 第1 章首先介绍了本文的研究目的及意义；其次介绍了机会的概念及特 性，以及国内外研究现状及其存在的问题：接着介绍了创业机会的概念，说 明可以采用机会发现为创业机会的选定提供解决方案；最后给出了论文的组 织结构与研究内容。 第2 章介绍了机会发现相关研究，包括机会形式化描述、发现算法以及 机会发现系统架构，为后面在这三个方面的展开进一步研究打下基础。 第3 章研究基于模态逻辑的机会形式化描述。首先，说明模念逻辑能够 很好的描述机会发现的相关特性；其次，提出了在模态语言中引入新的模态 8 lk 第1 章绪论 算子和推理规则而形成的l d k 。逻辑语言；接着，给出了该逻辑语言的可判 定性和可满足性证明，说明该l d k 。逻辑语言是有效的；最后，给出了在l d k a 逻辑下的机会及机会发现的定义。 形式化定义一 i 基于模态逻辑的机会形式化描述 阂k 蒜研究旧描l 绪论f1 机会发现相关研究 算法猫述 回 系统实现架构篓函龇铋l 的机会发现系统架构l 图1 1 论文的组织结构 f i g 1 1s t r u c t u r eo ft h ed i s s e r a t i o n 第4 章研究基于小世界理论的机会发现算法。首先，对于现有经典的机 会发现k e y g r a p h 算法进行了详细描述，并指出该算法存在的一些问题；其 次，对于这些问题，提出了基于小世界理论的机会发现算法，这罩仅仅关注 有改善的细节的描述；接着，通过仿真实验结果说明改进后的算法在各方面 都优于原先算法；最后，将该算法应用到了专利说明书中，利用该技术去发 现专利说明书中重要而稀少的那些特性，从而提供创业机会。 第5 章研究基于加温退火法的隐藏机会发现算法。首先，描述数据结晶 化算法的优缺点，对于其缺点进行改进；其次，提出加温退火法的隐藏机会 发现算法，对于该算法的处理流程进行详细描述，并给出具体判定的算法描 述；接着，通过仿真实验结果说明该算法在性能上比原来算法有了很大的改 进；最后，将该算法应用到多个专利说明书中，利用该技术去发现潜藏在相 关领域的专利文献中，可能存在的潜在的专利特性，从而可以提供关于技术 创新的创业机会。 第6 章研究基于智能a g e n t 的机会发现系统架构：首先，引入更加灵活 的智能a g e n t 来代替机会发现双螺旋过程中局部人机交互环节，并详细描述 9 哈尔滨i ：程人学博十学何论文 了系统中各个智能a g e n t 所具有的功能；其次，利用简洁有效的通讯机制来 保证智能a g e n t 问通讯准确无误，实质上是提出了机会发现系统的实现机制， 而该系统架构可以使系统实现更加具体化和形象化。 最后是对本文的总结及一些关于进一步工作研究方向的思考和建议。 一 i h 第2 章机会发现相关研究 第2 章机会发现相关研究 以认知理论为基础的机会发现具有一定数学表示形式，然而由于其机会 事件的定义、求解方法等问题，使其性能受到一定的影响。机会发现的学习 研究刚刚兴起，其目的在于通过对数据中的“对决策a g e n t 具有重要作用”并 且具有“稀少和不易被注意”的特性的那些事件或情形进行发现。本章简要 介绍了机会形式化刻画理论、机会发现算法、机会发现系统架构，为后续研 究工作奠定基础。 2 1 机会的形式化描述 机会是对a g e n t 具有重要影响的事件或情形。因此说，机会的存在必然 要和a g e n t 之问存在着某些必要的内在的联系，而这种联系称之为机会发现 相关性，即机会发现相关性是确定某个事件或情形能够成为机会的必要条 件。为了使得形式化描述方便和准确，本文也可以认定机会发现相关性就是 某个事件或情形成为机会的充分条件。 2 1 1 基于溯因推理的机会形式化描述 溯因( a b d u c t i o n ) 的概念最初是由哲学家p e i r c e 提出来的【5 6 】，他是这样 来刻画溯因的：c 是一个意外的现象；如果a 成立，则c 的成立便可以得到 解释；那么假设a 成立是合理的。溯因推理【5 7 】( a b d u c t i v er e a s o n i n g ) 是一 种不同于演绎推理和归纳推理的推理形式，是研究如何从已知结论生成可能 假设的推理形式。一般来说，溯因推理可以写成如下形式。 坐型坐 ( 2 1 ) 矽 公式( 2 一1 ) 表示：如果已知妒能蕴涵沙，且当前有事实沙，则假设缈在 当前成立是合理的。 p o p l e 在1 9 7 3 年首次将溯因推理引入到人工智能领域中【5 8 】，并且随后由 c h a m i a k 和m c d e r m o t t 对其进行了相应的修改【5 9 1 。由这些人把溯因推理的地 哈尔滨t 稃大学博十学何论文 位提高到与演绎推理和归纳推理并列的第三种推理形式。 日本学者a b e l 4 5 】首次把溯因推理引入机会发现，并且从信念变化的角度 来刻画机会和机会发现，给出了“如何定义一个机会和“如何发现这些机 会 两个问题的解答。对于前者，他把机会定义成能够用来解释未知事件的 假设。对于后者，他通过综合溯因推理和