超图研究专题.ppt
《超图研究专题.ppt》由会员分享,可在线阅读,更多相关《超图研究专题.ppt(42页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、B BI IE EE E超图研究专题王 旸2011年4月7日 I INSTITUTE OF NSTITUTE OF E ENTERPRISES NTERPRISES B BUSINESS USINESS I INTELLIGENCENTELLIGENCE一、超图的基本理论问题图论图论是离散数学的一个分支,超图超图是离散数学中最一般最一般的结构。18世纪数学家欧拉(Euler)对“Konigsberg七桥问题”的建模和分析开创了数学中图论这一分支的研究。图是由若干给定的点及连接两点的线所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系,用点点代表事物事物,用连接两点的线线表示相应两个事
2、物间具有这种关系关系。在运筹学的网络系统分析网络系统分析中,对最短路径、最大流、最小费用流等方面有了一些解决实际问题的研究。在数据结构数据结构中,为方便在计算机上处理和分析图,研究了图的存储结构、遍历等问题。在某些情况下,一般图并不能完全刻画真实世界网络的特征。多人(3人)合作撰写论文。ABABCABCXABC I INSTITUTE OF NSTITUTE OF E ENTERPRISES NTERPRISES B BUSINESS USINESS I INTELLIGENCENTELLIGENCE超图的主要概念 超图和简单超图 超图的表示方法 对偶超图 超图的阶、秩 一致超图 部分超图 子
3、超图 伴随超图 孤立顶点 耳朵 超路径、超链、超回路 关联矩阵 邻接矩阵 I INSTITUTE OF NSTITUTE OF E ENTERPRISES NTERPRISES B BUSINESS USINESS I INTELLIGENCENTELLIGENCE超图 Hypergraphs I INSTITUTE OF NSTITUTE OF E ENTERPRISES NTERPRISES B BUSINESS USINESS I INTELLIGENCENTELLIGENCE超图的表示超图主要有五种表示方法:图形表示(结构简单时较清晰直观,但表示方法不统一)关联矩阵表示(结构化,稀疏矩
4、阵,信息完备)二部图表示(直观,信息完备,但顶点的同质性消失)线图表示(超边的关系清晰,但顶点消失)连接树表示(关系表示清晰,信息完备,但不利于计算机处理)超图的图形表示超图的关联矩阵表示 I INSTITUTE OF NSTITUTE OF E ENTERPRISES NTERPRISES B BUSINESS USINESS I INTELLIGENCENTELLIGENCE超图的表示方法(续)超图的图形表示超图的二部图表示超图的线图表示超图的连接树表示 I INSTITUTE OF NSTITUTE OF E ENTERPRISES NTERPRISES B BUSINESS USINE
5、SS I INTELLIGENCENTELLIGENCE对偶超图e1e2e3e4v1v2v3v4v5v6v7v8 I INSTITUTE OF NSTITUTE OF E ENTERPRISES NTERPRISES B BUSINESS USINESS I INTELLIGENCENTELLIGENCE超图的超路径、超回路 I INSTITUTE OF NSTITUTE OF E ENTERPRISES NTERPRISES B BUSINESS USINESS I INTELLIGENCENTELLIGENCE超图的关联矩阵、邻接矩阵关联矩阵一个超图H=(V,E)的关联矩阵B满足下面的条件
6、:(1)B的每一行与H的顶点相关;(2)B的每一列与H的边相关;(3)如果第j个边与第i个顶点相关联,那么bij=1.邻接矩阵一个超图H=(V,E)的邻接矩阵S满足下面的条件:(1)S的每一行与H的顶点相关;(2)S的每一列与H的顶点相关;(3)如果顶点vi、vj之间存在一个关系,即存在一个弧,连着顶点vi、vj,那么 sij=1;否则sij=0.I INSTITUTE OF NSTITUTE OF E ENTERPRISES NTERPRISES B BUSINESS USINESS I INTELLIGENCENTELLIGENCE二、先验知识的超图系统建模机遇发现的超图建模及应用蔡淑琴,
7、吴颖敏管理学报,2009,6(11):14491454规划视角的市场机遇发现超图模型蔡淑琴,吴颖敏系统工程,2008,26(12):5761市场机遇发现的超图路径及其应用蔡淑琴,吴颖敏,程全胜武汉理工大学学报(信息与管理工程版),2008,30(6):923927Research on Market Opportunity Discovery Methods:A Perspective of Information ConstraintCai Shuqin,Wu Yingmin2007 The Sixth Wuhan International Conference on E-Business
8、(WHICEBE 2007):13061311Hypergraph Model of prior knowledge in opportunity discoveryWu Yingmin,Cai Shuqin2008 International Symposium on Knowledge Acquisition and Modeling(KAM 2008):216220A Hypergraph Model for Market Opportunity DiscoveryWang Yang,Wu Yingmin,Cai ShuqinThe Fourth International Joint
9、Conference on Computational Sciences and Optimization(CSO 2011):322326市场机遇发现的超图支持方法研究吴颖敏华中科技大学博士学位论文(管理科学与工程),2009,4 I INSTITUTE OF NSTITUTE OF E ENTERPRISES NTERPRISES B BUSINESS USINESS I INTELLIGENCENTELLIGENCE I INSTITUTE OF NSTITUTE OF E ENTERPRISES NTERPRISES B BUSINESS USINESS I INTELLIGENCEN
10、TELLIGENCE超图系统模型 I INSTITUTE OF NSTITUTE OF E ENTERPRISES NTERPRISES B BUSINESS USINESS I INTELLIGENCENTELLIGENCE构建顶点对超边的关系G 是建立机遇发现超图模型的关键步骤。根据顶点关系结构的明确性不同有两种构造方式:对于可以预先清晰定义的关系模式,采用先超边后顶点的构造方式,即先确定超图系统关系模式,描述为超边,进而在顶点集中搜寻各关系模式相关联的顶点。对于无法预先定义关系模式的情形,则通过对顶点进行信息挖掘以寻求其之间的关系模式,常见的信息挖掘方法包括聚类挖掘、频繁模式挖掘等等,这
11、种关系构造方法的结果是对象间潜在隐性的关系,因此具有非精确、不稳定的特性,往往需要通过不断的学习过程提高模式挖掘的精确性。I INSTITUTE OF NSTITUTE OF E ENTERPRISES NTERPRISES B BUSINESS USINESS I INTELLIGENCENTELLIGENCE I INSTITUTE OF NSTITUTE OF E ENTERPRISES NTERPRISES B BUSINESS USINESS I INTELLIGENCENTELLIGENCE I INSTITUTE OF NSTITUTE OF E ENTERPRISES NTER
12、PRISES B BUSINESS USINESS I INTELLIGENCENTELLIGENCE超图系统模型的特点 简单的形式化工具,让子类共享、结构遗传 对关系描述能力的拓展 具有柔性的结构 完整性的语义约束 支持开放系统的特性和决策支持能力的扩展 I INSTITUTE OF NSTITUTE OF E ENTERPRISES NTERPRISES B BUSINESS USINESS I INTELLIGENCENTELLIGENCE建模实例郑州市某商业银行支行商业银行未有统一描述的公司银行业务模式可以作为图式建模将来自该商业银行支行关于公司银行业务的资料通过预处理后,得到15个实
13、体:“宏观政策”、“行业结构”、“优选行业”、“企业客户”、“产品”、“合作企业”、“项目”、“领导人”、“财务”、“管理”、“综合授信”、“项目贷款”、“存储账户”、“私人客户”、“信用卡”。基于频繁项集构建超图不但更加简化超图结构,而且比基于事务构建的超图更能体现数据项之间的关系。因为频繁项集捕获的是支持度大于阈值的数据项的集合,是根据全局关系信息构建起来的。为了使对应超图是简单超图,选定最大频繁项集作为超边。支持度为30(经验值)。由于最大频繁项集本身不具备方向,故用无向超边表示。I INSTITUTE OF NSTITUTE OF E ENTERPRISES NTERPRISES B
14、BUSINESS USINESS I INTELLIGENCENTELLIGENCE I INSTITUTE OF NSTITUTE OF E ENTERPRISES NTERPRISES B BUSINESS USINESS I INTELLIGENCENTELLIGENCE基于超图模型的结构描述结构模式方法是对一个模式从结构上进行描述,即解释一个模式是如何由一些简单的子模式即模式基元组成。由于现实中的管理问题一般抽象于包含多个因素及相互关联的复杂系统,因此要在管理领域应用结构模式识别首先需要提出新的基元定义以及结构描述方法。超图模型可以满足描述不同基元的要求 I INSTITUTE OF
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 超图 研究 专题
限制150内