为博客生成标签图

  |   0 评论   |   5,261 浏览

图是由节点和边组成的。下图是一个 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 < tagList.size(); j++) {
        final String tag2 = tagList.get(j);

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

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

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

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

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

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

    return ret;
}

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

可视化

JSNetworkX

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

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

参数

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

杂乱的标签图 

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

我的博客

(实际效果在这里

完整代码

---- EOF ----
点击加入开源技术 Q 群 242561391,让学习和分享成为一种习惯!

评论

发表评论

validate