大数据图数据库之数据分片，数据图数据库
节选自《大数据日知录：架构与算法》十四章，书籍目录在此
对于海量待挖掘数据，在分布式计算环境下，首先面临的问题就是如何将数据比较均匀地分配到不同的服务器上。对于非图数据来说，这个问题解决起来往往比较直观，因为记录之间独立无关联，所以对数据切分算法没有特别约束，只要机器负载尽可能均衡即可。由于图数据记录之间的强耦合性，如果数据分片不合理，不仅会造成机器之间负载不均衡，还会大量增加机器之间的网络通信（见图14-5），再考虑到图挖掘算法往往具有多轮迭代运行的特性，这样会明显放大数据切片不合理的影响，严重拖慢系统整体的运行效率，所以合理切分图数据对于离线挖掘类型图应用的运行效率来说非常重要，但是这也是至今尚未得到很好解决的一个潜在问题。
对于图数据的切片来说，怎样才是一个合理或者是好的切片方式？其判断标准应该是什么？就像上面的例子所示，衡量图数据切片是否合理主要考虑两个因素：机器负载均衡以及网络通信总量。如果单独考虑机器负载均衡，那么最好是将图数据尽可能平均地分配到各个服务器上，但是这样不能保证网络通信总量是尽可能少的（参考图14-5右端切割方式，负载比较均衡，但是网络通信较多）；如果单独考虑网络通信，那么可以将密集连通子图的所有节点尽可能放到同一台机器上，这样就有效地减少了网络通信量，但是这样很难做到机器之间的负载均衡，某个较大的密集连通子图会导致某台机器高负载。所以，合理的切片方式需要在这两个因素之间找到一个较稳妥的均衡点，以期系统整体性能最优。
下面介绍两类从不同出发点切割图数据的方法，并分别介绍典型的具体切分算法及其对应的数学分析，首先需要强调一点：在选择具体的切分算法时并非越复杂的算法越可能在实际系统中被采纳，读者可以思考其中的道理，在后面会给出解答。
14.3.1 切边法（Edge-Cut）
现在面临的问题是：给定一个巨大的图数据和p台机器，如何将其切割成p份子图？解决这个图切割问题有两种不同的思路。
切边法代表了最常见的一种思路，切割线只能穿过连接图节点的边，通过对边的切割将完整的图划分为p个子图。图14-6代表将7个节点的图分发到3台机器上，左端展示了切边法方式，图节点的编号代表节点被分发到的机器编号。
通过切边法切割后的图数据，任意一个图节点只会被分发到一台机器，但是被切割开的边数据会在两台机器中都保存，而且被切割开的边在图计算的时候意味着机器间的远程通信。很明显，系统付出的额外存储开销和通信开销取决于被切割开的边的数量，图切割时通过的边越多，则系统需额外承载的存储开销和通信开销越高。
前文有述，衡量图数据分片合理与否有两个考虑因素：负载均衡和机器通信量，所以对于切边法来说，所有具体的切割算法追求的目标不外是：如何在尽可能均衡地将图节点分配到集群中的不同机器上这一约束下，来获得最小化切割边数量。
即在每台机器被分发到的节点尽可能均匀的条件约束下，求切割边最少的方法。其中，|V|/p代表所有的节点被p台机器均分所得数值，l≥1代表不平衡调节因子，通过调节l的大小可以控制节点分配的均匀度，当其值为1时，要求完全均分，其值越大，允许的不均衡程度越高。
从上述形式化描述可以看出，lamda约等于1的时候，这个问题本质上是一个图切割中的均衡p路分区（Balanced p-way Partitioning）问题，解决这个问题有很多相关研究（有兴趣的读者可以阅读本章参考文献[4]），但是由于图切割算法的时间复杂度较高，基本不太适合处理大规模数据，所以在真实的大规模数据场景下很少被采用。
在实际的图计算系统中，经常使用的策略是节点随机均分法，即通过哈希函数将节点均分到集群的各个机器中，并不仔细考虑边切割情况。Pregel和GraphLab都采用了这种策略。这种方法的优点是快速、简单且易实现，但是从定理14.1可以证明这种方法会将图中绝大多数的边都切开。
由定理14.1可知，假设集群包含10台机器，则被切割的边比例大约为90%，即90%的边会被切开，而如果包含100台机器，则99%的边会被切开。可见，这种切分方式是效率很低的一种。
14.3.2 切点法（Vertex-Cut）
切点法代表另外一种切割图的不同思路。与切边法不同，切点法在切割图的时候，切割线只能通过图节点而非边，被切割线切割的图节点可能同时出现在多个被切割后的子图中。图14-6右侧是切点法示意图，从图中可看出，图中心的节点被切割成三份，也就是意味着这个节点会同时出现在被切割后的三个子图中。
与切边法正好相反，切点法切割后的图中，每条边只会被分发到一台机器上，不会重复存储，但是被切割的节点会被重复存储在多台机器中，因此，同样存在额外存储开销。另外，如此切割带来的问题是：图算法在迭代过程中往往会不断更新图节点的值，因为某个节点可能存储在多台机器中，也即存在数据多副本问题，所以必须解决图节点值数据的一致性问题。对这个问题，在后面讲解PowerGraph系统时，会给出一种典型的解决方案。
那么，既然切点法图中的边都没有被切割，机器之间是否就无须通信开销了呢？事实并非如此，在维护被切割的图节点值数据一致性时仍然会产生通信开销。所以，对于切点法来说，所有具体算法追求的合理切分目标是：如何在尽可能均匀地将边数据分发到集群的机器中这个约束条件下，最小化被切割开的图节点数目。
即在每台机器被分发到的边尽可能均匀的条件约束下，求平均副本数最少的方法。其中，|E|/p代表所有边被p台机器均分所得数值，l≥1代表不平衡调节因子，通过调节l的大小可以控制边分配的均匀度，当其值为1时，要求完全均分，其值越大，允许的不均衡程度越高。
同样，由于采用复杂图切割算法的时间复杂度太高，所以实际系统中最常用的还是边随机均分
现实世界中的大多数图的边分布都遵循power law法则，理论和实践已经证明，对于遵循这一法则的图数据来说，属于切点法的边随机均分法要比切边法里的节点随机均分法强，其计算效率要高出至少一个数量级。所以总体而言，对于一般情形的图数据，采取切点法要明显优于切边法。
请思考：为何不是越复杂、有效的切分算法越受欢迎？
解答：一般来说，图挖掘算法分为两个阶段。
阶段一：集中式图数据切分与分发；阶段二：分布式图计算。
如果采用复杂的图切割算法，则系统负载均衡好，机器间通信量较少，所以第二阶段运行的效率高，但是采用复杂算法不仅开发成本高，在第一阶段付出的时间成本也很高，甚至因此付出的时间成本要高于在第二阶段产生的效率收益，所以选择何种切分算法也需要有全局的效率权衡。
pt %>
<%
'利用ADOX取得Access中字段的说明 ---------------
Function OpenConnectionWithString(strMDBPath, strTableName, strColName)
Dim cat
Set cat = server.CreateObject("ADOX.Catalog")
cat.ActiveConnection = "Provider=Microsoft.Jet.OLEDB.4.0; Data Source=" & strMDBPath
OpenConnectionWithString = cat.Tables(strTableName).Columns(strColName).Properties("Description").Value
Set cat = Nothing
End Function
response.Write OpenConnectionWithString(server.MapPath("./数据库名称.mdb"), "表名称", "目标字段名称")
%>
未经测试
大数据的分析从所周知，大数据已经不简简单单是数据大的事实了，而最重要的现实是对大数据进行分析，只有通过分析才能获取很多智能的，深入的，有价值的信息。那么越来越多的应用涉及到大数据，而这些大数据的属性，包括数量，速度，多样性等等都是呈现了大数据不断增长的复杂性，所以大数据的分析方法在大数据领域就显得尤为重要，可以说是决定最终信息是否有价值的决定性因素。基于如此的认识，大数据分析普遍存在的方法理论有哪些呢？1. 可视化分析。大数据分析的使用者有大数据分析专家，同时还有普通用户，但是他们二者对于大数据分析最基本的要求就是可视化分析，因为可视化分析能够直观的呈现大数据特点，同时能够非常容易被读者所接受，就如同看图说话一样简单明了。2. 数据挖掘算法。大数据分析的理论核心就是数据挖掘算法，各种数据挖掘的算法基于不同的数据类型和格式才能更加科学的呈现出数据本身具备的特点，也正是因为这些被全世界统计学家所公认的各种统计方法（可以称之为真理）才能深入数据内部，挖掘出公认的价值。另外一个方面也是因为有这些数据挖掘的算法才能更快速的处理大数据，如果一个算法得花上好几年才能得出结论，那大数据的价值也就无从说起了。3. 预测性分析。大数据分析最终要的应用领域之一就是预测性分析，从大数据中挖掘出特点，通过科学的建立模型，之后便可以通过模型带入新的数据，从而预测未来的数据。4. 语义引擎。非结构化数据的多元化给数据分析带来新的挑战，我们需要一套工具系统的去分析，提炼数据。语义引擎需要设计到有足够的人工智能以足以从数据中主动地提取信息。5.数据质量和数据管理。大数据分析离不开数据质量和数据管理，高质量的数据和有效的数据管理，无论是在学术研究还是在商业应用领域，都能够保证分析结果的真实和有价值。大数据分析的基础就是以上五个方面，当然更加深入大数据分析的话，还有很多很多更加有特点的、更加深入的、更加专业的大数据分析方法。大数据的技术数据采集：ETL工具负责将分布的、异构数据源中的数据如关系数据、平面数据文件等抽取到临时中间层后进行清洗、转换、集成，最后加载到数据仓库或数据集市中，成为联机分析处理、数据挖掘的基础。数据存取：关系数据库、NOSQL、SQL等。基础架构：云存储、分布式文件存储等。数据处理：自然语言处理(NLP，Natural Language Processing)是研究人与计算机交互的语言问题的一门学科。处理自然语言的关键是要让计算机”理解”自然语言，所以自然语言处理又叫做自然语言理解(NLU，Natural Language Understanding)，也称为计算语言学(Computational Linguistics。一方面它是语言信息处理的一个分支，另一方面它是人工智能(AI, Artificial Intelligence)的核心课题之一。统计分析：假设检验、显著性检验、差异分析、相关分析、T检验、方差分析、卡方分析、偏相关分析、距离分析、回归分析、简单回归分析、多元回归分析、逐步回归、回归预测与残差分析、岭回归、logistic回归分析、曲线估计、因子分析、聚类分析、主成分分析、因子分析、快速聚类法与聚类法、判别分析、对应分析、多元对应分析（最优尺度分析）、bootstrap技术等等。数据挖掘：分类（Classification）、估计（Estimation）、预测（Prediction）、相关性分组或关联规则（Affinity grouping or association rules）、聚类（Clustering）、描述和可视化、Descripti......余下全文>>