论文部分内容阅读
摘要：由于现在科学技术的迅猛发展以及人民生活水平的不断提升，互联网行业在悄无声息的进入大众的生活中，计算机也被应用在各行各业中。从社会网络到蛋白质交互网络等不同的领域产生了大量的数据，而图作为统计这些巨大数据的一个载体不仅能精确的描述出数据的属性，还能说明数据结构的特征，这些优势让以不确定图模型的数据挖掘算法在社会中得到广泛的应用。
关键词：数据；挖掘算法；不确定图
中图分类号：TP391 文献标识码：A 文章编号：1009-3044（2015）12-0182-02
Research on Data Mining Algorithm -- with Uncertain Graph Model as an Example
HUANG Xin
（Dehong Normal College， Dehong 678400， China）
Abstract： since the rapid development of science and technology and the continuous improvement of people’s living standards， the Internet industry in quietly into the public life， computer has been used in all walks of life. From the field of social network to different protein interaction networks produce a large amount of data， and the map as a carrier of these huge data statistics can not only accurately describe the attribute of the data， but also illustrate the characteristics of the data structure， these advantages make with uncertain graph data mining algorithm is widely used in the society.
Key words： data mining； algorithm； uncertain graph
现代的科学技术正在以飞快的速度发展，其中互联网和计算机技术也在蓬勃发展，国内的每个行业都会积累大量的数据信息来促进本企业的迅猛发展。不同的领域都会使用不同的图结构来记录这些数据，而不确定图模型就是统计这些数据的结构之一。但是在实际应用当中，不同的获取数据的工具以及原始数据的微小差距都能使获得的数据不精确，再加上人们个体之间的工作关系网和生活关系网都能用图来描述，将这些不确定的数据信息用图来说明就形成了不确定图模型数据。由于这些不确定图数据存在的量比较大，所以它包涵着丰富的信息，从中挖掘有用的知识是非常重要的，也是极具现实意义的。
1 数据挖掘
在利用不同的技术手段或者查阅大量的资料所获得的这些真实的、可能含有噪声的数据中挖掘出用户感兴趣的、能够理解的的有效数据的过程就称之为数据挖掘。换句话说用户需要从不完整的、模糊的、有噪声的大量的数据中发现突出点以及潜藏的有用信息。数据挖掘所涉及到的学科非常广泛，其最重要的就是借助计算机技术来完成这个过程，在最初搜集数据时需要数理统计、数据库方面的知识，在进行数据挖掘时需要各种分析工具，最后再将有效的数据与对应的模型进行转化时需要数学知识。
2 确定图数据挖掘
由于真实物理世界中的网络普遍具有不确定性，因此网络可以表示为不确定图。Jin等使用数据挖掘方法研究了如何从不确定图中挖掘连通可靠性高于某阈值的全部导出子图。该问题在蛋白质复合体发现、通信网络路由和社会网络分析中具有重要应用。
2.1 图
图，就是我们在数据结构中学到的图，它是一中存储信息的结构，在数据结构中它是被安排在后面的章节，所以很容易被我给忘记。图，在数据结构中的定义的基本意思是这样的：图中的每个节点都可以有多个父节点，多个子节点。所以图的结构是非常灵活的，它包含了链表的结构，包含了树的结果。它是整个数据结构的综合体。它的信息存储也是通过节点和边的形式进行存储。这就是图的概念，下面也给出了一个基本的图的结构图：
如图1就是一个图，该图是一个无向带权重的图，在我们现实生活中这样的图是存在的，例如我们全国的交通网络图，就是一个无向图，因为你可以到一个地方去肯定也可以沿着这条路返回，无向是两个节点不管是哪到哪沿着这条路径都可到达，例如：上图的V1——>V6可达，同时V6——>V1也可达，这样就称之为无向边。当然也存在有向边。
2.2 图数据挖掘
那么上面介绍了图的概念，那么什么事图数据挖掘，这个概念比较广，它是属于数据挖掘中的一种，我们知道数据挖掘有web数据挖掘（就是我们的百度/google等）、还有图像数据挖掘、还有基于场地的图像数据挖掘。那么图数据挖掘是什么呢？我们知道百度/谷歌是IR，他是信息检索，他是对文本信息进行检索，也就是我们的html页面。那么图的关键词搜索和IR有什么不同呢？我们知道IR是搜索包含我们关键词的文本内容全部返回给用户，但是返回的内容是否存在关系那就不好说，所以此时就出现了图的关键词搜索。图的关键词搜索就是返回给用户你输入的关键词相互之间的关系，例如：你输入张三、李四这两个人名关键词，那么图的关键词搜索机制将会返回包含在图中包含这两个关键词的节点这件的一个关系，一般是采取树的方式展现出来。那么究竟是什么关系呢？例如：张三是李四的同学，张三是李四的哥哥、张三和李四是老乡。那么这里的同学、哥哥、老乡就是这个两个关键词之间的关系。想想在IR中能做到这些吗？因为IR搜索注重的不是关系，它注重的是信息，他是将包含关键词的信息返回给用户，而不考虑关键词之间的关系。 那么在图数据挖掘中找这种关系是如何实现的呢？例如上图：假设要查找张三、李四这两个关键词，刚好在上图中有V1包含关键词张三，V2包含关键词李四，在普通的IR系统中是就将同时包含张三、李四的节点返回给用户（注意：此处的节点就是一个信息点，里面有内容而V1，V2....只是一个代号）。那图的关键词搜索返回关系，到底是返回什么关系呢？上图，我们知道从V1到V2有多条路径，如：V1——>V5——>V2、V1——>V3——>V2等等，此处就不一一列举出。那么我上面举出的两条路径，不就是一个棵树吗？一个是以V5为根节点，一个是以V3为根节点。那么节点V5和V3就是这两个关键词之间的一个关系，这就是我上面说的如何找出两个关键词之间的关系。这里就将如何找到两个关键词之间的关系总结一句话：找到包含关键词的节点公共父节点。那么这时候就面临这两个关键词的公共父节点肯定不只一个，那么我们该返回哪个？这就要看到我们图中边的权重了，这里就要用到了对图遍历的一些算法（Dijkstra），此处就不对搜索的详细过程进行过多的描述，后期我会发到此博客上。此处肯定的是将结果排序，按照到达公共父节点的路径消耗和节点的权重来排序。
2.3 不确定图数据的产生
伴随着数据收集以及存储技术日新月异的变更，互联网在社会中的应用随之增加，同时也会产生巨大的数据并且这些数据是不确定的。造成数据不确定的原因有很多种，首先其直接原因就是原始数据的不确定性，一般情况下这种不确定图数据是不能通过外在方式进行补偿的。其次要原因这里介绍三种，一是在对这些数据处理过程中要进行编码、索引、量化、存储等，每一个过程都会存在着不确定因素，这就造成了抽象数据误差。二是具体应用到每个用户的手中，而用户为了保护自己的隐私就会对加密数据进行干扰处理，使外人无法识别这些数据从而造成数据在还原过程中也出现不确定性。三是对数据进行分析完之后，往往会有缺失值的处理问题，由于仪器故障、接收双方字段不统一等因素导致最后出现缺失值，这种不确定图数据的缺失值可以通过插值的方法来削弱或解决，但是这种方法不能保证原始数据的不变，进而也引入了不确定性。
3 不确定图数据挖掘的算法研究
虽然用确定图的挖掘办法可以解决一部分不确定图数据挖掘，但是这种方法确实对确定图有极大的用途，对不确定图将会造成重要语义的严重丢失。现在数据库、网络等领域的科学研究人员讨论最多的话题就是不确定图数据的研究，他们主要针对不确定图模型的数据挖掘算法进行深入的探讨，让这种方法更好的服务于人们。
3.1 不确定图数据分类
数据挖掘方法通常是根据数据的不准确性来进行划分的，一般包括以下几种技术及方法：关联挖掘、数据划分、数据集聚三种。但是这些技术要通过相应的改进才能运用于不确定图数据的算法。其中，数据集聚可以划分为一般集聚和模糊集聚两类。一般集聚是通过针对预期的数据来提高算法的精准度；模糊集聚表示集聚的数据的结果为一个模糊的状态，可以表示为表格或者一定的概率。
3.2 不确定图数据模型
目前在国内使用最多也是应用最广的不确定图数据类型应该是可能世界模型，顾名思义这种模型是将每一个组成元素进行任意的拼凑，这种组合完的图形就能构成可能世界实例，他的概率由组成该图的元组的概率来计算。除了这种模型之外还包括半结构化数据模型、概率P—文档数据模型、关系数据模型等。
3.3 不确定图上子图研究
通过对相关资料的综合分析，可以将不确定图数据分为图的查询和图的数据挖掘两个部分。本论文着重研究对于不确定图的挖掘的研究。到目前为止，关于不确定图的研究尚未形成完整的理论体系，但不可否认的是在一定程度上已经取得了较为有价值的成就，尤其在最可靠子图问题的研究方面。针对某一用户特定的搜索值的涉及的最可靠字图课题的研究，可以通过一种两个阶段的数据挖掘的算法来解决此类搜索，首先使用抽样技术搜索可靠子图，通常可靠子图存在高概率的近似性；然后进行相应的确定图的相应指令，需要继续挖掘关键不确定图数据的算法。
4 不确定图模型数据挖掘运用
数据挖掘是为了在这个信息爆炸的大时代获取对实现目标有一定作用的信息。信息质量的优劣从其本质分析主要决定于其对原始数据挖掘的程度。当原始数据信息丰富、数据准备、挖掘方法合适的时候，其所获得的信息价值就会很高；反之，如果原始数据信息匮乏、数据模糊，挖掘方法失当，其所获得的信息价值就会很低。本节主要是为了提高获取信息价值，探讨对于不确定图模型数据挖掘技术及方法的运用。
数据挖掘的步骤会随不同领域的应用而有所变化，每一种数据挖掘技术也会有各自的特性和使用步骤，针对不同问题和需求所制定的数据挖掘过程也会存在差异。本论文着重针对不确定图模型进行相关的数据挖掘算法的运用的研究。
不确定图模型的数据挖掘完整的步骤如下：
1）理解不确定图模型。2）确定不确定图模型的数据。3）图模型数据分类。4）获取相关数据挖掘算法的知识与技术。5）分析不确定图模型数据。6）删掉错误图模型的数据。7）实际不确定图模型数据挖掘算法工作。8）测试和验证挖掘算法的结果。
由上述步骤可看出，针对不确定图模型的数据挖掘算法工作涉及了许多环节的工作，其中在数据预处理阶段的工作尤为重要，是整个不确定数据挖掘算法工作顺利开展以及取得成功的基础。
参考文献：
[1] 翟秋瑛.基于可达性的不确定图查询研究[D]. 哈尔滨：哈尔滨工业大学， 2013.
[2] 王文龙.一种高效的不确定图数据库上频繁子图模式挖掘算法[D]. 哈尔滨：哈尔滨工业大学， 2013.
[3] 杨健.不确定数据频繁模式挖掘算法研究[D].赣州：江西理工大学， 2012.
[4] 丁悦.不确定图聚类分析研究[D].西安：西北农林科技大学， 2012.
[5] 汪金苗.基于不确定数据的频繁项集挖掘算法的研究[D].淄博：山东理工大学， 2012.
[6] 周傲英，金澈清，王国仁，等.不确定性数据管理技术研究综述[J].计算机学报， 2009（01）.
[7] 夏菁.基于可信度计算的不确定数据起源研究[D]. 南京：南京航空航天大学， 2012.
[8] 汪金苗，张龙波，邓齐志，等.不确定数据频繁项集挖掘方法综述[J].计算机工程与应用， 2011（20）.
关键词：数据；挖掘算法；不确定图
中图分类号：TP391 文献标识码：A 文章编号：1009-3044（2015）12-0182-02
Research on Data Mining Algorithm -- with Uncertain Graph Model as an Example
HUANG Xin
（Dehong Normal College， Dehong 678400， China）
Abstract： since the rapid development of science and technology and the continuous improvement of people’s living standards， the Internet industry in quietly into the public life， computer has been used in all walks of life. From the field of social network to different protein interaction networks produce a large amount of data， and the map as a carrier of these huge data statistics can not only accurately describe the attribute of the data， but also illustrate the characteristics of the data structure， these advantages make with uncertain graph data mining algorithm is widely used in the society.
Key words： data mining； algorithm； uncertain graph
现代的科学技术正在以飞快的速度发展，其中互联网和计算机技术也在蓬勃发展，国内的每个行业都会积累大量的数据信息来促进本企业的迅猛发展。不同的领域都会使用不同的图结构来记录这些数据，而不确定图模型就是统计这些数据的结构之一。但是在实际应用当中，不同的获取数据的工具以及原始数据的微小差距都能使获得的数据不精确，再加上人们个体之间的工作关系网和生活关系网都能用图来描述，将这些不确定的数据信息用图来说明就形成了不确定图模型数据。由于这些不确定图数据存在的量比较大，所以它包涵着丰富的信息，从中挖掘有用的知识是非常重要的，也是极具现实意义的。
1 数据挖掘
在利用不同的技术手段或者查阅大量的资料所获得的这些真实的、可能含有噪声的数据中挖掘出用户感兴趣的、能够理解的的有效数据的过程就称之为数据挖掘。换句话说用户需要从不完整的、模糊的、有噪声的大量的数据中发现突出点以及潜藏的有用信息。数据挖掘所涉及到的学科非常广泛，其最重要的就是借助计算机技术来完成这个过程，在最初搜集数据时需要数理统计、数据库方面的知识，在进行数据挖掘时需要各种分析工具，最后再将有效的数据与对应的模型进行转化时需要数学知识。
2 确定图数据挖掘
由于真实物理世界中的网络普遍具有不确定性，因此网络可以表示为不确定图。Jin等使用数据挖掘方法研究了如何从不确定图中挖掘连通可靠性高于某阈值的全部导出子图。该问题在蛋白质复合体发现、通信网络路由和社会网络分析中具有重要应用。
2.1 图
图，就是我们在数据结构中学到的图，它是一中存储信息的结构，在数据结构中它是被安排在后面的章节，所以很容易被我给忘记。图，在数据结构中的定义的基本意思是这样的：图中的每个节点都可以有多个父节点，多个子节点。所以图的结构是非常灵活的，它包含了链表的结构，包含了树的结果。它是整个数据结构的综合体。它的信息存储也是通过节点和边的形式进行存储。这就是图的概念，下面也给出了一个基本的图的结构图：
如图1就是一个图，该图是一个无向带权重的图，在我们现实生活中这样的图是存在的，例如我们全国的交通网络图，就是一个无向图，因为你可以到一个地方去肯定也可以沿着这条路返回，无向是两个节点不管是哪到哪沿着这条路径都可到达，例如：上图的V1——>V6可达，同时V6——>V1也可达，这样就称之为无向边。当然也存在有向边。
2.2 图数据挖掘
那么上面介绍了图的概念，那么什么事图数据挖掘，这个概念比较广，它是属于数据挖掘中的一种，我们知道数据挖掘有web数据挖掘（就是我们的百度/google等）、还有图像数据挖掘、还有基于场地的图像数据挖掘。那么图数据挖掘是什么呢？我们知道百度/谷歌是IR，他是信息检索，他是对文本信息进行检索，也就是我们的html页面。那么图的关键词搜索和IR有什么不同呢？我们知道IR是搜索包含我们关键词的文本内容全部返回给用户，但是返回的内容是否存在关系那就不好说，所以此时就出现了图的关键词搜索。图的关键词搜索就是返回给用户你输入的关键词相互之间的关系，例如：你输入张三、李四这两个人名关键词，那么图的关键词搜索机制将会返回包含在图中包含这两个关键词的节点这件的一个关系，一般是采取树的方式展现出来。那么究竟是什么关系呢？例如：张三是李四的同学，张三是李四的哥哥、张三和李四是老乡。那么这里的同学、哥哥、老乡就是这个两个关键词之间的关系。想想在IR中能做到这些吗？因为IR搜索注重的不是关系，它注重的是信息，他是将包含关键词的信息返回给用户，而不考虑关键词之间的关系。 那么在图数据挖掘中找这种关系是如何实现的呢？例如上图：假设要查找张三、李四这两个关键词，刚好在上图中有V1包含关键词张三，V2包含关键词李四，在普通的IR系统中是就将同时包含张三、李四的节点返回给用户（注意：此处的节点就是一个信息点，里面有内容而V1，V2....只是一个代号）。那图的关键词搜索返回关系，到底是返回什么关系呢？上图，我们知道从V1到V2有多条路径，如：V1——>V5——>V2、V1——>V3——>V2等等，此处就不一一列举出。那么我上面举出的两条路径，不就是一个棵树吗？一个是以V5为根节点，一个是以V3为根节点。那么节点V5和V3就是这两个关键词之间的一个关系，这就是我上面说的如何找出两个关键词之间的关系。这里就将如何找到两个关键词之间的关系总结一句话：找到包含关键词的节点公共父节点。那么这时候就面临这两个关键词的公共父节点肯定不只一个，那么我们该返回哪个？这就要看到我们图中边的权重了，这里就要用到了对图遍历的一些算法（Dijkstra），此处就不对搜索的详细过程进行过多的描述，后期我会发到此博客上。此处肯定的是将结果排序，按照到达公共父节点的路径消耗和节点的权重来排序。
2.3 不确定图数据的产生
伴随着数据收集以及存储技术日新月异的变更，互联网在社会中的应用随之增加，同时也会产生巨大的数据并且这些数据是不确定的。造成数据不确定的原因有很多种，首先其直接原因就是原始数据的不确定性，一般情况下这种不确定图数据是不能通过外在方式进行补偿的。其次要原因这里介绍三种，一是在对这些数据处理过程中要进行编码、索引、量化、存储等，每一个过程都会存在着不确定因素，这就造成了抽象数据误差。二是具体应用到每个用户的手中，而用户为了保护自己的隐私就会对加密数据进行干扰处理，使外人无法识别这些数据从而造成数据在还原过程中也出现不确定性。三是对数据进行分析完之后，往往会有缺失值的处理问题，由于仪器故障、接收双方字段不统一等因素导致最后出现缺失值，这种不确定图数据的缺失值可以通过插值的方法来削弱或解决，但是这种方法不能保证原始数据的不变，进而也引入了不确定性。
3 不确定图数据挖掘的算法研究
虽然用确定图的挖掘办法可以解决一部分不确定图数据挖掘，但是这种方法确实对确定图有极大的用途，对不确定图将会造成重要语义的严重丢失。现在数据库、网络等领域的科学研究人员讨论最多的话题就是不确定图数据的研究，他们主要针对不确定图模型的数据挖掘算法进行深入的探讨，让这种方法更好的服务于人们。
3.1 不确定图数据分类
数据挖掘方法通常是根据数据的不准确性来进行划分的，一般包括以下几种技术及方法：关联挖掘、数据划分、数据集聚三种。但是这些技术要通过相应的改进才能运用于不确定图数据的算法。其中，数据集聚可以划分为一般集聚和模糊集聚两类。一般集聚是通过针对预期的数据来提高算法的精准度；模糊集聚表示集聚的数据的结果为一个模糊的状态，可以表示为表格或者一定的概率。
3.2 不确定图数据模型
目前在国内使用最多也是应用最广的不确定图数据类型应该是可能世界模型，顾名思义这种模型是将每一个组成元素进行任意的拼凑，这种组合完的图形就能构成可能世界实例，他的概率由组成该图的元组的概率来计算。除了这种模型之外还包括半结构化数据模型、概率P—文档数据模型、关系数据模型等。
3.3 不确定图上子图研究
通过对相关资料的综合分析，可以将不确定图数据分为图的查询和图的数据挖掘两个部分。本论文着重研究对于不确定图的挖掘的研究。到目前为止，关于不确定图的研究尚未形成完整的理论体系，但不可否认的是在一定程度上已经取得了较为有价值的成就，尤其在最可靠子图问题的研究方面。针对某一用户特定的搜索值的涉及的最可靠字图课题的研究，可以通过一种两个阶段的数据挖掘的算法来解决此类搜索，首先使用抽样技术搜索可靠子图，通常可靠子图存在高概率的近似性；然后进行相应的确定图的相应指令，需要继续挖掘关键不确定图数据的算法。
4 不确定图模型数据挖掘运用
数据挖掘是为了在这个信息爆炸的大时代获取对实现目标有一定作用的信息。信息质量的优劣从其本质分析主要决定于其对原始数据挖掘的程度。当原始数据信息丰富、数据准备、挖掘方法合适的时候，其所获得的信息价值就会很高；反之，如果原始数据信息匮乏、数据模糊，挖掘方法失当，其所获得的信息价值就会很低。本节主要是为了提高获取信息价值，探讨对于不确定图模型数据挖掘技术及方法的运用。
数据挖掘的步骤会随不同领域的应用而有所变化，每一种数据挖掘技术也会有各自的特性和使用步骤，针对不同问题和需求所制定的数据挖掘过程也会存在差异。本论文着重针对不确定图模型进行相关的数据挖掘算法的运用的研究。
不确定图模型的数据挖掘完整的步骤如下：
1）理解不确定图模型。2）确定不确定图模型的数据。3）图模型数据分类。4）获取相关数据挖掘算法的知识与技术。5）分析不确定图模型数据。6）删掉错误图模型的数据。7）实际不确定图模型数据挖掘算法工作。8）测试和验证挖掘算法的结果。
由上述步骤可看出，针对不确定图模型的数据挖掘算法工作涉及了许多环节的工作，其中在数据预处理阶段的工作尤为重要，是整个不确定数据挖掘算法工作顺利开展以及取得成功的基础。
参考文献：
[1] 翟秋瑛.基于可达性的不确定图查询研究[D]. 哈尔滨：哈尔滨工业大学， 2013.
[2] 王文龙.一种高效的不确定图数据库上频繁子图模式挖掘算法[D]. 哈尔滨：哈尔滨工业大学， 2013.
[3] 杨健.不确定数据频繁模式挖掘算法研究[D].赣州：江西理工大学， 2012.
[4] 丁悦.不确定图聚类分析研究[D].西安：西北农林科技大学， 2012.
[5] 汪金苗.基于不确定数据的频繁项集挖掘算法的研究[D].淄博：山东理工大学， 2012.
[6] 周傲英，金澈清，王国仁，等.不确定性数据管理技术研究综述[J].计算机学报， 2009（01）.
[7] 夏菁.基于可信度计算的不确定数据起源研究[D]. 南京：南京航空航天大学， 2012.
[8] 汪金苗，张龙波，邓齐志，等.不确定数据频繁项集挖掘方法综述[J].计算机工程与应用， 2011（20）.