雅乐网

计算机技术、学习成长

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

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

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));
    }

我要评论

验证码*: 9 + 2 =