计算机科学

计算机科学 ›› 2025, Vol. 52 ›› Issue (4): 147-160.doi: 10.11896/jsjkx.240100084

• 数据库&大数据&数据科学 • 上一篇    下一篇

基于超图的知识提取算法

刘川1, 杜宝苍2, 毛华1   

  1. 1 河北大学数学与信息科学学院 河北 保定 071002
    2 河北金融学院管理学院 河北 保定 071051
  • 收稿日期:2024-01-08 修回日期:2024-07-12 出版日期:2025-04-15 发布日期:2025-04-14
  • 通讯作者: 毛华(mh@hbu.edu.cn)
  • 作者简介:(18811527086@163.com)
  • 基金资助:
    国家自然科学基金(61572011)

Knowledge Extraction Algorithm Based on Hypergraphs

LIU Chuan1, DU Baocang2, MAO Hua1   

  1. 1 College of Mathematics and Information Science,Hebei University,Baoding,Hebei 071002,China
    2 College of Management,Hebei Finance University,Baoding,Hebei 071051,China
  • Received:2024-01-08 Revised:2024-07-12 Online:2025-04-15 Published:2025-04-14
  • About author:LIU Chuan,born in 1997,master candidate.His main research interests include hypergraph and formal concept analysis.
    MAO Hua,born in 1963,Ph.D,professor.Her main research interests include rough sets,formal concept analysis and hypergraph.
  • Supported by:
    National Natural Science Foundation of China(61572011).

PDF (PC)

101

摘要： 知识提取一直是计算机领域研究的主题之一,然而现有的一些知识提取方法还不能满足可视化以及潜在知识的提取两方面的实际需求。众所周知,知识是由可定义知识和潜在知识组成,并且可定义知识可以在潜在知识的提取过程中同时得到,反之则不然。有关可定义知识的提取目前已有许多成果,但针对潜在知识的提取的研究相对较少,特别是如何通过可视化方法提取潜在知识是一个急需解决的问题。为此,文中利用超图的可视化特点,在信息系统的背景下,探究了信息系统与超图之间的对应关系,并且给出了两者之间相互转化的方法。利用此方法,结合超图理论与粗糙集理论,定义了基于超图的一对上下近似算子,进一步地,提出近似超图的概念,探究近似超图的相关性质,完成近似超图的构建,并在此基础上创建了一种有效方法以实现超图框架下的知识提取。将所提方法与经典的和新近提出的近似理论以及知识提取方法进行了对比,结果表明所提方法在近似方案和知识提取等方面具有多种优势。通过实际案例验证了所提方法的正确性,从而说明了其可应用性。所提方法是现有的知识提取理论的发展和补充。

关键词: 知识提取, 信息系统, 超图, 近似超图, 可视化方法

Abstract: Knowledge extraction has always been one of the topics in computer science research.However,some existing know-ledge extraction methods are not sufficient to meet the practical needs in terms of visualization and latent knowledge extraction.It is well known that knowledge consists of definable knowledge and latent knowledge,and definable knowledge can be obtained while the latent knowledge is extracted,but not vice versa.Regarding the extraction of definable knowledge,many achievements have been made,but relatively less attention has been paid to the extraction of latent knowledge,especially how to extract latent knowledge through visualization methods,which is an urgent problem to be solved.Therefore,utilizing the visualization characte-ristics of hypergraphs in the context of information systems,this paper explores the correspondence between information systems and hypergraphs,and proposes methods for their mutual conversion.Using this method,combined with hypergraph theory and rough set theory,a pair of hypergraph-based upper and lower approximation operator is defined.Furthermore,the concept of approximate hypergraphs is proposed,and its properties are explored.The construction of approximate hypergraphs is completed,and an effective method for knowledge extraction under the hypergraph framework is implemented.By comparing with classical and recently proposed approximation theories and knowledge extraction methods,the advantages of the proposed method in terms of approximation and knowledge extraction are demonstrated.For the proposed method,its correctness is verified through practical examples,so that its applicability is indicated.The proposed method is a development and supplement to existing knowledge extraction theories.

Key words: Knowledge extraction, Information system, Hypergraph, Approximate hypergraph, Visualization methods

中图分类号: 

  • TP391
[1]PAWLAK Z.RoughSets:Theoretical Aspects of Reasoningabout Data[M].Dordrecht:Kluwer Academic Publishers,1991.
[2]PAWLAK Z.Rough Sets[J].International Journal of Computer &Information Sciences,1982,11:341-356.
[3]MAO H,WANG S Y,LIU C,et al.Hypergraph-Based Attribute Reduction of Formal Contexts in Rough Sets[J].Expert Systems with Applications,2023,234:121062.
[4]YAO Y Y,YANG J.Granular Fuzzy Sets and Three-way Approx-imations of Fuzzy Sets[J].International Journal of Appro-ximate Reasoning,2023,161:109003.
[5]JARADEH M Y,SINGH K,STOCKER M,et al.Information Extraction Pipelines for Knowledge Graphs[J].Knowledge and Information Systems,2023,65(5):1989-2016.
[6]BRETTO A.Hypergraph Theory:an Introduction[M].Cham:Springer,2013.
[7]VINAS R,JOSHI C K,GEORGIEV D,et al.Hypergraph Factorization for Multi-tissue Gene Expression Imputation[J].Nature Machine Intelligence,2023,5(7):739-753.
[8]PRAJNANASWAROOPA S,GEETHA J,SOMASUNDARAM K.Total Chromatic Number for Some Classes of Cayley Graphs[J].Soft Computing,2023:1-9.
[9]DALCENGIO S,LECOMTE V,POLETTINI M.Geometry of Nonequilibrium Reaction Networks[J].Physical Review X,2023,13(2):021040.
[10]BERGE C.Graphs and Hypergraphs[M].English translation,Amsterdam:North-Holland Publishing Company,1973.
[11]CHVATAL V.Hypergraphs and Ramseyian Theorems[J].Proceedings of the American Mathematical Society,1971,27(3):434-440.
[12]LOVASZ L.Normal Hypergraphs and The Perfect Graph Conjecture[J].Discrete Mathematics,1972,2(3):253-267.
[13]ERDOS P,LOVASZ L.Problems and Results on 3-ChromaticHypergraphs and Some Related Questions[J].Infinite and Finite Sets,1975,10(2):609-627.
[14]OWRANG O M M,MILLER L L.Query Translation in a He-terogeneous Distributed Database Based on Hypergraph Models[C]//Proceedings of the 1986 ACM Fourteenth Annual Confe-rence on Computer Science.New York:Association for Computing Machinery,1986:412.
[15]GOLDSTEIN A J.Database Systems:A Directed HypergraphDatabase:A Model for The Local Loop Telephone Plant[J].Bell System Technical Journal,1982,61(9):2529-2554.
[16]SACCA D.Closures of Database Hypergraphs[J].Journal of the ACM,1985,32(4):774-803.
[17]LANDE D,FU M,GUO W,et al.Link Prediction of Scientific Collaboration Networks Based on Information Retrieval[J].World Wide Web,2020,23:2239-2257.
[18]ZHANG F,YUAN N J,LIAN D,et al.Collaborative Knowledge Base Embedding for Recommender Systems[C]//Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York:Association for Computing Machinery,2016:353-362.
[19]JI S,FENG Y,JI R,et al.Dual Channel Hypergraph Collaborative Filtering[C]//Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery &Data Mining.New York:Association for Computing Machinery,2020:2020-2029.
[20]YANG B,MITCHELL T.Leveraging Knowledge Bases in LSTMs for Improving Machine Reading[C]//Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics(Volume 1:Long Papers).Vancouver:Association for Computational Linguistics,2017:1436-1446.
[21]RITAL S,CHERIFI H,MIGUET S.Weighted Adaptive Neighborhood Hypergraph Partitioning for Image Segmentation[C]//Pattern Recognition and Image Analysis:Third International Conference on Advances in Pattern Recognition(ICAPR 2005).Berlin Heidelberg:Springer,2005:522-531.
[22]TAN S L,GUAN Z Y,CAI D,et al.Mapping Users AcrossNetworks by Manifold Alignment on Hypergraph[C]//Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence.California:AAAI Press,2014:159-165.
[23]ZHOU H Y,ZHANG D Q.Multi-site Hypergraph Convolu-tional Neural Networks and Application[J].Computer Science,2022,49(3):129-133.
[24]CUI B J,ZHANG Y P,WANG B.Multimodal Data Fusion Algorithm Based on Hypergraph Regularization[J].Computer Science,2023,50(6):167-174.
[25]LIU C,REN G D.Phylogenetic Analysis of Genera of the Tribe Blaptini Based on The Characteristics of Defensive Glands(Coleoptera:Tenebrionidae)[J].Acta Entomologica Sinica,2012,55(10):1205-1220.
[26]GRATZER G.Lattice Theory:First Concepts and DistributiveLattices[M].New York:Dover Publications,2009.
[27]LIANG J Y,QU K S,XU Z B.Reduction of Attribute in Information Systems[J].Systems Engineering-Theory & Practice,2001,21(12):76-80.
[28]GONG X,HIGHAM D J,ZYGALAKIS K.Generative Hypergraph Models and Spectral Embedding[J].Scientific Reports,2023,13(1):540.
[29]YOU L,JIANG H,HU J,et al.GPU-accelerated Faster Mean Shift with Euclidean Distance Metrics[C]//2022 IEEE 46th Annual Computers,Software,and Applications Conference(COMPSAC).Los Alamitos:IEEE,2022:211-216.
[30]ZHAO L.A Theory of Spatial Granular Computing[D].Regina:University of Regina,2023.
[31]GAO Y,FENG Y,JI S,et al.HGNN+:General Hypergraph Neural Networks[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2022,45(3):3181-3199.
[32]HUANG J,HUANG X,YANG J.Residual Enhanced Multi-Hypergraph Neural Network[C]//2021 IEEE International Conference on Image Processing(ICIP).Anchorage:IEEE,2021:3657-3661.
[33]CHEN L H.Research on Modeling and Representation of He-terogeneous Hypergraphs for Academic Recommendations [D].Jilin:Jilin University,2023.
[34]VELDT N.Optimal LP Rounding and Linear-Time Approximation Algorithms for Clustering Edge-Colored Hypergraphs[C]//Proceedings of the 40th International Conference on Machine Learning.New York:PMLR,2023:34924-34951.
[35]ZHAO X,YU Y,ZHOU G,et al.Fast Hypergraph Regularized Nonnegative Tensor Ring Decomposition Based on Low-rank Approximation[J].Applied Intelligence,2022,52(15):17684-17707.
[36]YAO Y Y.Three-way Decision:an Interpretation of Rules inRough Set Theory[C]//Rough Sets and Knowledge Technology:4th International Conference,RSKT 2009,Gold Coast,Australia,July 14-16,2009.Proceedings 4.Berlin Heidelberg:Springer,2009:642-649.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
地址：重庆市渝北区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发