您的位置：山东大学 -> 科技期刊社 -> 《山东大学学报（工学版）》

山东大学学报 (工学版) ›› 2019, Vol. 49 ›› Issue (5): 105-111.doi: 10.6040/j.issn.1672-3961.0.2018.209

• 机器学习与数据挖掘 • 上一篇    下一篇

一种基于动态均分的最大信息系数改进算法

孟燕霞1(),郭禹辰1,王莉2,*()   

  1. 1. 太原理工大学信息与计算机学院, 山西 晋中 030600
    2. 太原理工大学大数据学院, 山西 晋中 030600
  • 收稿日期:2018-05-25 出版日期:2019-10-20 发布日期:2019-10-18
  • 通讯作者: 王莉 E-mail:2111428372@qq.com;462672475@qq.com
  • 作者简介:孟燕霞(1993—)，女，山西忻州人，硕士研究生，主要研究方向为数据挖掘. E-mail:2111428372@qq.com
  • 基金资助:
    国家自然基金项目(61872260);山西省重点研发计划项目(201703D421013)

An improved algorithm of maximal information coefficient based on dynamic equipartition

Yanxia MENG1(),Yuchen GUO1,Li WANG2,*()   

  1. 1. College of Information and Computer, Taiyuan University of Technology, Jinzhong 030600, Shanxi, China
    2. College of Data Science, Taiyuan University of Technology, Jinzhong 030600, Shanxi, China
  • Received:2018-05-25 Online:2019-10-20 Published:2019-10-18
  • Contact: Li WANG E-mail:2111428372@qq.com;462672475@qq.com
  • Supported by:
    国家自然基金项目(61872260);山西省重点研发计划项目(201703D421013)

RichHTML

10

PDF (PC)

721

摘要：

针对最大信息系数(maximal information coefficient, MIC)算法计算时间复杂度较高的问题,提出一种基于动态均分的最大信息系数(dynamic equpartition of maximal information coefficient, DE-MIC)改进算法,利用动态均分对两变量在网格中的散点图进行不断迭代寻优,通过对获得的互信息进行正则化得到最优的DE-MIC值,同时利用标准的可移植操作系统接口(portable operating system interface of UNIX, POSIX)对数据集进行多线程计算,使算法在大规模数据集上的计算效率更高。经过在多个数据集上与快速最大信息系数算法(rapid computation of the maximal information coefficient, RapidMIC)比较, DE-MIC算法在保持原有最大信息系数算法普适性和均匀性的前提下,计算速度更快且效率更佳。

关键词: 动态均分, 相关性, 最大信息系数, 统计分析

Abstract:

In order to solve the problem of high computational time complexity of the maximal information coefficient algorithm, an improved algorithm of the maximal information coefficient(MIC) based on dynamic equipartition was presented. The scattered points shown in the grid were iterated and optimized by using dynamic mean division pairs of variables. The obtained mutual information entropy was regularized to obtain the optimal MIC value, and the multi-thread computation of the data set was carried out by using the POSIX parallel strategy, which made the computation more efficient in the computation of large data sets. Compared with the RapidMIC method on multiple data sets, the DE-MIC algorithm was faster and more efficient under the premise of preserving the generality and equitability of the maximal information coefficient algorithm.

Key words: dynamic equipartition, correlation, maximal information coefficient, statistical analysis

中图分类号: 

  • TP3-0

图1

MIC算法过程"

图2

DE-MIC算法流程图"

表1

两变量函数关系定义"

关系类型 具体形式
线性函数 y=x
抛物线函数 y=x2+x+1
立方函数 y=128(x-1/3)3-48(x-1/3)2-12(x-1/3)+2
指数函数 y=2x
周期+线性函数 y=sin(10πx)+x
随机数 (x, y)

图3

MIC算法计算两变量的MIC值"

图4

DE-MIC算法计算两变量DE-MIC值"

图5

MIC算法计算具有噪声两变量MIC值"

图6

DE-MIC算法计算具有噪声两变量DE-MIC值"

表2

试验数据统计表"

数据集 变量数N 特征数M
Spellman 4 381 23
RNA 20 422 16
MLB2008 132 337

图7

抛物线函数的计算时间"

图8

立方函数的计算时间比较"

表3

DE-MIC算法计算单变量对所需时间"

s
数据集 RapidMIC DE-MIC
Spellman 0.219 0.019
RNA 0.831 0.058
MLB2008 0.019 0.009

表4

DE-MIC算法计算一对多变量所需时间"

s
数据集 RapidMIC DE-MIC
Spellman 0.548 0.066
RNA 0.565 0.151
MLB2008 4.805 2.227

表5

DE-MIC算法计算两组变量所需时间"

s
数据集 RapidMIC DE-MIC
Spellman 4.852 2.571
RNA 5.056 3.354
MLB2008 43.918 30.398

表6

四种算法的性能综合对比"

算法 真实数据集 算法主要思想 优势 不足
KM-MIC[9] 美国联邦铁路事故数据集 利用k-means将数据集中两变量分别划分为不同数量的数据块 利用k-means聚类算法
使得算法计算时间复杂度降低		 未考虑计算准确度
只针对于对相关系数要求不高的数据集
CHIMIC[16] Prostate1与2两个基因表达谱数据, WDBC与WPBC两个肿瘤组织图像数据集 利用动态规划算法对其中一个变量划分,并以卡方测验检测各分段点的显著性
利用均分对另一边两变量进行划分		 利用卡方检验对网格数进行控制
算法的准确度较高		 计算效率较低
应用于医学方面,求取其主要的疾病特征
RapidMIC[18] 见表2 对其中一个变量进行动态规划
对另一变量进行均分
同时利用了POSIX并行策略		 利用POSIX并行策略,使算法可以在所有线程执行 计算时间复杂度较高,算法效率低
DE-MIC 见表2 利用动态均分分别对两变量划分不同的网格
同时利用了POSIX并行策略		 利用动态均分原理快速寻找到两变量最优划分
算法时间复杂度降低,效率提升		 准确度有待提高
针对大规模数据集
1 樊嵘, 孟大志, 徐大舜. 统计相关性分析方法研究进展[J]. 数学建模及其应用, 2014, 3 (1): 1- 12.
doi: 10.3969/j.issn.2095-3070.2014.01.002
FAN Rong , MENG Dazhi , XU Dashun . Survey of research process on statistical correlation analysis[J]. Mathematical Modeling and Its Applications, 2014, 3 (1): 1- 12.
doi: 10.3969/j.issn.2095-3070.2014.01.002
2 PEARSON K . Mathematical contributions to the theory of evolution:Ⅲ: regression, heredity and panmixia[J]. Philosophical Transactions of the Royal Society of London:Series A: Containing Papers of a Mathematical or Physical Character, 1895, 187, 253- 318.
3 MYERS J L , WELL A D . Research design and statistical analysis[M]. 2nd ed New York, USA: Lawrence Erlbaum Associates, 2003: 15- 89.
4 KRUSKAL W H . Ordinal measures of association[J]. Journal of the American Statistical Association, 1958, 53 (284): 814- 861.
doi: 10.1080/01621459.1958.10501481
5 CIGANOVIC N , BEAUTY N J , RENNER R . Smooth max-information as one-shot generalization for mutual information[J]. IEEE Transactions on Information Theory, 2014, 60 (3): 1573- 1581.
doi: 10.1109/TIT.2013.2295314
6 DELICADO P , SMREKAR M . Measuring non-linear dependence for two random variables distributed along a curve[J]. Statistics and Computing, 2009, 19 (3): 255- 269.
doi: 10.1007/s11222-008-9090-y
7 RESHEF D N , RESHEF Y A , FINUCANE H K , et al. Detecting novel associations in large data sets[J]. Science, 2011, 334 (6062): 1518- 1524.
doi: 10.1126/science.1205438
8 SPEED T . A correlation for the 21st century[J]. Science, 2011, 334 (6062): 1502- 1503.
doi: 10.1126/science.1215894
9 SHAO Fubo , LI Keping , et al. Railway accidents analysis based on the improved algorithm of the maximal information coefficient[J]. Intelligent Data Analysis, 2016, 20 (3): 597- 613.
doi: 10.3233/IDA-160822
10 PANG C N I , GOEL A , LI S S , et al. A multidimensional matrix for systems biology research and its application to interaction networks[J]. Journal of Proteome Research, 2012, 11 (11): 5204- 5220.
doi: 10.1021/pr300405y
11 KOREN O , GOODRICH J K , CULLENDER T C , et al. Host remodeling of the gut microbiome and metabolic cha-nges during pregnancy[J]. Cell, 2012, 150 (3): 470- 480.
doi: 10.1016/j.cell.2012.07.008
12 SAGL G , BLASCHKE T , BEINAT E , et al. Ubiquitous geo-sensing for context-aware analysis: exploring relationships between environmental and human dynamics[J]. Sensors, 2012, 12 (7): 9800- 9822.
doi: 10.3390/s120709800
13 EILER A , ZAREMBA-NIEDZWIEDZKA K , MARTINEZ-CARCIA M , et al. Productivity and salinity structuring of the microplankton revealed by comparative freshwater metagenomics[J]. Environmental Microbiology, 2014, 16 (9): 2682- 2698.
doi: 10.1111/1462-2920.12301
14 ZHANG Yi , JIA Shili , HUANG Haiyun , et al. A novel algorithm for the precise calculation of the maximal information coefficient[J]. Scientific Reports, 2014, (4): 6662.
15 WANG Shuliang , ZHAO Yiping . Analysing large biological datasets with an improved algorithm for MIC[J]. International Journal of Data Mining and Bioinformatics, 2015, 13 (2): 158.
doi: 10.1504/IJDMB.2015.071548
16 CHEN Yuan , ZENG Ying , LUO Feng , et al. A new algorithm to optimize maximal information coefficient[J]. PLos One, 2016, 11 (6): e0157567.
doi: 10.1371/journal.pone.0157567
17 ALBANESE D , FILOSI M , VISINTAINER R , et al. Minerva and minepy:a C engine for the MINE suite and its R, Python and MATLAB wrappers[J]. Bioinformatics, 2013, 29 (3): 407- 408.
doi: 10.1093/bioinformatics/bts707
18 TANG D , WANG M , ZHENG W , et al. RapidMic: rapid computation of the maximal information coefficient[J]. Evolutionary Bioinformatics, 2014, 10- 11.
19 SPELLMAN P T , SHERLOCK G , ZHANG M Q , et al. Comprehensive identification of cell cycle-regulated genes of the yeast saccharomyces cerevisiae by microarray hybridization[J]. Molecular Biology of the Cell, 1998, 9 (12): 3273- 3297.
doi: 10.1091/mbc.9.12.3273
20 KALARI K R , ROSSELL D , NECELA B M , et al. Deep sequence analysis of non-small cell lung cancer: integrated analysis of gene expression, alternative splicing, and single nucleotide variations in lung adenocarcinomas with and without oncogenic KRAS mutations[J]. Frontiers in Oncology, 2012, 2- 12.
[1] 王梦园,张雄,马亮,彭开香. 基于因果拓扑图的工业过程故障诊断[J]. 山东大学学报(工学版), 2017, 47(5): 187-194.
[2] 侯广松,高军,吴衍达,张欣,邓影,李常刚,张亚萍. 输电线路参数与运行方式的相关性分析[J]. 山东大学学报(工学版), 2017, 47(4): 89-95.
[3] 翟东海1,2,鱼江1,聂洪玉1,崔静静1,杜佳1. 基于相关性反馈的自适应热点话题追踪模型[J]. 山东大学学报(工学版), 2014, 44(1): 7-12.
[4] 蒋志方1,王德明2,杜晓亮1,孟祥旭1,李慎芳1. 基于结构优化的RAN城市环境空气质量预测模型[J]. 山东大学学报(工学版), 2010, 40(6): 1-7.
[5] 孟祥星1,于大洋2,韩学山2,赵建国3. 太阳辐射与负荷波动的相关性对光伏发电并网的影响[J]. 山东大学学报(工学版), 2010, 40(2): 126-129.
[6] 刘云,邱晓国 . 内插TOC系数法测定水体中COD研究[J]. 山东大学学报(工学版), 2007, 37(4): 108-117 .
[7] 牛新生,叶华,王亮 . 内插TOC系数法测定水体中CODcr研究[J]. 山东大学学报(工学版), 2007, 37(4): 0-0 .
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] 张迎春 王佐勋 王桂娟. 基于神经网络控制器的高压电缆测温系统[J]. 山东大学学报(工学版), 2009, 39(5): 62 -67 .
[2] 张道强. 知识保持的嵌入方法[J]. 山东大学学报(工学版), 2010, 40(2): 1 -10 .
[3] 董成喜,吴德伟,何 晶 . 基于粗糙模糊集理论的卫星导航系统作战效能评估方法[J]. 山东大学学报(工学版), 2008, 38(4): 32 -36 .
[4] 张盾,侯精明,刘韩生,徐根海 . 渥奇面上掺气挑坎位置的试验与数值计算分析[J]. 山东大学学报(工学版), 2008, 38(2): 101 -105 .
[5] 黄劲潮. 基于快速区域建议网络的图像多目标分割算法[J]. 山东大学学报(工学版), 2018, 48(4): 20 -26 .
[6] 刘涛 贾磊 朱文兴. 考虑相关车流的交通流格子模型[J]. 山东大学学报(工学版), 2009, 39(6): 63 -67 .
[7] 朱俊,赵建锋,陈之健. 循环往复Pushover分析轴压比对圆柱桥墩延性能力的影响[J]. 山东大学学报(工学版), 2016, 46(5): 110 -115 .
[8] 马宗正,邵凤翔,王新莉,杨安杰. 发动机尾气温差发电装置[J]. 山东大学学报(工学版), 2016, 46(2): 122 -127 .
[9] 杨敏,邹增大,宋文鹏,孙小磊 . Si3N4/（Cu，Nb）/Ni/Inconel600高温合金部分液相扩散连接接头的组织与力学性能[J]. 山东大学学报(工学版), 2007, 37(6): 36 -40 .
[10] 尚芳 刘允刚 张承慧. 一类不确定非线性系统输出反馈扰动抑制[J]. 山东大学学报(工学版), 2010, 40(1): 19 -27 .
版权所有 © 2018 《山东大学学报(工学版)》编辑部　
地址: 济南市山大南路27号（250100）　 电话: 0531-88366735　 E-mail: xbgxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发