不确定图数据挖掘算法研究.pdf

《不确定图数据挖掘算法研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、中文摘要中又捅斐随着计算机产业及互联网的不断发展，各行各业积累了海量的数据信息，图作为最通用的数据结构之一，在描述数据的属性及结构特征等方面具有显著的优势：一方面它可以描述生物、化学等学科中的化合物及蛋白质并直观表达各类性质；另一方面在越来越广泛使用的互联网以及现实生活中，人与人之间或不同个体单位所构成的社交网络也都可抽象成图，使用图来描述的数据信息称为图数据。由于数据来源的差异及描述手段的限制，实际生活中获得的图数据经常出现结构与属性不精确和不完整的情况，具有各种不确定性的图数据广泛存在，从不确定图数据中所蕴含的丰富结构及语义信息中挖掘知识具有重要意义。本文对不确定图挖掘的几个典型算法问题

2、进行了研究。主要研究成果如下：1．针对不确定图中的频繁子图挖掘问题提出一种基于随机游走技术的极大频繁子图挖掘算法。该算法基于随机游走技术，利用不确定图自身的特点，结合其与确定图的关系，避免了枚举指数级别可能图实例的计算，可高效快速地发现不确定图中的极大频繁子图。2．针对在不确定图中挖掘紧密子图问题提出一套有效的解决方案。首先对问题进行了形式化的定义，然后在理论上证明了紧密子图发现问题的计算复杂性，并根据不同的问题规模提出基于分枝限界策略的精确算法和具有更高效率的近似算法，实验证实所提算法可以有效挖掘不确定图中存在概率较高的紧密子图。3．在挖掘不确定图中紧密子图的相关研究基础上，提出适用于无线

3、传感器网络特点的紧密区域发现算法。该算法首先在无线传感器网络中分布式地构建逻辑网络并将该网络抽象为不确定图，然后应用计算量较小的剪枝策略对网络进行搜索，最终快速有效地发现网络中的紧密子区域，为无线传感器网中其他有关的算法和应用提供基础。关键词：不确定图；图挖掘；极大频繁子图；紧密子图；无线传感器网络黑龙江大学硕士学位论文AbstractWiththerapiddevelopmentofcomputertechnologyindustryandtheInternet，massivedatahavebeenaccumulatedinmoreandmorereal．worldapplication

4、s．AsoneoIthemostgeneraldatastructures．graphshavesignificantadvantageswhentheyareusedtomodelpropertyandstructurefeaturesofknowledge．Ononeside，graphscanbedirectlyusedtorepresentpatternsandpropertyinformationinbiology,chemistry,andSOon．Ontheotherhand，moreandmoreapplicationsintheInternetandreallifesuch

5、astherelationshipsbetweenpeoplecanmodeledasgraphs．Thedatadescribedbygraphsarecalledthegraphdata。Duetothelimitationsofdatasources，datadescriptionmethodsanddataacquisitiontechniques，graphdatathatareimpreciseandincompletelyexistsinpractice．Graphswithuncertaintiesarecalleduncertaingraphs．Largeamountofv

6、aluableandrichknowledgearecontainedinuncertaingraphs，andthusdiscoveringknowledgefromuncertaingraphsisofpracticalsignificance．Wefocusonthetechniquesformininguncertaingraphs．Themaincontributionsofthisthesisareas±ollows：Thisthesisproposesamaximalfrequentpatternminingalgorithmsonuncertaingraphset．Theal

7、gorithmisdevelopedbasedonrandomwalk．Itconsiderstherelationshipbetweenuncertaingraphsanddeterministicgraphs，thusavoidingcomputingtheexponentialnumberofpossibleworlds．ThealgorithmisabletofindK-maximalfrequent