为博客生成标签图

本贴最后更新于 3536 天前,其中的信息可能已经事过境迁

图是由节点和边组成的。下图是一个 6 节点无向完全图:

无向完全图

边权重

可以把权重是看成是边的属性,可视化时这个属性决定了边的“粗细”,权重大的边粗一些:

边带权重的无向完全图

节点度

度就是和节点相连的边的数目。例如上图中,每个节点的度都为 5。我们可以把节点度看成是节点的属性,可视化时这个属性决定了节点的“大小”,度大的节点看上去要大一些:

节点度

标签图

好了,上面我们简单介绍了图的概念,接下来我们就开始实战吧:为博客生成标签图!标签图反映了博主文章涉猎的范围偏好、以及这些标签之间的相关性

标签数据

要生成标签图,我们需要先准备好基础数据。这些数据就是标签,准确地说是每篇文章的标签:

[
    [   
        "一篇文章的标签",
        "弱类型",
        "Latke",
        "B3log Latke",
        "Java",
        "ORM",
        "JSON",
"Open Source" ], [ "另一篇文章的标签", "Open Source", "NetBeans", "JSF", "PrimeFaces", "JDK 8", "Java" ] ]

这个 JSON 数组很容易就能生成,保存为 data.json 文件。

生成算法

我们把标签作为节点,现在要做的就是把这些节点连起来。节点之间是否存在边,是通过边权重计算得出的:如果权重大于某个常量参数,则认为这两个节点连通,所以现在的重点就是边权重的计算。

边权重值是两个标签同时出现在同一篇文章标签中的次数

 比如上面的 data.json 中,Java 和 Open Source 同时出现了两次,那它们之间的边权重就是 2。下面我们简单描述以下算法并给出核心代码:

1. 从 data.json 中读取所有标签,去重复,放到 tagList 中
2. 遍历 tagList,取出两个标签来计算它们之间的边权重

for (int i = 0; i < tagList.size(); i++) {
    final String tag1 = tagList.get(i);
for (int j = i + 1; j &lt; tagList.size(); j++) {
    final String tag2 = tagList.get(j);

    int originalWeight = getWeight(tag1, tag2, tagsArray);

    if (originalWeight &gt; WEIGHT) {
        int weight = (int) Math.floor(originalWeight / SCALE);
        if (weight &gt; 1) {
            // 生成 tag1 和 tag2 带权重的边
            // ....
        }
    }
}

}

private static int getWeight(final String tag1, final String tag2, final JSONArray tagsArray) {
int ret = 0;

for (int i = 0; i &lt; tagsArray.length(); i++) {
    // 一篇文章的标签数组
    final JSONArray tagArray = tagsArray.getJSONArray(i);

    // 转成集合
    final Set&lt;String&gt; tagSet = new HashSet&lt;&gt;();
    for (int j = 0; j &lt; tagArray.length(); j++) {
        final String tag = tagArray.getString(j);
        tagSet.add(tag);
    }

    // 如果这篇文章同时出现了 tag1 和 tag2,则权重加 1
    if (tagSet.contains(tag1) &amp;&amp; tagSet.contains(tag2)) {
        ret++;
    }
}

return ret;

}

 这个 naive algorithm 效率很低,不过因为博客标签数据量不大,实际跑下来还能接受(300+ 标签,耗时 20s+)。

可视化

JSNetworkX

JSNetworkXNetworkX 的 JavaScript 版本,目前已经实现了很多常用算法和特性,基于 D3.js。

基本用法请参考这里,前面我们已经生成了带权重的边,而节点度则是放在这里处理的(因为 JSNetworkX 可以方便的计算节点度),文末给出完整代码。

参数

前面我们提到过边权重参数,这个参数是为了控制生成边的数目(权重大的边才有必要进行绘制),否则生成的图可能会是下面这个样子:

杂乱的标签图 

目前我的参数是调整为:WEIGHT = 12SCALE = 10(具体参数含义请参考源代码),效果如下:

我的博客

(实际效果在这里

完整代码

  • Tag
    1 引用 • 1 回帖
  • Graph
    1 引用 • 1 回帖
  • Algorithm
    1 引用 • 1 回帖
  • D3.js
    3 引用 • 4 回帖
  • JSNetworkX
    1 引用 • 1 回帖
  • JavaScript

    JavaScript 一种动态类型、弱类型、基于原型的直译式脚本语言,内置支持类型。它的解释器被称为 JavaScript 引擎,为浏览器的一部分,广泛用于客户端的脚本语言,最早是在 HTML 网页上使用,用来给 HTML 网页增加动态功能。

    710 引用 • 1173 回帖 • 193 关注

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...