R语言股市可视化相关矩阵:最小生成树

本文在股市可视化中可视化相关矩阵 :最小生成树

由Kaizong Ye,Sherry Deng撰写

在本文示例中,我将使用日数据和1分钟数据来可视化股票数据 。

我发现以下概念定义非常有用:

×

与Prim算法贪心选择不同,Kruskal算法采取每次选择权值最小的边的方法,这样,在不构成环且最后能够连接完所有边它们的权重和一定是最小的。

和之前Prim算法的图一样,便于区别二者。

Kruskal既然是选择最小的边,那么就先找一个最小的出来,是1-6(10)

然后继续找出剩下的边中最小一条边,是3-4(12)

继续找一条最小的出来,2-7(14)

在来,为了区别已经选择的点,我把点的颜色也做个标记,有颜色的表示为已经加入生成树的点

喔,忘了把最小的边2-3(16)选了

现在图变成了这样,(依旧难看)…….

还没找完,继续找最小的边..是7-4(18)

你会发现我把这条边用蓝色标记了,是不是我为了好玩??当然不是了,这条边是有问题的。

这条边虽然是上一次选择完后剩下的边中最短的,但是,它的左右两个点已经是最小生成树的结点了,而把这条边加入后,构成了右边的一个大大的环。这样显然不是最小生成树了.

再复习下,生成树:一个连通图的生成树,是一个极小连通子图,其中包含图的所有结点,和构成一棵数的(n-1)条边。如果在一棵生成树的两个结点上添加任意一边,必定构成一个环。

最小生成树:图的所有生成树中所有边的权值和最小的那个生成树。

所以,有环的连生成树都不是了,怎么会是最小生成树。。

所以,这条边7-4(18)丢掉丢掉,重新选择。选择5-4(22)

好像图中所有的点都有颜色了,但是还没完全好,因为它们还不是一条绳上的蚂蚱,

继续选,最短的是6-5(25)

继续选 ,唉,不对,选了24发现又有环了,选28也构成环了。。。。在仔细一看,最小生成树已经生成了

这个就是Kruskal算法的流程。




  • 连通图:在无向图中,若任意两个顶点vivi与vjvj都有路径相通,则称该无向图为连通图。
  • 强连通图:在有向图中,若任意两个顶点vivi与vjvj都有路径相通,则称该有向图为强连通图。
  • 连通网:在连通图中,若图的边具有一定的意义,每一条边都对应着一个数,称为权;权代表着连接连个顶点的代价,称这种连通图叫做连通网。

  • 生成树:一个连通图的生成树是指一个连通子图,它含有图中全部n个顶点,但只有足以构成一棵树的n-1条边。一颗有n个顶点的生成树有且仅有n-1条边,如果生成树中再添加一条边,则必定成环。
  • 最小生成树:在连通网的所有生成树中,所有边的代价和最小的生成树,称为最小生成树。

热门课程

R语言数据分析挖掘必知必会

面对扑面而来的数据浪潮,包含Google、Facebook等国际企业,都已采用R语言进行数据分析

探索课程


接下来,让我们获取1分钟的收盘价数据,并基于最近5天可视化相关性:

辅助功能:


可下载资源

关于作者

Kaizong Ye拓端研究室(TRL)的研究员。

本文借鉴了作者最近为《R语言数据分析挖掘必知必会 》课堂做的准备。

​非常感谢您阅读本文,如需帮助请联系我们!

 
QQ在线咨询
售前咨询热线
15121130882
售后咨询热线
0571-63341498