数据分割分子动力学算法.pdf

2014年 8月 计 算 数 学 第 36卷第 3期 Aug．，2014 MATHEMATICA NUMERICA SINICA v01．36．No．3 数据分割的分子动力学算法 ) 石子烨。)梁 恒 白峰杉 (清华大学数学科学系，北京100084) 摘 要 数据分割研究的基本内容是数据的分类和聚类，是数据挖掘的核心问题之一，在实际问题中 应用广泛．特别是针对有向网络数据的研究更是学科发展的前沿．但 由于这类 问题结构的非对称 性，使得模型与算法的构建存在本质困难，因此相应的研究结果较少．本文借鉴分子动力学方法的 思想，提出了一类新的网络数据半监督分类模型及算法．该算法不仅适用于关系对称的无向网络 数据，而且适用于关系非对称的有向网络．最后针对期刊引用网络数据进行了数值实验，结果表明 了模型及算法的可行性和有效性． 关键词：数据分割；半监督模型与算法；分类；聚类；有向网络数据 MR (~ooo)主题分类：62H30，65C35 1．引 言 分类是数据挖掘中一个重要的研究领域，应用遍及 自然科学、经济金融、教育及工程等众 多学科领域．分类算法是在已知类别的 (亦称有标签的)数据集上建立和训练数据分割模型， 把未知类别的数据赋予一个给定类别标签的过程，它是一种有监督的 (supervised)[]数据处 理过程．比较经典的分类方法主要包括决策树、贝叶斯算法、人工神经网络、支持向量机、关 联分类、集成算法 (Bagging和Boosting)等．聚类则是针对未知类别的 (亦称无标签的)数据 进行的数据分割，是一种无监督的 (unsupervised)数据处理过程．经典的聚类方法包括K一均 值算法、谱聚类方法等． 在现实的大规模数据集中，获得大量有标签的数据是相当困难的，它需要对数据的背景有 深入的了解和分析，因此通常这些数据标签是通过相关领域的专家来标注，不仅成本昂贵，而 且由于每位专家个人经验程度的不同及理解的角度不同，对数据的标记往往存在一定程度 的 差异．故在大数据 的实际应用中，通常情况是少量有标签的数据和大量无标签的数据并存．由 于含标签的数据点较少，单纯只利用有标签的数据往往不能得到泛化能力强的模型．因此，如 何利用大量无标签数据来提升在少量有标签数据上模型的泛化能力，已成为当前数据挖据领 域的热点，半监督算法也因此应运而生L213，71． 目前半监督模型与算法被很多领域的研究者所关注并得到有效应用，已成为数据挖掘领 域 [3-5J的一个重要分支，是介于有监督分类和无监督聚类之间的数据分割模型，目标是用有 标签的数据和无标签的数据共同建立分类模型，使得相同类别的数据对象具有较高的相似度， 而不同类别的数据对象相似度较低，其效果优于仅在有标签数据上建立的模型． 分子动力学模拟 (moleculardynamicssimulation)6【J是一种微观层面的建模方法，其基 本出发点是通过考察粒子间的相互作用构建模型，在微观上模拟粒子运动的计算机模拟方法． 2014年 1月 29日收到． )基金项 目：国家 自然科学基金 资助项 目 。)现工作单位：中国电子科学研究院，北京 100041． 326 计 算 数 学 2014短 模拟的目的在于通过计算并记录粒子的运动轨迹，可按照一定的统计物理方法，得到系统热 力学及力学上的宏观性质．本文借鉴了分子动力学的思想，提出了数据分割问题的一种动态算 法，它运用分子动力学模拟算法构建数据分割模型．具有实际应用背景的数值实验，表明了这 种模型及算法的可行性和有效性． 2．模型构建 在经典分子动力学模拟中，L—J势能函数 (Lennard—Jonespotentialfunction)是计算化学 中两分子间作用势能的一个函数，因其形式简单而被广