雅乐网

计算机技术、学习成长

数学 » 社团检测 » 重叠社区发现评估指标：标准化互信息NMI计算步骤和C++代码（Normalized Mutual Information）

重叠社区发现评估指标：标准化互信息NMI计算步骤和C++代码（Normalized Mutual Information）

最后修改于 2019-05-12 发表于 2017-05-20 14,497 views 3

社团检测

NMI的英文全称是Normalized Mutual Information，中文叫做标准化互信息，它可以用来衡量两种聚类结果的相似度。

本文介绍适用于重叠聚类的NMI计算步骤，重叠指的是，一个节点可以属于多个类别。

假设一个图中的真实社团如下所示：

注意上面3和4同时属于社团1和社团2，这就是重叠的含义。

而我们的一个重叠的社团检测算法，得到的结果如下所示：

要来比较算法的结果和真实的结果有多大的相似性，就可以使用NMI指标来评估。

参考论文：Detecting the overlapping and hierarchical community structure in complex networks

下面的步骤中两种划分方式对应上面的两个文件。

可运行的示例代码下载：NMI.cpp

C++接口

NMI的两个参数是两种社区划分方案，可以使用 <vector<vector<int>> 来表示，函数接口如下：

X和Y是两种划分，X[0]是X中第1个社团包含的结点向量，X[1]是X中第2个社团包含的结点向量。

如果有一个划分为空，则返回0。

下面使用Xi和Yj表示两种划分中的某个社团。

求两种划分中的结点个数

后面要用到参与聚类的结点个数，也就是求 X 和 Y中所有元素的个数。使用遍历所有元素加进set的方式，在结点编号不连续时也可以正常工作。

为了函数传入参数的简洁，使用全局变量double g_nodes_num记录结点个数。

信息熵 H(Xi)

这里的Xi指的是划分中的一个社团，也就是一个vector<int> ，它的信息熵怎么求呢？

Xi的形式是这样的 [1 2 3 4]表示结点1,2,3,4一共4个结点属于该社团。由于例子中共有9个不重复结点，自然有9-4=5个结点不属于该社团。

把Xi看做随机变量，它表示的是节点属于该社团。Xi=1表示结点属于该社团，Xi=0表示结点不属于该社团，那么根据上面实际属于该社团的结点个数，可以得到Xi的概率分布：

P(Xi = 1) = 4 / 9

P(Xi = 0) = 1 – P(Xi)

根据信息熵的定义

$$h(x) = – x * log(x) $$

$$H(X) = \sum_i h(P(X = X_i))$$

可以得到

$$H(X_i) = h(P(Xi = 1)) + h(P(Xi = 0))$$

从公式可以看出，一个社团的信息熵，只和这个社团的结点数目以及总结点个数有关。准确的说，是和社团中结点个数占总数的比例有关，而与具体哪个结点没有关系。设这个比例为x，则H(Xi)的函数为

$$f(x) = -x * log(x) – (1-x) * log(1-x)$$

这个函数的图像如下；

可见，一个社团的信息熵，从0开始随着结点数目的增加而增加，增加到一半结点时达到最大值1，最后随着结点增加减小至0 。

从上面的函数图象可以看出H(Xi)这个函数是关于0.5对称的，也就是说，一个社团有 x 个结点和有 (n-x)个结点，他们的信息熵相等

代码如下

联合熵 H(Xi,Yj)

Xi和Yj分别是一个社团，把Xi和Yj看做多维随机变量，它们的取值就有4种情况：

Xi=1, Yj=1 ，表示结点同时属于这两个社团。那实际中的结点个数就是 Xi 和 Yj 的交集的元素个数。

Xi=0, Yj=1， 表示结点属于社团Xi，但不属于社团Yj。 这样的结点个数是 Xi 和 Yj 的差集的元素个数。

Xi=0, Yj=1， 表示结点属于社团Xi，但不属于社团Yj。 这样的结点个数是 Yj 和 Xi 的差集的元素个数。

Xi=0, Yj=0，表示结点既不属于社团Xi，也不属于社团Yj。这样的结点个数是 总结点个数 – 上面三种情况的结点个数。

这些结点个数 除以 总结点个数，就可以得到这四种情况的概率值：P00,P01,P10,P11。

应用信息熵的公式，得到

$$H(X_i, Y_j) = h(P(Xi=1, Yj=1)) + h(p(Xi=0, Yj=1)) + h(p(Xi=1, Yj=0)) + h(p(Xi=0, Yj=0))$$

之所以求这个是为了下面求条件熵方便。看一个特殊情况，当Xi和Yj是完全一致的时候，一个节点要么同时属于X和Y，要么同时不属于X和Y，此时p(Xi=0, Yj=1)和p(Xi=1， Yj=0)的值都是0，也就是

$$H(X_i, Y_j) = h(P(Xi=1, Yj=1)) + h(p(Xi=0, Yj=0)) = H(X_i) = H(Y_j)，当X_i和Y_j一致时$$

有一个意外的情况出现了，当X和Y两个社团互补的时候，也就是X和Y没有公共元素，但他们的并集组成全集，此时 同时属于X和Y 或者 同时不属于X和Y 的结点数是0，公式中第1项和第4项是0，由于H(Xi)的对称性，这同样导致

$$H(X_i, Y_j) = h(P(Xi=1, Yj=0)) + h(p(Xi=0, Yj=1)) = H(X_i) = H(Y_j)，当X_i和Y_j互补时$$

在其他情况下，由于P00,P01,P10,P11四个相加之和为1，H(Xi, Yj) 会小于H(Xi)和H(Yj)

条件熵H(Xi|Yj)

两个社团的条件熵公式

$$H(X_i|Y_j) = H(X_i, Y_j) – H(Y_j)$$

这个表示的是社团Xi和Yj的差异程度。当Xi和Yj完全相同的时候，H(X_i, Y_j) = H(Y_j)，此时H(X_i|Y_j) = 0 ；而Xi和Yj有区别的时候，这个值就会大于0

意外情况是，Xi和Yj互补的时候，H(X_i|Y_j) = 0也成立，这是我们不愿意看到的。因此这里设置一个变通：

当

$$h(P00)+h(P11) \ge h(P01)+h(P10)$$

的时候

$$H(X_i|Y_j) = H(X_i, Y_j) – H(Y_j)，when h(P00)+h(P11) \ge h(P01)+h(P10)$$

而条件不满足时，也就意味着同时属于或不属于Xi和Yj的结点数要小于 仅在一个社团的结点数目，也就是两个社团有互补的趋势，由于上面的讨论，趋近互补时，H(X_i, Y_j)会趋近H(Yj)导致这个值也趋近0，然而两个社团互补我们认为他们非常不相似，这时定义

$$H(X_i|Y_j) = H(X_i)，when h(P00)+h(P11) < h(P01)+h(P10) $$

由于我们的代码中P00，P01这些变量计算是在H_Xi_joint_Yj函数中，我们修改了这个函数使本节函数符合上面的两种情况

条件熵 H(Xi|Y)

H(Xi|Y) = min{H(Xi|Yj)} for all j ，也就是从Y中找出一个和Xi匹配最好的条件熵的值

标准条件熵H(Xi|Y)_norm

标准的意思就是把它变成取值0-1之间，公式为

$$H(X_i|Y)_{norm} =\frac{ H(X_i|Y) }{ H(X_i)}$

条件熵H(X|Y)

这个就是遍历X中的所有Xi，把 H(X_i|Y) 相加

条件熵H(X|Y)_norm

这个就是遍历X中的所有Xi，假设有k个，把H(X_i|Y)_norm相加，然后除以k

$$H(X|Y)_{norm} = \frac{1}{k} \sum_i^k  H(X_i|Y)_{norm}$

NMI_LFK

有了上面的准备工作，我们终于可以轻松的根据公式

$$NMI(X,Y) = 1 – \frac{1}{2} [H(X|Y)_{norm} + H(Y|X)_{norm}]$$

写出计算NMI的代码啦

从公式也可以看出，NMI的计算对应X和Y的顺序没有关系，也就是NMI(X,Y) = NMI(Y,X)

这个NMI的计算是Andrea Lancichinetti, Santo Fortunato and János Kertész三个人在论文论文：Detecting the overlapping and hierarchical community structure in complex networks 中提出的，因此可以记为NMI_LFK

改进的NMI

论文 Normalized Mutual Information to evaluate overlapping community finding algorithms 对LFk提出的NMI提出了改进：

论文指出，LFK提出的NMI计算方法，在一些特殊情况表现不佳：

情况一：

若 X包含很多社团，而Y仅仅包含一个社团，Y中仅有的一个社团和X中的某个社团完全一致。根据直觉，这两种划分方式应该很不一样。X中若包含k个社团，Y中仅有一个社团和X中的某个社团一致，根据直觉NMI值应该大约为 1/k

但在LFK的NMI计算中

$$NMI_{LFK}(X,Y) = 1 – \frac{1}{2} [H(X|Y)_{norm} + H(Y|X)_{norm}]$$

H(Y|X) 这个的值是0，这导致NMI_LFK的值会大于0.5

情况二：

Y中包含了所有可能的社团组合。此时会有 H(X|Y)=0 ,NMI_LFK的值也会大于0.5

H(X)

这个是所有的H(Xi)相加。

互信息I(X:Y)

$$I(X:Y) = \frac{1}{2} ( H(X) + H(Y) – H(X|Y) – H(Y|X) )$

NMI_max

$$NMI_{max} = \frac{I(X:Y)}{max ( (H(X), H(Y) )}$

 

如果文章对你有帮助，欢迎点赞或打赏（金额不限）。你的打赏将全部用于支付网站服务器费用和提高网站文章质量，谢谢支持。

版权声明:

本文由 原创，商业转载请联系作者获得授权。
非商业转载请注明作者 或 雅乐网 ，并附带本文链接：
http://www.yalewoo.com/nmi_normalized_mutual_information_of_overlapping_community_detection.html

上一篇：

下一篇：

与 相关的文章

文章《重叠社区发现评估指标：标准化互信息NMI计算步骤和C++代码（Normalized Mutual Information）》共有3条评论：

  1. 常振海

    大侠您好，我按照您的程序顺序连接，建立了一个.cpp文件，想用来计算overlapping时的NMI,但在执行时遇到下面的问题：fatal error C1004: 发现意外的文件尾，不知该怎样进行调整 ？请您指教！ 谢谢！
    #include
    #ifndef _INC_MATH
    #define _INC_MATH
    #include
    #include
    using namespace std;
    double NMI(vector<vector > & X, vector<vector > & Y)
    {
    if (X.size() == 0 || Y.size() == 0)
    return 0;
    }

    //返回X和Y中不重复元素个数
    int getNodesNum(vector<vector > & X, vector<vector > & Y)
    {
    set s;
    for (size_t i = 0; i < X.size(); ++i)
    {
    for (size_t j = 0; j < X[i].size(); ++j)
    s.insert(X[i][j]);
    }
    for (size_t i = 0; i < Y.size(); ++i)
    {
    for (size_t j = 0; j < Y[i].size(); ++j)
    s.insert(Y[i][j]);
    }
    return s.size();
    }

    double g_nodes_num;
    double NMI(vector<vector > & X, vector<vector > & Y)
    {
    if (X.size() == 0 || Y.size() == 0)
    return 0;
    g_nodes_num = getNodesNum(X, Y);

    } //为了函数传入参数的简洁，使用全局变量double g_nodes_num记录结点个数

    //entropy
    double log2(double x)
    {
    return log(x) / log(2);
    }
    double h(double x)
    {
    if (x > 0)
    return -1 * x * log2(x);
    else
    return 0;
    }
    double H(vector & Xi)
    {
    double p1 = Xi.size() / g_nodes_num;
    double p0 = 1 – p1;
    return h(p0) + h(p1);
    }

    //返回a和b的交集
    vector intersection(vector& a, vector& b)
    {
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    vector res(max(a.size(), b.size()));
    auto iter = std::set_intersection(a.begin(), a.end(), b.begin(), b.end(), res.begin());
    res.resize(iter – res.begin());

    return res;
    }
    //返回a和b的差集
    vector difference(vector& a, vector& b)
    {
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    vector res(max(a.size(), b.size()));
    auto iter = std::set_difference(a.begin(), a.end(), b.begin(), b.end(), res.begin());
    res.resize(iter – res.begin());

    return res;
    }

    //H(Xi, Yj)
    double H_Xi_joint_Yj(vector & Xi, vector & Yj)
    {
    double P11 = intersection(Xi, Yj).size() / g_nodes_num;
    double P10 = difference(Xi, Yj).size() / g_nodes_num;
    double P01 = difference(Yj, Xi).size() / g_nodes_num;
    double P00 = 1 – P11 – P10 – P01;
    return h(P11) + h(P10) + h(P01) + h(P00);
    }
    //H(Xi, Yj)
    double H_Xi_joint_Yj(vector & Xi, vector & Yj)
    {
    double P11 = intersection(Xi, Yj).size() / g_nodes_num;
    double P10 = difference(Xi, Yj).size() / g_nodes_num;
    double P01 = difference(Yj, Xi).size() / g_nodes_num;
    double P00 = 1 – P11 – P10 – P01;

    if (h(P11) + h(P00) >= h(P01) + h(P10))
    return h(P11) + h(P10) + h(P01) + h(P00);
    else
    return H(Xi) + H(Yj); //求条件熵时再减去H(Yj)正好是H(Xi)
    }

    //H(Xi|Yj)
    double H_Xi_given_Yj(vector & Xi, vector & Yj)
    {
    return H_Xi_joint_Yj(Xi, Yj) – H(Yj);
    }

    //H(Xi|Y) return min{H(Xi|Yj)} for all j
    double H_Xi_given_Y(vector & Xi, vector<vector > & Y)
    {
    double res = H_Xi_given_Yj(Xi, Y[0]);
    for (size_t i = 1; i < Y.size(); ++i)
    {
    res = min(res, H_Xi_given_Yj(Xi, Y[i]));
    }
    return res;
    }

    //H(Xi|Y)_norm
    double H_Xi_given_Y_norm(vector & Xi, vector<vector > & Y)
    {
    return H_Xi_given_Y(Xi, Y) / H(Xi);
    }

    //H(X|Y) = sum {H(Xi|Y)}
    double H_X_given_Y(vector<vector > & X, vector<vector > & Y)
    {
    double res = 0;
    for (size_t i = 0; i < X.size(); ++i)
    {
    res += H_Xi_given_Y(X[i], Y);
    }

    return res;
    }

    //H(X|Y)_norm
    double H_X_given_Y_norm(vector<vector > & X, vector<vector > & Y)
    {
    double res = 0;
    for (size_t i = 0; i < X.size(); ++i)
    {
    res += H_Xi_given_Y_norm(X[i], Y);
    }

    return res / X.size();
    }

    //计算NMI
    double NMI(vector<vector > & X, vector<vector > & Y)
    {
    if (X.size() == 0 || Y.size() == 0)
    return 0;
    g_nodes_num = getNodesNum(X, Y);

    return 1 – 0.5 * (H_X_given_Y_norm(X, Y) + H_X_given_Y_norm(Y, X));
    }

    //改进的NMI
    //H(X)
    double H(vector<vector > & X)
    {
    double res = 0;
    for (size_t i = 0; i < X.size(); ++i)
    {
    res += H(X[i]);
    }
    return res;
    }

    //I(X:Y)
    double I(vector<vector > & X, vector<vector > & Y)
    {
    return 0.5 * (H(X) + H(Y) – H_X_given_Y(X, Y) – H_X_given_Y(Y, X));
    }

    //计算改进的NMI
    double NMI_max(vector<vector > & X, vector<vector > & Y)
    {
    return I(X,Y) / max(H(X), H(Y));
    }

    回复

我要评论

验证码*： 8 + 0 =