基于关联规则映射的生物信息网络多维数据挖掘算法

第３２卷第６期　２０１５年６月　计算机应用研究　Ａｐｐｌｉｃａｔｉｏｎ　Ｒｅｓｅａｒｃｈ　ｏｆ　Ｃｏｍｐｕｔｅｒｓ　Ｖｏ１．３２　Ｎｏ．６　Ｊｕｎ．２０１５　基于关联规则映射的生物信息网络　多维数据挖掘算法米　唐晓东　（华南师范大学经济与管理学院，广州５１０６３０）　摘要ｌ＿针对在生物信息网络中对复杂和大规模的数据集进行挖掘时所出现的算法挖掘精度低、运行速度慢、　内存占用大等问题，提出一种基于关联规则映射的生物信息网络多维数据挖掘算法。该算法结合网络数据集之　间的关联映射关系，从而确定网络数据集的关联规则，并引入挖掘因子和相对误差来提高算法的挖掘精度；根据　多维子空间中数据集之间的关联程度进行子空间区分以及子空间内数据集区分，从而实现对不同数据集的有效　挖掘。在实验中，对不同数据集数量下的算法内存占用情况、算法挖掘精度、算法运行时间进行仿真，从实验结　果可以看出基于关联规则映射的挖掘算法可以有效地提高挖掘精度，在减少内存占用和提升计算速度上也具有　一定的优势。　关键词：数据挖掘；关联规则映射；生物信息网络；多维数据挖掘　中图分类号：ＴＰ３９１　文献标志码：Ａ　文章编号：１００１—３６９５（２０１５）０６—１６１４—０３　ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００１－３６９５．２０１５．０６．００３　Ｂｉｏｌｏｇｉｃａｌ　ｉｎｆｏｒｍａｔｉｏｎ　ｎｅｔｗｏｒｋ　ｍｕｌｔｉｄｉｍｅｎｓｉｏｎａｌ　ｄａｔａ　ｍｉｎｉｎｇ　ａｌｇｏｒｉｔｈｍ　ｂａｓｅｄ　ｏｎ　ａｓｓｏｃｉａｔｉｏｎ　ｒｕｌｅｓ　ｍａｐｐｉｎｇ　Ｔａｎｇ　Ｘｉａｏｄｏｎｇ　（Ｄｅｐｔ．ｏｆＥｃｏｍｍｅｒｃｅ　ｓＤ　＾Ｃｈｉｎａ　Ｎｏｒｍａｌ　Ｕｎｉｖｅｒｓｉｔｙ，Ｇｕａｎｇｚｈｏｕ　５１０６３０，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｆｏｒ　ｔｈｅ　ｐｒｏｂｌｅｍｓ　ｓｕｃｈ　ａｓ　ｍｉｎｉｎｇ　ｌｏｗ　ａｃｃｕｒａｃｙ　ｏｆ　ａｌｇｏｒｉｔｈｍ，ｌｏｗ　ｓｐｅｅｄ　ａｎｄ　ｌａｒｇｅ　ｍｅｍｏ￣ｆｏｏｔｐｒｉｎｔ　ｗｈｅｎ　ｄｉｇｇｉｎｇ　ｔｈｅ　ｃｏｍｐｌｅｘ　ａｎｄ　ｌａｒｇｅ－ｓｃａｌｅ　ｄａｔａ　ｓｅｔｓ　ｉｎ　ｔｈｅ　ｂｉｏｌｏｇｉｃａｌ　ｉｎｆｏｒｍａｔｉｏｎ　ｎｅｔｗｏｒｋ，ｔｈｉｓ　ｐａｐｅｒ　ｐｒｏｐｏｓｅｄ　ａ　ｂｉｏｌｏｇｉｃａｌ　ｉｎｆｏｒｍａｔｉｏｎ　ｎｅｔｗｏｒｋ　ｍｕｌｔｉ－ｄｉｍｅｎｓｉｏｎａｌ　ｄａｔａ　ｍｉｎｉｎｇ　ａｌｇｏｒｉｔｈｍ　ｔｈａｔ　ｂａｓｅｄ　ｏｎ　ａｓｓｏｃｉａｔｉｏｎ　ｒｕｌｅｓ　ｍａｐｐｉｎｇ．Ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ｃｏｍｂｉｎｅｄ　ａｓｓｏｃｉａｔｉｏｎ　ｍａｐｐｉｎｇ　ｒｅｌａｔｉｏｎｓｈｉｐ　ｂｅｔｗｅｅｎ　ｔｈｅ　ｎｅｔｗｏｒｋ　ｄａｔａｓｅｔ　ｔｏ　ｄｅｔｅｒｍｉｎｅ　ｔｈｅ　ａｓｓｏｃｉａｔｉｏｎ　ｒｕｌｅｓ　ｏｆ　ｎｅｔｗｏｒｋ　ｄａｔａｓｅｔ，ａｎｄ　ｉｎｔｒｏｄｕｃｅｄ　ｔｈｅ　ｍｉｎｉｎｇ　ｆａｃｔｏｒ　ａｎｄ　ｒｅｌａｔｉｖｅ　ｅｒｒｏｒ　ｔｏ　ｉｍｐｒｏｖｅ　ｍｉｎｉｎｇ　ａｃｃｕｒａｃｙ　ｏｆ　ｔｈｅ　ａｌｇｏｒｉｔｈｍ．Ａｃｃｏｒｄｉｎｇ　ｔｏ　ｔｈｅ　ｍｕｌｔｉ—ｄｉｍｅｎｓｉｏｎａｌ　ｓｕｂｓｐａｃｅ　ｄｅｇｒｅｅ　ｏｆ　ａｓｓｏｃｉａ—　ｔｉｏｎ　ｂｅｔｗｅｅｎ　ｔｈｅ　ｄａｔａ　ｓｅｔｓ　ｔｏ　ｄｉｓｔｉｎｇｕｉｓｈ　ｔｈｅ　ｓｕｂｓｐａｃｅ　ａｎｄ　ｓｕｂｓｐａｃｅ　ｄａｔａｓｅｔｓ　ｉｎ　ｏｒｄｅｒ　ｔｏ　ａｃｈｉｅｖｅ　ｅｆｆｅｃｔｉｖｅ　ｅｘｃａｖａｔｉｏｎ　ｏｆ　ｄｉｆｆｅｒｅｎｔ　ｄａｔａ　ｓｅｔｓ．Ｔｈｅ　ｅｘｐｅｒｉｍｅｎｔ　ａｌ　ｒｅｓｕｈｓ　ｏｎ　ｔｈｅ　ｍｅｍｏ￣ｕｓａｇｅ　ｏｆ　ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ｏｎ　ｔｈｅ　ｎｕｍｂｅｒ　ｏｆ　ｄｉｆｆｅｒｅｎｔ　ｓｅｔｓ　ｏｆ　ｄａｔａ，ｔｈｅ　ａｃｃｕｒａｃｙ　ｏｆ　ｍｉｎｉｎｇ　ａｌｇｏｒｉｔｈｍ，ｔｈｅ　ｓｉｍｕｌａｔｉｏｎ　ｏｆ　ａｌｇｏｒｉｔｈｍ　ｒｕｎｎｉｎｇ　ｔｉｍｅ，ｓｈｏｗ　ｔｈｅ　ａｓｓｏｃｉａｔｉｏｎ　ｒｕｌｅ　ｍｉｎｉｎｇ　ａｌｇｏｒｉｔｈｍ　ｃａｎ　ｅｆｆｅｃｔｉｖｅｌｙ　ｉｍｐｒｏｖｅ　ｔｈｅ　ｍｉｎｉｎｇ　ｍａｐ　ａｃｃｕｒａｃｙ，ｒｅｄｕｃｅ　ｔｈｅ　ｍｅｍｏ￣ｆｏｏｔｐｒｉｎｔ　ａｎｄ　ｅｎｈａｎｃｅ　ｔｈｅ　ｃｏｍｐｕｔｉｎｇ　ｓｐｅｅｄ．　Ｋｅｙ　ｗｏｒｄｓ：ｄａｔａ　ｍｉｎｉｎｇ；ａｓｓｏｃｉａｔｉｏｎ　ｒｕｌｅ　ｍａｐｐｉｎｇ；ｂｉｏｌｏｇｉｃａｌ　ｉｎｆｏｒｍａｔｉｏｎ　ｎｅｔｗｏｒｋ；ｍｕｈｉｄｉｍｅｎｓｉｏｎａｌ　ｄａｔａ　ｍｉｎｉｎｇ　刘殷雷等人　提出一种不确定性数据流上频繁项集挖掘　０　引言　数据挖掘是指在大量的数据当中通过搜索算法来寻找隐　藏的数据信息，它是基于机器学习、人工智能、模式识别等技　术，数据挖掘能在大量数据中寻找规律，寻找出数据集所含规　的有效算法，该算法通过一个有效的数据结构来对不确定性数　据事务流的项集进行存储，并且在数据结构的基础上设计了一　种挖掘算法ＳＲＵＦ—ｍｉｎｅ，通过深度遍历全局树来挖掘数据流。　王伟平等人　提出一种有效的挖掘数据流近似频繁项算法，　该算法通过一种确定的ｓ一近似方法来准确挖掘数据流中的频　律，并通过可视化形式表现出来　０　。随着多媒体以及网络技　术的不断发展，图像、音频、视频等多媒体数据在不断增多，要　繁项，并利用概要数据来满足用户的查询，并且有效地减少算　法的空间复杂性和平均处理时间，得到较小的频率误差。刘大　对这些数据进行有效管理和查询非常困难，而采用具有学习能　力的数据挖掘技术，可以通过发掘大量数据信息所具有的潜在　内容特征而进行多媒体数据的有效聚类，能够更好地对大量数　据进行管理，方便对数据实行统计查询　。生物信息网络是　指运用数学方法和图论、网络拓扑学等方法来研究生物信息系　有等人　提出一种基于环路紧密度的复杂网络社区挖掘算　法，该算法通过环路紧密值来实现网络社区的有效聚类，使用　广度优先遍历算法遍历全图，并取与各个核中最为紧密的核作　为归属，在实验中通过真实网络数据集来对挖掘算法的有效性　进行了验证。张鸿等人　提出一种基于关系矩阵融合的多媒　体数据聚类方法，该方法通过对图像以及音／视频数据进行特　性矩阵的相关性统计分析，并进行相关性融合来挖掘数据集的　统的网络，它包括生物科学、数学模型、计算机科学等技术，以　网络的思维来研究生物系统各个组成部分的联系以及组织结　构等　，　。　收稿日期：２０１４—０４—１５；修回１３期：２０１４－０６—０４　基金项目：广东省“产学研”资助项目（２０１２Ｂ０９１１０００４３）　作者简介：唐晓东（１９６８．），男，湖南衡阳人，副教授，硕士，主要研究方向为电子商务、数据挖掘（ｅｌｌｉｐｔｉｃ＠１６３．ｃｏｍ）　第６期　唐晓东：基于关联规则映射的生物信息网络多维数据挖掘算法　据集　和　。　・１６１５・　相似语义，最后采用基于相似度的循环迭代方法来实现数据聚　类。Ｐｅｎｇ等人－】。。提出一种基于数据集成、数据挖掘和多准则　１　决策的事故信息管理框架，它可以支持异构的分布式事件数　据，让决策者（ＤＭＳ）决定检测异常并提取有用的知识，能够协　ｆ　一　助ＤＭＳ评估风险，并在事件中选择一个合适的替代方案，提供　差异化服务，以满足不同事件管理阶段的要求。　，（Ｖｉ，　）：ｌ；　【　一　１　卢　ｌ　０　（４）　从大多数数据集中区别出数据集　和数据集　后，再通　１　数据集关联规则映射　在一个生物信息网络中，为了能对网络所构建的拓扑结构　过这两个数据集之间的关联映射就可以把它们分别区分出来。　接着本文通过概率估计的方法来得到数据挖掘频率，采用　的概率估计公式为　ｍ　，图进行挖掘，并减少在搜索生物信息网络的特征数据时所带来　的复杂度，本文结合网络数据的关联映射关系确定网络数据集　２　的关联规则，提高数据挖掘效率，并且通过概率估计的方法得　到数据挖掘频率，并引入挖掘因子和相对误差来提高挖掘精　度　Ｉ，　］。图１为采用关联规则映射方法的数据挖掘结构图。　图１数据挖掘结构图　对于生物信息网络的结构拓扑图，本文定义一个Ｇ＝（　，　Ｅ）来表示拓扑图。其中：；　Ｖ表示组成该网络的各个组织结构，　、　●●●●●●●●Ｊ　，，．．．．．．．．．．．，　．　．，Ｅ表示联系各个组织结构的边。在Ｖ＝（ｌ　　，　，…　）中，　（０≤ｉ≤ｎ）表示数据集，、●●●●●●●●●●Ｊ　＝（　　２　一，　），　（０≤　≤ｍ）表　．．．．．．＋　．．．．．．．　，　示该数据集的一个有效数据。假设数据集　；　与数据集　之　间的关联程度可以用关联属性组（　，卢　０　）来表示，　表示　数据集之间的大小关联，　表示数据集之间的语义关联，０　表　示数据集之间的类型关联。　对于数据集之间的关联映射关系，本文进行如下定义：　定义１　对于数据集　与数据集　之间的关联属性组　（　，卢　０　），都可以表示为这两个数据集中的任意数据之间　的关联程度。　定义２　可以采用关联系数矩阵的形式来表示关联属性　组。关联系数矩阵是这两个数据集中的所有数据之间关联程　度的平均值。　Ｋｌ　　ｌｆ　１Ｏ３ｌ　Ｉ＝ｌ；ｉｋ］ｆ　Ｏｌｉ　ｌ…　ｉ　ｌ］　ｌ…卢ｌｌ；　　］ｌｆｌ；　０ｉ　ｌ…Ｏｉｌ　Ｊｋ］　　（１）　【０　Ｊ　ｌ　…ｎ　１八卢１＾…卢　１八口１　…ｐｄ　Ｊ　定义３数据集之间除了具有关联性外，也具有差异性。　差异性系数矩阵用关联属性矩阵的倒数形式表示。　１　ｌ　１　１　１　Ｏｌｉｋ　ｌ　卢ｆｌ　卢Ｉ　０；ｌ　０１　卢　（２）　１　１　１　１　１　Ｏｉｋ　１＾　口ｎ　０ｌ　０　１　根据关联系数矩阵和差异性系数矩阵，对于数据集　和　数据集　之间的关联映射为　ｋ１　ｋ１　ｌ一百　’…　ｍ—　得到数据集　和数据集　之间的关联映射后，采用互相　关系矩阵得到数据集的关联规则，来从大多数数据集中区别数　㈥　为了提高数据挖掘精度，本文引入了挖掘因子和相对　误差。　篓　．　２　㈤　其中：Ａ表示挖掘因子，取值为（０，１），　表示预期挖掘概率与　实际挖掘情况之间的相对误差。为了取得合适的Ａ值，使得　挖掘频率达到最大，本文在（０，１）使Ａ取不同的值，得到了图２　所示的挖掘频率变化情况。从图２中可以看出，当取值为Ａ＝　０．７时，挖掘频率最大。　２　多维数据的数据集特性挖掘　本文假设数据样本是分布于多维子空间，当在同一子空间　内两个数据样本的关联程度越大，则具有强相关性，关联程度　越小，则具有弱相关性。对同一子空间的数据样本进行区分　时，则需要根据数据样本的关联程度来制定挖掘规则。当数据　集是位于不同的子空间，则只需要根据子空间的关联性质来区　分出子空间即可　。　假设子空间的维度为ｄ，先挖掘处于不同子空间的不同数　据集，其中子空间用矩阵Ｍ表示，定义为　Ｍｆｌ　　］　ＪＩ　＝　ｄ≤ｎ　（７）　假设两个数据集　和　分别位于两个不同的子空间　Ｍ　（ｉ≤ｄ）和　（ｋ≤ｄ），其中这两个子空间的欧几里德距离为　Ｄ（ｉ，ｋ），两个数据集的欧几里德距离为ｄ（ｉ，ｋ）。则对于不同　子空间的两个数据集的挖掘公式为　Ｗ（Ｍ　，Ｍ　）＝．等＿　ｌｆ　Ｊ　］　　（　）Ｐ（　）×ｌ０　ＪＤ（一　，　）　＋ｄ一　（　，　）　（８）　其中：　表示子空间挖掘因子，Ｐ（　）、Ｐ（　）分别表示数据集　和数据集　的挖掘频率。　对于同一子空间的不同数据集的挖掘，通过不同数据集之　间的关联程度进行区分。先通过式（１）和（２）求得　和　，然　后求得在同一空间下数据集　和　的关联因子：　…　］　（９）　得到数据集　和　的关联因子ｇ（ｉ，ｋ）之后，可以得到相　同子空间下这两个数据集的挖掘公式为　・１６１６・　计算机应用研究　第３２卷　（　，伊）＝（Ｐ（　）一Ｐ（　））ｇ（　，ｋ）ｄ（　，ｋ）×　ｅｇ（‘，　）　７８．１％，Ｂａｌ的算法为８０．２％，而且从数据集数量不断增加时　（１０）　ｆｌ；　Ｘｌ　ｋ‘一　ｍ！Ｉ　１　ｆ　１ｆ…　ｍ；Ｉ‘１　ｌ　ｍ　…　１　Ｊｌ　ｍＩ…Ｘｌｉ　Ｊ　挖掘精度的变化情况来看，本文算法的挖掘精度所受到的影响　较小。　，，　．．．．．。．。．．．．．．．．　图５为在不同数据集数量下的算法运行时间，算法运行时　假设在同一空间　‘下数据集之间关联程度限定阈值　（　），当数据集之间的关联因子ｇ（ｉ，ｋ）大于　（　）时，则这两　个数据集具有强相关性，则两个数据集的区分公式写成　ｆ　…　、　间都是随着所采用的数据集的数量的增多而增大，在数据集数　量为１　０００时本文算法的运行时间为１６．７　Ｓ，Ｓｕｎ算法的运行　时间为ｌ９．７　ｓ，Ｂａｌ的算法的运行时间为２１．３　Ｓ，所用运行时间　越短，更能反映算法在计算能力上的优势，也更加适用于对实　　　…Ｉ【　　　ｌＪ　，　（　Ｖ声、一　（　（　～　）　际的大规模数据集进行挖掘。ｒ　…　、　Ｉ【　…　　，　Ｊ　“（√　Ｖ　…　～耋（　）＿尸（　）（　１　）　当数据集之间的关联因子ｇ（ｉ，ｋ）小于　（　）时，则这两个　数据集具有弱相关性，则两个数据集的区分公式写成　ｆ　ｌ　…　１　Ｉ；　；１　（　，　）　＋　ｌ３）　・　ｊ　；ｌ　（　，Ｖｋ）　・　Ｊ　（Ｖｋ）＝　（＇ＩＴｅ　一１）　＋÷　（Ｐ（　）一Ｐ（　））（１４）　３实验分析　为了验证本文提出的基于关联规则映射的生物信息网络　多维数据挖掘算法，所采用的实验仿真硬件平台为ＩＢＭ的ＰＣ　机，主频为２．３　ＧＨｚ　ＣＰＵ，操作系统为Ｗｉｎｄｏｗｓ　ＸＰ，内存为　４　ＧＢ。软件仿真平台为ＭＡＴＬＡＢ　７．０，在实验中准备了随机真　实的数据集，包括赛车数据集、天气预报数据集、金融走势数据　集等１　０００个数据集。在实验中作为对比的算法有两组，一组　为Ｓｕｎ等人　提出的一种异构信息网数据挖掘的分析方法，　另一组是Ｂａｌ＿ｌ　提出的一种基于粗糙集理论的数据挖掘方法。　实验分为三个部分，包括在不同数据集数量下内存占用情况、　在不同数据集数量下的算法挖掘精度以及在不同数据集数量　下的算法运行时间。　图３为在不同数据集数量下内存占用情况，内存占用越　少，说明该数据挖掘算法的性能情况越好，越适合于对实际真　实的大型数据集进行挖掘。从图中的情况来看，基于关联规则　映射的挖掘算法所占用的内存容量较少，而基于粗糙集理论和　异构信息网的数据挖掘算法所占用的内存容量较多，因此在对　数据集进行挖掘的性能上本文提出算法具有更大的优势。　料　瞩　图２挖掘频率随Ａ　图３不同数据集数量下　取不同值时的变化情况　内存占用情况　图４为在不同数据集数量下的算法挖掘精度情况，数据集　数量越大的情况下能保持较好的挖掘精度，则说明该挖掘算法　在实际应用上的有效性。从图４中的情况可以看出，在挖掘精　度上本文算法占据领先优势，在数据集数量为１　０００的情况　下，挖掘精度达到了８６．７％，而Ｓｕｎ算法的挖掘精度仅为　厘　曹　２００　４００　６００　８００　１ｏｏＯ　数据集数量　数据集数量　图４在不同数据集数量下的　图５在不同数据集数量下的　算法挖掘精度　算法运行时间　４结束语　本文提出了一种基于关联规则映射的生物信息网络多维　数据挖掘算法，该算法针对生物信息网络中复杂的大规模数据　信息进行挖掘，所采用的方法为数据集关联规则映射和多维数　据的数据集特性挖掘方法，前者主要是通过得到数据集之间的　关联映射关系来提高数据挖掘频率和数据挖掘精度，后者则是　通过对相同子空间和不同子空间的数据集特性集进行区分，从　而达到有效的数据挖掘效果。实验中通过对挖掘算法进行了　三组评估实验来分析算法在挖掘精度、内存占用以及运行时间　上的独特优势。　参考文献：　［１］Ｌｏｗ　Ｙ，Ｂｉｃｋｓｏｎ　Ｄ，Ｇｏｎｚａｌｅｚ　Ｊ，ｅｔ　ａ１．Ｄｉｓｔｒｉｂｕｔｅｄ　ＧｒａｐｈＬａｂ：ａ　ｆｒａｍｅ－　ｗｏｒｋ　ｆｏｒ　ｍａｃｈｉｎｅ　ｌｅａｒｎｉｎｇ　ａｎｄ　ｄａｔａ　ｍｉｎｉｎｇ　ｉｎ　ｔｈｅ　ｃｌｏｕｄ［Ｊ］．Ｐｒｏｃｅｅｄ－　ｉｎｇｓ　ｏｆ　ｔｈｅ　ＶＬＤＢ　Ｅｎｄｏｗｍｅｎｔ，２０１２，５（８）：７１６￣２７．　［２］Ａｌｃａｌｔｉ—Ｆｄｅｚ　Ｊ，Ｆｅｒｎａｎｄｅｚ　Ａ，Ｌｕｅｎｇｏ　Ｊ，ｅｔ　ａ１．ＫＥＥＬ　ｄａｔａ—ｍｉｎｉｎｇ　ｓｏｆｔ－　ｗａｒｅ　ｔｏｏｌ：ｄａｔａ　ｓｅｔ　ｒｅｐｏｓｉｔｏｒｙ，ｉｎｔｅｇｒａｔｉｏｎ　ｏｆ　ａｌｇｏｒｉｔｈｍｓ　ａｎｄ　ｅｘｐｅｒｉｍｅｎ－　ｔｌａ　ａｎａｌｙｓｉｓ　ｆｒａｍｅｗｏｒｋ［Ｊ］．Ｊｏｕｒｎａｌ　ｏｆ　Ｍｕｌｔｉｐｌｅ—Ｖａｌｕｅｄ　Ｌｏｇｉｃ＆Ｓｏｆｔ　Ｃｏｍｐｕｔｉｎｇ，２０１１，１２（１７）：２０４—２０９．　［３］赵川源，何东健，乔永亮．基于多光谱图像和数据挖掘的多特征杂　草识别方法［Ｊ］．农业工程学报，２０１３，２９（２）：１９２—１９８．　［４］宋淑彩，祁爱华，王剑雄．面向Ｗｅｂ的数据挖掘技术在网站优化　中的个性化推荐方法的研究与应用［Ｊ］．科技通报，２０１２，２８（２）：　１１７．１１９．　［５］Ｇａｒｃｉａ　Ｓ，Ｆｅｒｍｉｎｄｅｚ　Ａ，Ｌｕｅｎｇｏ　Ｊ，ｅｔ　ａ１．Ａｄｖａｎｃｅｄ　ｎｏｎｐａｒａｍｅｔｒｉｃ　ｔｅｓｔｓ　ｆｏｒ　ｍｕｌｔｉｐｌｅ　ｃｏｍｐａｒｉｓｏｎｓ　ｉｎ　ｔｈｅ　ｄｅｓｉｇｎ　ｏｆ　ｅｘｐｅｒｉｍｅｎｔｓ　ｉｎ　ｃｏｍｐｕｔａｔｉｏｎａｌ　ｉｎｔｅｌｌｉｇｅｎｃｅ　ａｎｄ　ｄａｔａ　ｍｉｎｉｎｇ：ｅｘｐｅｒｉｍｅｎｔａｌ　ａｎａｌｙｓｉｓ　ｏｆ　ｐｏｗｅｒ［Ｊ］．　１ｎｆｏｒｍａｔｉｏｎ　Ｓｃｉｅｎｃｅｓ，２０１０，１８０（１Ｏ）：２０４４—２０６４．　［６］刘殷雷，刘玉葆，陈程．不确定性数据流上频繁项集挖掘的有效算　法［Ｊ］．计算机研究与发展，２０１１，４８（３）：１－７．　［７］王伟平，张冬冬．一种有效的挖掘数据流近似频繁项算法［Ｊ］．软　件学报，２００７，１８（４）：８８４・８９２．　［８］刘大有，杨建宁，杨博，等．基于环路紧密度的复杂网络社区挖掘　方法［Ｊ］．吉林大学学报：工学版，２０１３，３（１）：９８—１０５．　［９］张鸿，吴飞，张晓龙．基于关系矩阵融合的多媒体数据聚类［Ｊ］．　计算机学报，２０１１，３４（９）：１７０５—１７１１．　（下转第１６２０页）　・１６２０・　计算机应用研究　第３２卷　方向由ＳＶＭ来确定，这样便提高了准确率。此外，后者的性能　２Ｄ０９，４３（２）：１０５－１２１．　更为稳定，不会因为训练数据的改变而导致测试性能发生波　［２］周强，孙茂松，黄昌宁，等．汉语最长名词短语的自动识别［Ｊ］．软　动。但是由图５可以看出，随着训练集比重的提高，算法的准　件学报，２０００，１１（２）：１９５—２０１．　确率并没有随之提高，原因在于数据量的庞大，２０％的数据特　［３］Ｇｏｌｄｂｅｒｇ　Ｙ，Ｅｌｈａｄａｄ　Ｍ．Ａｎ　ｅｆｉｆｃｉｅｎｔ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｅａｓｙ—ｆｉｒｓｔ　ｎｏｎ－ｄｉｒｅｃ－　征已经能很好地训练算法。根据短语本身的特点分析，最能够　ｔｉｏｎａｌ　ｄｅｐｅｎｄｅｎｃｙ　ｐａｒｓｉｎｇ［Ｃ］／／Ｐｒｏｃ　ｏｆ　Ａｎｎｕａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｈｕ　影响算法性能的特征主要在于词性特征以及节点的位置、长度　ｍａｎ　Ｌａｎｇｕａｇｅ　Ｔｅｃｈｎｏｌｏｇｉｅｓ　ａｎｄ　ｔｈｅ　Ｎｏｒｔｈ　Ａｍｅｒｉｃａｎ　Ｃｈａｐｔｅｒ　ｏｆ　ｔｈｅ　Ａｓｓｏｃｉａｔｉｏｎ　ｆｏｒ　Ｃｏｍｐｕｔａｔｉｏｎａｌ　Ｌｉｎｇｕｉｓｔｉｃｓ．２０１０：７４２－７５０．　等特征，词本身特征对算法的影响更小一些。　本文还将结合ＳＶＭ的简单边优先算法与基于最大生成树　［４］冯志伟．机器翻译研究［Ｍ］．北京：中国对外翻译出版公司，２００４：　６２ｌ一６２２．　算法的ｃｔｂｐａｒｓｅｒ的性能进行了比较，实验结果如表２所示。　［５］李彬，刘挺，秦兵，等．基于语义依存的汉语句子相似度计算［Ｊ］．　Ｃｔｂｐａｒｓｅｒ基于宾州中文树库标准，能很好地应用于完整句子的　计算机应用研究，２００３，２０（１２）：ｌ５一ｌ７．　依存分析。然而由表２可以看出对于复杂名词短语进行依存　［６］Ｘｕｅ　Ｎｉａｎｗｅｎ，Ｘｉａ　Ｆｅｉ．Ｔｈｅ　ｂｒａｃｋｅｔｉｎｇ　ｇｕｉｄｅｌｉｎｅｓ　ｏｆｒ　ｔｈｅ　ｐｅｎｎ　Ｃｈｉｎｅｓｅ　分析时，算法的边和根还有整个短语的准确率都高于ｃｔｂｐａｒｓｅｒ　ｔｒｅｅｂａｎｋ（３．０），ＩＲＣＳ－００－０８［Ｒ］．Ｐｈｉｌａｄｅｌｐｈｉａ：Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｐｅｎｎ—　的结果，甚至算法的最坏值也均优于ｃｔｂｐａｒｓｅｒ。这也很好地说　ｓｙｌｖａｎｉａ，２０１０．　明了复杂名词短语的依存分析对句子依存分析的重要性，将复　［７］Ｚｈａｎｇ　Ｙｕｅ，Ｃｌａｒｋ　Ｓ．Ｔｒａｎｓｉｔｉｏｎ—ｂａｓｅｄ　ｐａｒｓｉｎｇ　ｏｆ　ｔｈｅ　Ｃｈｉｎｅｓｅ　ｔｒｅｅｂａｎｋ　杂名词短语成分和句子的其他成分分别分析，并将得到的子树　ｕｓｉｎｇ　ａ　ｇｌｏｂａｌ　ｄｉｓｃｒｉｍｉｎａｔｉｖｅ　ｍｏｄｅｌ［Ｃ］／／Ｐｒｏｃ　ｏｆｔｈｅ　ｌｌｔｈ　Ｉｎｔｅｒｎａｔｉｏｎ－　相结合得到句子依存分析的完整结果，能够有效地提高分析的　ａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｐａｒｓｉｎｇ　Ｔｅｃｈｎｏｌｏｇｉｅｓ．２００９：１６２－１７１．　效果。　［８］ＭｃＤｏｎａｌｄ　Ｒ，Ｐｅｒｅｉｒａ　Ｆ．Ｎｏｎ—ｐｍｊｅｃｔｉｖｅ　ｄｅｐｅｎｄｅｎｃｙ　ｐａｒｓｉｎｇ　ｕｓｉｎｇ　表２结合ＳＶＭ简单边优先算法与ｃｔｂｐａｒｓｅｒ性能比较　ｓｐａｎｎｉｎｇ　ｔｒｅｅ　ａｌｇｏｒｉｔｈｍｓ［Ｃ］／／Ｐｒｏｃ　ｏｆ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｈｕｍａｎ　Ｌａｎ—　ｇｕａｇｅ　Ｔｅｃｈｎｏｌｏｇｙ　ａｎｄ　Ｅｍｐｉｉｒｃａｌ　Ｍｅｔｈｏｄｓ　ｉｎ　Ｎａｔｕｒｌａ　Ｌａｎｇｕａｇｅ　Ｐｒｏ—　ｃｅｓｓｉｎｇ．２００５：５２３－５３０．　［９］ＭｃＤｏｎａｌｄ　Ｒ，Ｃｒａｍｍｅｒ　Ｋ，Ｐｅｒｅｉｒａ　Ｆ．Ｏｎｌｉｎｅ　ｌａｒｇｅ—ｍａｒｇｉｎ　ｔｒａｉｎｉｎｇ　ｏｆ　ｄｅｐｅｎｄｅｎｃｙ　ｐａｒｓｅｒｓ［Ｃ］／／Ｐｒｏｃ　ｏｆ　ｔｈｅ　４３ｒｄ　Ａｎｎｕａｌ　Ｍｅｅｔｉｎｇ　ｏｆ　ｔｈｅ　Ａｓ－　４．４算法的不足　ｓｏｃｉａｔｉｏｎ　ｆｏｒ　Ｃｏｍｐｕｔａｔｉｏｎａｌ　Ｌｉｎｇｕｉｓｔｉｃｓ．２００５：９１－９８．　在分析算法的分析结果时，笔者发现当短语长度比较长或　［１０］Ｚｈａｎｇ　Ｙｕｅ，Ｃｌｒａｋ　Ｓ．Ａ　ｔａｌｅ　ｏｆ　ｔｗｏ　ｐａｒｓｅｒｓ：ｉｎｖｅｓｔｉｇａｔｉｎｇ　ｎａｄ　ｃｏｍｂｉ－　者短语中有依存关系的两个词之间的距离较长而其中之一和　ｎｉｎｇ　ｇｒａｐｈ・・ｂａｓｅｄ　ａｎｄ　ｔｒａｎｓｉｔｉｏｎ－ｂａｓｅｄ　ｄｅｐｅｎｄｅｎｃｙ　ｐａｒｓｉｎｇ　ｕｓｉｎｇ　邻近的词也可以构成依存关系时，往往会优先将邻近的两个节　ｂｅａｍ－ｓｅｒａｃｈ［Ｃ］／／Ｐｒｏｃ　ｏｆ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｅｍｐｉｒｉｃｌａ　Ｍｅｔｈｏｄｓ　ｉｎ　Ｎａｔｕ—　ｒａｌ　Ｌａｎｇｕａｇｅ　Ｐｒｏｃｅｓｓｉｎｇ．２００８：５６２・５７１．　点连接而导致错误。这相比基于图的算法是一个最大的不足，　［１１］周惠巍，黄德根，高洁，等．最大生成树算法和决策式算法相结合　这也是笔者以后需要解决的问题。　的中文依存关系解析［Ｊ］．中文信息学报，２０１２，２６（３）：１６－２１．　５结束语　［１２］辛霄，范士喜，王轩，等．基于最大熵的依存句法分析［Ｊ］．中文信　息学报，２００９，２３（２）：１８　２２．　本文提出了对简单边优先的依存句法分析算法，并用其对　［１３］刘挺，马金山，李生．基于词汇支配度的汉语依存分析模型［Ｊ］．　复杂名词短语进行依存分析，算法应用的对象是包含至少三个　软件学报，２００６，１７（９）：１８７６—１８８３．　词语的复杂名词短语。本文对算法进行了改进，但算法性能仍　［１４］郭庆琳，李艳梅，唐琦．基于ＶＳＭ的文本相似度计算的研究［Ｊ］．　有不足。下一步的工作主要包括两个方向：ａ）进一步解决长　计算机应用研究，２００８，２５（１１）：２３５６－２３５８．　［１５］Ｃｏｌｌｉｎｓ　Ｍ．Ｄｉｓｃｒｉｍｉｎａｔｉｖｅ　ｔｒａｉｎｉｎｇ　ｍｅｔｈｏｄｓ　ｆｏｒ　ｈｉｄｄｅｎ　Ｍａｒｋｏｖ　ｍｏｄｅｌｓ：　距离依存关系的识别；ｂ）对复杂名词短语内部依存关系类型　ｔｈｅｏｒｙ　ａｎｄ　ｅｘｐｅｒｉｍｅｎｔｓ　ｗｉｔｈ　ｐｅｒｃｅｐｔｒｏｎ　ａｌｇｏｒｉｔｈｍｓ［ｃ］／／Ｐｒｏｃ　ｏｆ　的确定。　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｅｍｐｉｉｒｃａｌ　Ｍｅｔｈｏｄｓ　ｉｎ　Ｎａｔｕｒｌａ　Ｌａｎｇｕａｇｅ　Ｐｒｏｃｅｓｓｉｎｇ．　参考文献：　２００７：ｌ一８．　［１］Ｇｉｒｊｕ　Ｒ，Ｎａｋｏｖ　Ｐ，Ｎａｓｔａｓｅ　Ｖ，ｅｔ　ａ１．Ｃｌａｓｓｉｉｆｃａｔｉｏｎ　ｏｆ　ｓｅｍａｎｔｉｃ　ｒｅｌａｔｉｏｎｓ　［１６］闰友彪，陈元琰．机器学习的主要策略综述［Ｊ］．计算机应用研　ｂｅｔｗｅｅｎ　ｎｏｍｉｎａｌｓ［Ｊ］．Ｌａｎｇｕａｇｅ　Ｒｅｓｏｕｒｃｅｓ　ａｎｄ　Ｅｖａｌｕａｔｉｏｎ，　究，２００４，２１（７）：４－１３．　（上接第１６１６页）　Ｙｏｒｋ：ＡＣＭ　Ｐｒｅｓｓ，２０１１：４９３—５０１．　［１０］Ｐｅｎｇ　Ｙｉ，Ｚｈａｎｇ　Ｙｏｎｇ，Ｔａｎｇ　Ｙｕ，ｅｔ　ａ１．Ａｎ　ｉｎｃｉｄｅｎｔ　ｉｎｆｏｒｍａｔｉｏｎ　ｎｌｎａ－　［１３］Ｔｈｅｌｗａｌｌ　Ｍ，Ｗｉｌｋｉｎｓｏｎ　Ｄ，Ｕｐｐａｌ　Ｓ．Ｄａｔａ　ｍｉｎｉｎｇ　ｅｍｏｔｉｏｎ　ｉｎ　ｓｏｃｉａｌ　ｎｅｔ—　ａｇｅｍｅｎｔ　ｆｒａｍｅｗｏｒｋ　ｂａｓｅｄ　ｏｎ　ｄａｔａ　ｉｎｔｅｇｒａｔｉｏｎ，ｄａｔａ　ｍｉｎｉｎｇ，ａｎｄ　ｍｕｌｔｉ－　ｗｏｒｋ　ｃｏｍｍｕｎｉｃａｔｉｏｎ：ｇｅｎｄｅｒ　ｄｉｆｆｅｒｅｎｃｅｓ　ｉｎ　ＭｙＳｐａｃｅ［Ｊ］．Ｊｏｕｒｎａｌ　ｏｆ　ｃｒｉｔｅｒｉａ　ｄｅｃｉｓｉｏｎ　ｍａｋｉｎｇ［Ｊ］．Ｄｅｃｉｓｉｏｎ　Ｓｕｐｐｏｒｔ　Ｓｙｓｔｅｍｓ，２０１　１，５１　ｔｈｅ　Ａｍｅｒｉｃａｎ　Ｓｏｃｉｅｔｙ　ｆｏｒ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ，　（２）：３１６—３２７．　２０１０，６１（１）：１９０－１９９．　［１１］Ｎｇａｉ　Ｅ　Ｗ　Ｔ，Ｈｕ　Ｙｏｎｇ，Ｗｏｎｇ　Ｙ　Ｈ，ｅｔ　ａ１．Ｔｈｅ　ａｐｐｌｉｃａｔｉｏｎ　ｏｆ　ｄａｔａ　ｍｉｎ—　［１４］Ｓｕｎ　Ｙｉｚｈｏｕ，Ｈａｎ　Ｊｉａｗｅｉ，Ｙａｎ　Ｘｉｆｅｎｇ，ｅｔ　ａ１．Ｍｉｎｉｎｇ　ｋｎｏｗｌｅｄｇｅ　ｆｒｏｍ　ｉｎ—　ｉｎｇ　ｔｅｃｈｎｉｑｕｅｓ　ｉｎ　ｆｉｎａｎｃｉｌａ　ｆｒａｕｄ　ｄｅｔｅｃｔｉｏｎ：ａ　ｃｌａｓｓｉｉｆｃａｔｉｏｎ　ｆｒａｍｅｗｏｒｋ　ｔｅｒｃｏｎｎｅｃｔｅｄ　ｄａｔａ：ａ　ｈｅｔｅｒｏｇｅｎｅｏｕｓ　ｉｎｆｏｒｍａｔｉｏｎ　ｎｅｔｗｏｒｋ　ａｎａｌｙｓｉｓ　ｐ—　ａｎｄ　ａｌｌ　ａｃａｄｅｍｉｃ　ｒｅｖｉｅｗ　ｏｆ　ｌｉｔｅｒａｔｕｒｅ［Ｊ］．Ｄｅｃｉｓｉｏｎ　Ｓｕｐｐｏｒｔ　Ｓｙｓ－　ｐｒｅａｃｈ［Ｊ］．Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　ＶＬＤＢ　Ｅｎｄｏｗｍｅｎｔ，２０１２，５（１２）：　ｔｅｍｓ，２０１１，５０（３）：５５９—５６９．　２０２２．２０２３．　［１２］Ｍｏｈａｍｍｅｄ　Ｎ，Ｃｈｅｎ　Ｒｕｉ，Ｆｕｎｇ　Ｂ，ｅｔ　ａ１．Ｄｉｆｆｅｒｅｎｔｉａｌｌｙ　ｐｒｉｖａｔｅ　ｄａｔａ　［１５］Ｂａｌ　Ｍ．Ｒｏｕｇｈ　ｓｅｔｓ　ｔｈｅｏｒｙ　ａｓ　ｓｙｍｂｏｌｉｃ　ｄａｔａ　ｍｉｎｉｎｇ　ｍｅｔｈｏｄ：ｎａ　ａｐｐｌｉｃａ—　ｒｅｌｅａｓｅ　ｆｏｒ　ｄａｔａ　ｍｉｎｉｎｇ［Ｃ］／／Ｐｒｏｅ　ｏｆ　ｔｈｅ　１７ｔｈ　ＡＣＭ　ＳＩＧＫＤＤ　Ｉｎｔｅｍａ・　ｔｉｏｎ　ｏｎ　ｃｏｍｐｌｅｔｅ　ｄｅｃｉｓｉｏｎ　ｔａｂｌｅ［Ｊ］．Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｃｉｅｎｃｅｓ　Ｌｅｔｔｅｒｓ，　ｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｋｎｏｗｌｅｄｇｅ　Ｄｉｓｃｏｖｅｒｙ　ａｎｄ　Ｄａｔａ　Ｍｉｎｉｎｇ．Ｎｅｗ　２０１３，２（１）：１１１－１１６．