超图研究专题.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

15、NSTITUTE OF E ENTERPRISES NTERPRISES B BUSINESS USINESS I INTELLIGENCENTELLIGENCEa类基元描述c类基元描述bc类基元描述 I INSTITUTE OF NSTITUTE OF E ENTERPRISES NTERPRISES B BUSINESS USINESS I INTELLIGENCENTELLIGENCE基于超图模型的模式识别机遇发现不仅有对事物属性的识别，更主要的是基于原型或图式所进行的模式识别。即人们希望得到的不仅只有简单的模式分类，还要有各个部分之间的关系，即事物的结构。要识别对象之间的各部分之间的联

16、系，需要使用结构模式识别方法。提取超图的线图，来描述基元关联，然后对线图进行同构判断。基于c类基元的个例描述 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基于超图模型的路径分析市场机遇能够通过新手段、新目标、以及手段目标关联的形成使新的商品、服务、原料、市场

17、和组织方法得以提出。Eckhardt and Shane,2003定义:超图系统模型中，目标顶点到其他顶点之间的一条超路径称为解超路。解超路就是候选机遇。可达矩阵：一个超图H=(V，E)的可达矩阵A满足下面的条件：（1）A的每一行与H的顶点相关；（2）A的每一列与H的顶点相关；（3）如果顶点vi、vj之间存在可达通路，即至少存在一条超路径，连着顶点vi、vj，那么 aij=1；否则aij=0.I INSTITUTE OF NSTITUTE OF E ENTERPRISES NTERPRISES B BUSINESS USINESS I INTELLIGENCENTELLIGENCE超路径的求解

18、方法 基于两点的超路径求解算法 基于起始点的超图路径求解算法本质上都是将超图化为二部图之后再求解超路径基于两点的超路径求解算法思想 I INSTITUTE OF NSTITUTE OF E ENTERPRISES NTERPRISES B BUSINESS USINESS I INTELLIGENCENTELLIGENCE构造树X1到X5之间的路径有21条得到X1到X5之间的超路径有11条.I INSTITUTE OF NSTITUTE OF E ENTERPRISES NTERPRISES B BUSINESS USINESS I INTELLIGENCENTELLIGENCE基于起始点的超

19、路径求解算法思想V-E-V表存储结构：二部图的V-E-V表存储结构：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实例分析求解V4到V15之间的超路径对于该超路径在市场机遇中的解释商业银行公司银行向零售银行转型的通常做法是：在对企业客户（v4）进行信贷调

20、查（e4）时获取企业领导（v8）的信息。通过为其办理储蓄业务（e6），建立储蓄账户（v13）。又由储蓄账户衍生多种个人理财业务（e7），从而发展为可能的私人客户（v15）。I INSTITUTE OF NSTITUTE OF E ENTERPRISES NTERPRISES B BUSINESS USINESS I INTELLIGENCENTELLIGENCE基于超图模型的信息吸取开放系统支持，与环境的信息交互如何将新图式和已有图式进行结合？认知主体对客观信息的认知或理解是否正确，不仅取决于新信息是否全面和真实，还取决于主体的知识结构是否适应客观信息，以及运用认知主体原有的知识结构对新信息的

21、过滤、加工、整理过程是否正确。超图模型采用具有严谨运算约束的关联矩阵形式和自然连接算子描述信息吸取。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考察h1

22、对该新信息的信息吸取，将新信息亦做建模处理得到 hnew。V1=（宏观政策，行业结构，优选行业，企业客户，综合授信，产品，合作企业，项目，项目贷款，财务，领导人，管理，储蓄账户，信用卡，私人客户）Vnew=（项目贷款，贷款优惠，交易协议，商品买卖，个贷业务）实例分析 I INSTITUTE OF NSTITUTE OF E ENTERPRISES NTERPRISES B BUSINESS USINESS I INTELLIGENCENTELLIGENCE求解V4到V15之间的超路径对于该路径的解释是：通过对房地产商（v4）的房地产开发项目（v12）进行公司贷款业务（e5），获得房地产开发后的

23、房贷优惠（v16）的发放权（e8），再通过房屋交易（e9）设计个贷业务（v19），通过个贷业务的账户绑定（e10）发展零售银行业务客户（v15）。由这条新的超路径可以发现房贷是商业银行转型的一个机遇。I INSTITUTE OF NSTITUTE OF E ENTERPRISES NTERPRISES B BUSINESS USINESS I INTELLIGENCENTELLIGENCE三、多粒度决策信息结构的超图表达基于超图系统的机遇发现决策支持粒度计算研究肖泉，蔡淑琴，叶波，吴颖敏情 报 学 报,2010,29(6):10231030研究的问题：基于复杂信息和知识的决策支持模式与决策支持

24、系统机遇发现决策信息的特性层级特性：粒度需求不同原始级：细粒度，信息单一、量大、不可再分知识级、决策级：粗粒度单一粒度不可行建立多粒度决策信息结构多元相关性：元素关联关系的描述超图一般图的推广以超边来描述顶点间的多元集合关系 处理非精确、不确定的多元性 I INSTITUTE OF NSTITUTE OF E ENTERPRISES NTERPRISES B BUSINESS USINESS I INTELLIGENCENTELLIGENCEQ：如何用超图理论来定义和计算信息粒度？粒度计算关注的两个问题如何构造粒度（粒度的形成、表示和语义解释）机遇发现的超图系统及其粒度描述如何利用粒度进行计算

25、（粒度运算法则及问题求解方法等）基于粒度计算的机遇发现决策支持模式 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四、超图结构的知识相似度计算基于超图结构的知识相似度计算模型研究 肖泉，蔡淑琴，叶波 情报学报,2010,

26、29(5):805812知识的表达：基于特征：“属性-值”对、特征向量、或带填充槽的框架优点：表示简单、检索高效、应用广泛缺点：将知识各特征视为相互独立的属性，不能描述知识内部结构基于结构：语义网、认知图、概念图 通过定义对象间的关联，描述知识内部结构缺点：经典图论方法只能描述二元关系超图：普通图的扩展，应用与GIS、任务规划等领域缺点：限于对知识的表示，缺乏后续研究 I INSTITUTE OF NSTITUTE OF E ENTERPRISES NTERPRISES B BUSINESS USINESS I INTELLIGENCENTELLIGENCE超图结构的相似度超图结构相似度的定义

27、对应，逆对应相似度 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五、UGC产品族设计问题基于超图设计模型的用户创造内容产品族设计映射研究蔡淑琴，马玉涛，肖泉，胡慕海情报学报（已录用）UGC产品族的设计 公

28、理设计理论 映射研究 超图建模 形式化描述 评价与优化 I INSTITUTE OF NSTITUTE OF E ENTERPRISES NTERPRISES B BUSINESS USINESS I INTELLIGENCENTELLIGENCE六、情境化推荐中的偏好漂移识别情境化推荐中基于超图模式的用户偏好漂移识别研究胡慕海，蔡淑琴，叶波，马玉涛情境化资源分析超图理论考虑时间因素情境化资源的超图模型表达带时间因子的情境化资源超图模型超图的相关操作资源、资源簇相似度的计算用户偏好漂移的识别方法 I INSTITUTE OF NSTITUTE OF E ENTERPRISES NTERPRIS

29、ES B BUSINESS USINESS I INTELLIGENCENTELLIGENCE讨论1.吴颖敏师姐的超图系统模型十分经典；2.无向超图比有向超图好用；3.任何复杂对象（信息、知识、偏好、产品）的结构都可以尝试用超图进行表达；4.超图研究的关键工具：邻接矩阵，关联矩阵，二部图；5.超图做研究的地方：建模与形式化表达，相似性度量6.尚未使用到的概念：对偶超图、伴随超图、孤立顶点、耳朵、超图的圈、超图的无圈分解、汉密尔顿超图7.其他人在研究：超图与超网络；基于超图的主题地图，基于超图的聚类，基于超图的蜂窝通信，分子超图 I INSTITUTE OF NSTITUTE OF E ENTERPRISES NTERPRISES B BUSINESS USINESS I INTELLIGENCENTELLIGENCE超图与基金（71071066）