计算机科学 ›› 2018, Vol. 45 ›› Issue (7): 293-298.doi: 10.11896/j.issn.1002-137X.2018.07.050

• 交叉与前沿 • 上一篇    下一篇

基于高阶最小生成树脑网络的多特征融合分类方法

秦梦娜,陈俊杰,郭浩   

  1. 太原理工大学计算机科学与技术学院 山西 晋中030600
  • 收稿日期:2017-06-02 出版日期:2018-07-30 发布日期:2018-07-30
  • 作者简介:秦梦娜(1992-),女,硕士生,CCF会员,主要研究方向为人工智能、智能信息处理、脑信息学;郭 浩(1981-),男,博士,副教授,CCF会员,主要研究方向为人工智能、智能信息处理、脑信息学,E-mail:feiyu_guo@sina.com(通信作者);陈俊杰(1956-),男,博士,教授,主要研究方向为人工智能、智能信息处理、脑信息学。
  • 基金资助:
    本文受国家自然科学基金(61373101,61472270,61402318,61672374),山西省科技厅应用基础研究项目青年面上项目(201601D021073),山西高等教育机构科技创新项目(2016139)资助。

Multi-feature Fusion Classification Method Based on High-order Minimum Spanning Tree Brain Network

QIN Meng-na, CHEN Jun-jie, GUO Hao   

  1. College of Computer Science and Technology,Taiyuan University of Technology,Jinzhong,Shanxi 030600,China
  • Received:2017-06-02 Online:2018-07-30 Published:2018-07-30

摘要: 现有的基于脑疾病的分类方法的研究使用的都是传统的低阶功能连接网络。低阶功能连接网络可能会忽略复杂的大脑区域之间动态的相互作用的模式。高阶功能连接网络能够反映网络中包含的丰富的动态时间信息,但原有的高阶功能连接网络使用聚类的方法降低了数据维度,使得构建的网络无法进行有效的神经学解释;其次,高阶功能连接网络由于规模较大,在利用复杂网络或图理论计算一些拓扑指标时消耗较大。基于此,提出了一种高阶最小生成树网络的构建方法,然后计算了传统的可量化网络指标(度和离心率)并结合频繁子图挖掘技术来挖掘具有判别能力的子网络,最后采用多核支持向量机进行分类。实验结果表明所提方法的分类精确度高达97.54%,获得了很好的分类性能。

关键词: 低阶功能连接网络, 高阶功能连接网络, 频繁子图, 最小生成树

Abstract: Existing researches on classification of brain diseases is based on the traditional low-order functional connectivity network.Low-order functional connectivity network may overlook the complex and dynamic interaction patterns among brain regions,which are essentially time-varying.The high-order functional connectivity network can reflect the abundant dynamic time information contained in the network.However,the traditional high-order functional connectivity network adopts the clustering method to reduce the dimensionality of the data,making the construced network can not be effectively interpreted from the perspective of neurology.Even more importantly,due to the large scale of the high-order functional connectivity network,it is verytime-comsuming to use some complex network or graph theory to calculate some topological properties.Therefore,this paper proposed a method for constructing a high-order minimum spanning tree network,calculated the traditional quantifiable network properties (degree and eccentricity),and used frequent subgraph mining technology to capture the discriminative subnetworks as features.Then,this paper applied a multi-kernel learning technique into the corresponding selected features to obtain the final classification results.The experimental results show that the classification accuracy is up to 97.54%.

Key words: Frequent subgraph, High-order functional connectivity network, Minimum spanning tree, Slow-order functional connectivity network

中图分类号: 

  • TP181
[1]POWERJ D,COHEN A L,NELSON S M,et al.Functional network organization of the human brain[J].Neuron,2011,72(4):665-678.
[2]ALEXANDER-BLOCH A F,GOGTAY N,MEUNIER D,et al.Disrupted modularity and local connectivity of brain functional networks in childhood-onset schizophrenia[J].Frontiers in Systems Neuroscience,2010,4:147.
[3]YANG G F,ZHANG Q,ZHANG Y T,et al.An fMRI Study of Aberrant Brain Network in Schizophrenia Patients[J].Chinese Journal of Clinical Psychology,2009,17(5):581-583.(in Chinese)
杨桂芬,张权,张云亭,等.精神分裂症患者异常脑网络的fMRI研究[J].中国临床心理学杂志,2009,17(5):581-583.
[4]HE Y,CHEN Z,EVANS A.Structural insights into aberranttopological patterns of large-scale cortical networks in Alzheimer’s disease.
[J].Journal of Neuroscience,2008,4(4):4756-4766.
[5]VAND E,DOUW L,BAAYEN J C,et al.Long-term effects of temporal lobe epilepsy on local neural networks:a graph theoretical analysis of corticography recordings[J].Plos One,2009,4(11):e8081.
[6]INOKUCHI A,WASHIO T,MOTODA H.An Apriori-BasedAlgorithm for Mining Frequent Substructures from Graph Data[C]∥Principles of Data Mining and Knowledge Discovery,European Conference(Pkdd 2000).Lyon,France,DBLP,2000:13-23.
[7]DAMARAJUE,ALLEN E A,BELGER A,et al.Dynamic functional connectivity analysis reveals transient states of dysconnectivity in schizophrenia[J].Neuroimage Clinical,2014,5:298-308.
[8]ZHANG H,CHEN X,SHI F,et al.Topographical Information-Based High-Order Functional Connectivity and Its Application in Abnormality Detection for Mild Cognitive Impairment[J].Journal of Alzheimers Disease Jad,2016,54(3):1095-1112.
[9]CHEN X,ZHANG H,GAO Y,et al.High-order resting-statefunctional connectivity network for MCI classification[J].Human Brain Mapping,2016,37(9):3282-3296.
[10]JACKSONT S,READ N.Theory of minimum spanning trees.I.Mean-field theory and strongly disordered spin-glass model[J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2009,81(1):021130.
[11]BAO J,LU L,JI Z H.Tourism transportation optimization and tour route designing of north anhui province based on the kruskal algorithm of graph-theory[J].Human Geography,2010(3):144-148.(in Chinese)
鲍捷,陆林,吉中会.基于最小生成树Kruskal算法的皖北地区旅游交通优化与线路组织[J].人文地理,2010(3):144-148.
[12]WU Z,BRAUNSTEIN L A,HAVLIN S,et al.Transport in weighted networks:partition into superhighways and roads.
[J].Physical Review Letters,2006,96(14):148702.
[13]DEMURU M,FARA F,FRASCHINI M.Brain network analysis of EEG functional connectivity during imagery hand movements[J].Journal of Integrative Neuroscience,2013,12(4):441-447.
[14]VOURKAS M,KARAKONSTANTAKI E,SIMOS P G,et al.Simple and difficult mathematics in children:a minimum spanning tree EEG network analysis[J].Neuroscience Letters,2014,576:28-33.
[15]LEE U,KIM S,JUNG K Y.Classification of epilepsy typesthrough global network analysis of scalp electroencephalograms[J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2006,73(4 Pt 1):041920.
[16]TIJMSB M,WINK A M,DE H W,et al.Alzheimer’s disease:connecting findings from graph theoretical studies of brain networks[J].Neurobiology of Aging,2013,34(8):2023-2036.
[17]BORCHARDTV,LORD A R,LI M,et al.Preprocessing strategy influences graph-based exploration of altered functional networks in major depression[J].Human Brain Mapping,2016,37(4):1422-1442.
[18]FEI F,WANG L P,JIE B,et al.Discriminative subgraph mining with application in MCI classification[J].Journal of Nanjing University(Natural Sciences),2015,51(2):328-334.(in Chinese)
费飞,王立鹏,接标,等.判别性子图挖掘方法及其在MCI分类中的应用[J].南京大学学报(自然科学),2015,51(2):328-334.
[19]DU J,WANG L,JIE B,et al.Network-based classification ofADHD patients using discriminative subnetwork selection and graph kernel PCA[J].Computerized Medical Imaging & Gra-phics the Official Journal of the Computerized Medical Imaging Society,2016,52:82-88.
[20]WANG L,FEI F,JIE B,et al.Combining Multiple NetworkFeatures for Mild Cognitive Impairment Classification[C]∥IEEE International Conference on Data Mining Workshop.IEEE,2014:996-1003.
[21]FRISTON K J.Statistical Parametric Mapping:The Analysis of Functional Brain Images[J].Neurosurgery,2013,61(1):216-216.
[22]TZOURIOMAZOYER N,LANDEAU B,PAPATHANASSIOU D,et al.Automated anatomical labeling of activations in SPM using a macroscopic anatomical parcellation of the MNI MRI single-subject brain[J].Neuroimage,2002,15(1):273-289.
[23]TEWARIEP,VAN D E,HILLEBRAND A,et al.The minimum spanning tree:an unbiased method for brain network analysis[J].Neuroimage,2015,104:177-188.
[24]KRUSKAL J B.On the shortest spanning subtree of a graph and the traveling salesman problem[J].Proceedings of the American Mathematical Society,1956,7(1):48-50.
[25]LOPESR H C.Kolmogorov-Smirnov Test[J].International Encyclopedia of Statistical Science,2008,10(1):718-720.
[26]BENJAMINI,YOAV,HOCHBERG Y,et al.Controlling the False Discovery Rate:A Practical and Powerful Approach to Multiple Testing.Royal Statistical Society.Series B (Me-thodological),1995,57(1):289-300.
[27]POLAJNAR M,DEMSAR J.Small network completion using frequent subnetworks [J].Intelligent Data Analysis,2015,19(1):89-108.
[28]YAN X,HAN J.gSpan:Graph-Based Substructure Pattern Mi-ning[C]∥IEEE International Conference on Data Mining.IEEE Computer Society,2002:721.
[29]LANCKRIETG R G,CRISTIANINI N,BARTLETT P,et al.Learning the Kernel Matrix with Semi-Definite Programming.
[C]∥Nineteenth International Conference on Machine Lear-ning.Morgan Kaufmann Publishers Inc.2002:323-330.
[30]SHERVASHIDZE N,SCHWEITZER P,VAN LEEUWEN E J,et al.Weisfeiler-Lehman Graph Kernels[J].Journal of Machine Lear-ning Research,2011,12(3):2539-2561.
[31]GUO H,LIU W Z,LIU Z F,et al.Difference index analysis on resting state functional brain network and its application in major depressive disorder classification[J].Computer Applications &Software,2014(12):85-88.(in Chinese)
郭浩,刘文钊,刘志芬,等.静息态功能脑网络差异指标分析及抑郁症分类应用[J].计算机应用与软件,2014(12):85-88.
[32]SACCHETM D,CAMACHO M C,LIVERMORE E E,et al.Accelerated aging of the putamen in patients with major depressive disorder[J].J Psychiatry Neurosci,2017,42(3):164.
[33]QIAO L,ZHANG H,KIM M,et al.Estimating functional brain networks by incorporating a modularity prior[J].Neuroimage,2016,141:399-407.
[34]M-L W,DONG C,ANDREEV V,et al.Prediction of susceptibi-lity to major depression by a model of interactions of multiple functional genetic variants and environmental factors[J].Mol Psychiatry,2012,17(6):624-633.
[1] 朱鹏宇,鲍培明,吉根林.
用户频繁通信关系的并行挖掘算法研究
Parallel Algorithm for Mining User Frequent Communication Relationship
计算机科学, 2018, 45(2): 103-108. https://doi.org/10.11896/j.issn.1002-137X.2018.02.018
[2] 洪睿, 康晓东, 李博, 王亚鸽.
一种基于复杂网络的图像形状及纹理描述方法
Image Shape and Texture Description Method Based on Complex Network
计算机科学, 2018, 45(11A): 244-246.
[3] 朱庆生,段浪军,杨力军.
基于自然邻居和最小生成树的原型选择算法
Prototype Selection Algorithm Based on Natural Neighbor and MST
计算机科学, 2017, 44(4): 241-245. https://doi.org/10.11896/j.issn.1002-137X.2017.04.051
[4] 袁关伟,赵家刚.
基于“断弦护枝”思想的MST构造算法的设计与分析
Design and Analysis of MST Constructing Algorithm Based on the Idea that is Named as Pruning Bowstrings and Protecting Branches
计算机科学, 2012, 39(Z6): 437-440.
[5] 王桂娟,印鉴,詹卫许.
GC-BES:一种新的基于嵌入集的图分类方法
GC-BES:A Novel Graph Classification Approach Based on Embedding Sets
计算机科学, 2012, 39(6): 155-158.
[6] 王桂娟,印鉴,詹卫许.
基于类别信息的特征子图选择策略
Feature Subgraph Selection Strategy Based on Category Information
计算机科学, 2011, 38(8): 169-170.
[7] 胡桂武 郑启伦 彭宏 邓伟林.
基于最小生成树的多序列联配算法

计算机科学, 2005, 32(4): 59-61.
[8] 刘勇国 张伟 陈克非 廖晓峰.
基于禁忌搜索的聚类簇数目估算算法

计算机科学, 2005, 32(1): 168-171.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!