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

山东大学学报 (工学版) ›› 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

14

PDF (PC)

1908

摘要：

针对最大信息系数(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]. 山东大学学报 (工学版), 2025, 55(5): 51-61.
[2] 薛冰冰,王勇,杨维浩,王川,于迪,王旭. 基于ETC收费数据的高速公路交通流数据修复及实时预测[J]. 山东大学学报 (工学版), 2025, 55(3): 58-71.
[3] 邹正标,刘毅志,廖祝华,赵肄江. 动态交通流量预测的时空注意力图卷积网络[J]. 山东大学学报 (工学版), 2024, 54(5): 50-61.
[4] 陈成,董永权,贾瑞,刘源. 基于交互序列特征相关性的可解释知识追踪[J]. 山东大学学报 (工学版), 2024, 54(1): 100-108.
[5] 王骏林,冯春,张一鸣. 考虑温度相关性的岩石热破裂数值模拟[J]. 山东大学学报 (工学版), 2023, 53(1): 106-113.
[6] 区伟潮,葛阳,朱延廷,高厚磊,龚辉昶. 基于双端原理的中压电缆潜伏性故障定位方法[J]. 山东大学学报 (工学版), 2022, 52(5): 84-91.
[7] 孙东磊,孙可奇,杨金叶,曹永吉,袁振华,刘冬,张恒旭. 考虑灵活性需求的电力系统优化调度[J]. 山东大学学报 (工学版), 2022, 52(1): 120-127.
[8] 李文升, 王宪, 米元泽, 曹永吉, 刘晓明, 张恒旭, 刘子菡. 考虑风光多维时空相关性的电源规划方法[J]. 山东大学学报 (工学版), 2022, 52(1): 111-119.
[9] 张胜男,王雷,常春红,郝本利. 基于三维剪切波变换和BM4D的图像去噪方法[J]. 山东大学学报 (工学版), 2020, 50(2): 83-90.
[10] 王梦园,张雄,马亮,彭开香. 基于因果拓扑图的工业过程故障诊断[J]. 山东大学学报(工学版), 2017, 47(5): 187-194.
[11] 侯广松,高军,吴衍达,张欣,邓影,李常刚,张亚萍. 输电线路参数与运行方式的相关性分析[J]. 山东大学学报(工学版), 2017, 47(4): 89-95.
[12] 翟东海1,2,鱼江1,聂洪玉1,崔静静1,杜佳1. 基于相关性反馈的自适应热点话题追踪模型[J]. 山东大学学报(工学版), 2014, 44(1): 7-12.
[13] 蒋志方1,王德明2,杜晓亮1,孟祥旭1,李慎芳1. 基于结构优化的RAN城市环境空气质量预测模型[J]. 山东大学学报(工学版), 2010, 40(6): 1-7.
[14] 孟祥星1,于大洋2,韩学山2,赵建国3. 太阳辐射与负荷波动的相关性对光伏发电并网的影响[J]. 山东大学学报(工学版), 2010, 40(2): 126-129.
[15] 刘云,邱晓国 . 内插TOC系数法测定水体中COD研究[J]. 山东大学学报(工学版), 2007, 37(4): 108-117 .
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] 李 侃 . 嵌入式相贯线焊接控制系统开发与实现[J]. 山东大学学报(工学版), 2008, 38(4): 37 -41 .
[2] 来翔 . 用胞映射方法讨论一类MKdV方程[J]. 山东大学学报(工学版), 2006, 36(1): 87 -92 .
[3] 余嘉元1 , 田金亭1 , 朱强忠2 . 计算智能在心理学中的应用[J]. 山东大学学报(工学版), 2009, 39(1): 1 -5 .
[4] 陈瑞,李红伟,田靖. 磁极数对径向磁轴承承载力的影响[J]. 山东大学学报(工学版), 2018, 48(2): 81 -85 .
[5] 王波,王宁生 . 机电装配体拆卸序列的自动生成及组合优化[J]. 山东大学学报(工学版), 2006, 36(2): 52 -57 .
[6] 张英,郎咏梅,赵玉晓,张鉴达,乔鹏,李善评 . 由EGSB厌氧颗粒污泥培养好氧颗粒污泥的工艺探讨[J]. 山东大学学报(工学版), 2006, 36(4): 56 -59 .
[7] Yue Khing Toh1 ， XIAO Wendong2 ， XIE Lihua1 . 基于无线传感器网络的分散目标跟踪：实际测试平台的开发应用（英文）[J]. 山东大学学报(工学版), 2009, 39(1): 50 -56 .
[8] 孙炜伟,王玉振. 考虑饱和的发电机单机无穷大系统有限增益镇定[J]. 山东大学学报(工学版), 2009, 39(1): 69 -76 .
[9] 孙玉利,李法德,左敦稳,戚美 . 直立分室式流体连续通电加热系统的升温特性[J]. 山东大学学报(工学版), 2006, 36(6): 19 -23 .
[10] 王勇, 谢玉东.

大流量管道煤气的控制技术研究

[J]. 山东大学学报(工学版), 2009, 39(2): 70 -74 .
版权所有 © 2018 《山东大学学报(工学版)》编辑部　
地址: 济南市山大南路27号（250100）　 电话: 0531-88366735　 E-mail: xbgxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发