大数据结构分析模型.pptx
,大数据分析原理与实践6、结构分析模型,什么是结构分析？,结构分析即发现数据中的结构。其输入是数据，输出是数据中某种有规律的结构。,Dijkstra 算法,问题：求解某个顶点到图中所有其他点的最短路径。如图，求 0 到 1,2,3,4 的最短距离。也称单源最短路径。,Dijkstra 算法,思想：设点集S存放着已找到最短路径的顶点，数组D中保存着 0 到 1,2,3,4 已知的最小距离。初始值 S=0，D=5,13,3,。,思想：每次加入一个点，并进行相应的修改。,Dijkstra 算法,思想：在S中加入点 1，则有于是 S=0,1，=5,11,3,。同理，依次加入其余点，最后的数组d即为 0 到其他点的最短路径。,思想：每次加入一个点，并进行相应的修改。,Dijkstra 算法,思想：算法的时间复杂度为(2)，其中n为图中点的个数。同理，也可以考虑将每次加入一条边，即为Bellman-Ford算法，时间复杂度为，其中k为边的个数。若需要输出最小距离对应的路径，则需记录每次下式成立时，j和k的值,思想：每次加入一个点，并进行相应的修改。,Floyd 算法,问题：求解图中所有其他顶点之间的最短路径。如图，求 0,1,2,3,4 这5个顶点间的最短距离。,Floyd 算法,思想：直观上，我们可以使用n次Dijkstra算法，求得每个点到其他点的最小距离，时间复杂度为(3)。而Floyd算法的时间复杂度也为(3)，但其过程简单的多，主要表现在输出最小距离对应的路径上。,思想：使用一个矩阵维护路径信息。,PageRank算法,毫无疑问：PageRank算法是链接排名中最重要也最负盛名的算法。,PageRank算法,一点历史：PageRank与GooglePageRank算法，在1996年，由google创始人佩奇和布林发明。这项技术在1998年前后使得搜索的相关性有了质的飞跃，圆满地解决了以往网页搜索结果中排序不好的问题。,PageRank算法,思想：“民主表决”在互联网上，如果一个网页被很多其他网页所链接，说明它受到普遍的承认和信赖，那么它的排名就高。,PageRank算法,思想：“民主表决”正如在现实生活中股东大会里的表决，每个股东的表决权的是取决于它们所持有的股份。而网页的网页排名，在于链接它的网页的网页排名。网页Y的网页排名 PageRank(y)=0.001+0.01+0.02+0.05=0.081,PageRank算法,思想：“民主表决”那么如何事先知道网页X1的重要程度呢？对所有网页假设一个初值，算出第一次迭代排名，然后根据第一次迭代排名，算出第二次迭代排名。经过足够多次的迭代之后，估计值将收敛到真实值。,PageRank算法,具体来说：矩阵相乘假定向量B为N个网页的网页排名。矩阵A为网页之间链接的数目，其中amn代表第m个网页指向第n个网页的链接数。在这里，A是已知的，B是我们所要计算的。,PageRank算法,具体来说：矩阵相乘假定 Bi 是第 i 次的迭代结果，那么=1 初始假设：所有网页的排名都是1/N，即 0=(1,1,1)经过多次迭代，Bi 最终会收敛到B，此时=一般只需10次迭代基本上就收敛了。,PageRank算法,更多：平滑处理及MapReduce平滑处理：网页之间链接的数量相比互联网的规模非常稀疏，使用一个小常数 进行平滑处理=+1 1 MapReduce：早期的PageRank计算的并行化是半手工、半自动的。2003年，谷歌的工程师发明了MapReduce，使得PageRank的计算完全自动化了。,什么是结构计数结构计数是对图中具有某种特定结构的结构进行计数。比较经典的结构计数有三角形结构计数，即输入图G，输出其中的三角形。,什么是结构聚类结构聚类指的是对一个图中的节点和边进行聚类。对于节点聚类来说，输入图G，输出其节点的分类，使得每个分类在结构上关联密切。,维基百科的定义社团是一个或一组网站，是虚拟的社团；虚拟的社团是指有着共同爱好和目标的人通过媒体相互影响的社交网络平台；在这个平台上，潜在地跨越了地理和政治的边界。基于主题的定义社团是由一群有着共同兴趣的个人，和备受他们欢迎的网页组成。也有人给出的定义为社团是在图中共享相同属性的的顶点的集群，这些顶点在图中扮演着十分相似的角色。比如，处理相关话题的一组网页可以视为一个社团。基于主题及结构的定义社团定义为图中所有顶点构成的全集的一个子集，它满足子集内部顶点之间连接紧密，而子集内部顶点与子集外部的其他顶点连接不够紧密的要求。,社团发现,按主题分类可以分为明显的(explicit)社团和隐含的(implicit)社团。顾名思义，明显的社团是与某些经典的、流行的、大众的主题相关的一组网页。比如大家熟知的Facebook,IMDB,YouTube,Amazon,Flickr等等，它们的特点是易定义、易发现、易评价。与之相反的隐含社团则是与某些潜在的、特殊的、小众的主题相关的一组网页，比如是讨论算法、数据库的网页集合，它们的特点是难定义，难发现，难评价。按社团形成机制分类可以分成预定义社团和自组织社团。预定义社团指预先定义好的社团，比如LinkedIn,Google Group,Facebook等等。相反自组织社团指自组织形成的社团，比如有关钓鱼岛事件的一组网页。,社团发现,社团的用途社团的用途的用途十分广泛，它能帮助搜索引擎提供更好的搜索服务，如基于特定主题的搜索服务，以及为用户提供针对性的相关网页等等。它也在主题爬虫(Focused crawling)的应用中发挥重要作用。它还能够用于研究社团与知识的演变过程。,社团发现,团(clique)一组顶点，其中任意两个顶点之间有一条边相连。例如1,2,3和2,3,4是团。,社团发现,T-准团(quasi-clique)一组顶点S，其导出子图的密度大于等于t。导出子图密度=导出子图边数|S|(|S|-1)/2，其中|S|表示顶点集合S中顶点的个数，下面其他定义中的|S|也是同样的含义。例如1,2,3,4是一个0.8-准团。p-准团(quasi-clique)一组顶点S，其中每个顶点与S中至少p(|S|-1)个其他顶点相邻。例如1,2,3,4是一个0.6-准团。,k-核(core)一组顶点S，其中每个顶点与S中至少k个其他顶点相邻。例如1,2,3,4,5,6,7是一个2-核。,社团发现,k-plex一组顶点S，其中每个顶点与S中至少|S|-k个其他顶点相邻。例如1,2,3,4是一个2-plex。kd-团(clique)一组顶点S，其中任意两个顶点之间的最短路径（不能经过S以外的顶点）长度小于等于k。例如1,2,3,4,5是一个2d-团。,k-club一组顶点S，其中任意两个顶点之间的最短路径（可经过S以外的顶点）长度小于等于k。例如1,2,3,4,5,6是一个2d-团。(s,t)-biclique一组顶点ST，S中任意顶点与T中任意顶点都有边相连，S中顶点之间互不相邻，T中顶点之间也互不相邻，|S|=s，|T|=t。,社团发现,上面给出了社团的绝对定义，下面介绍社团的相对定义包括强定义形式、弱定义形式以及中间定义形式三种。强定义形式要求S中任意顶点v与S中其他顶点之间的边数大于v与S以外顶点之间的边数。如图所示，根据定义，红色的节点不属于任何的社团。,社团发现,弱定义形式要求S中顶点之间的边数大于等于S中顶点与S以外顶点之间的边数。如图所示，红色结点属于虚线框内的社团，尽管它们的出度大于入度。中间定义形式要求S中任意顶点v与S中其他顶点之间的边数大于等于v与任意其他社团内顶点之间的边数。,社团发现,谢谢！,Thanks for your attention!,
