|||
5.1 信息熵基本概念
信息论的创始人申农(Claude Shannon)[7]1948年引入了一个重要概念:信息熵,用来描述信息传播不确定性。信息论指出,如果一个事件有n个可能结局,那么结局未出现前的不确定程度 h 与 n 的对数成正比。关于信息论的中文介绍,参见科学网博客文章[8]等,读者可从这通俗易懂的描述里了解基本概念。
假设样本空间 (sample space) X 有 n 个基本事件 (events),基本事件 xj 的概率為 pj, j=1, 2, …, n, ∑ pj = 1。申农的信息理论可给出度量事件发生不确定性的信息熵函数,亦称负熵函数:
h (p1, p2, ..., pn)
= ∑ - pj Log2 (pj), j = 1, ..., n,
(1)
式中,Log2 为以2为底的对数。
例如,有一枚硬币,头像的那面称为正面,另一面称为反面。如果投币看其结果是正面还是反面,这是一个不确定事件。在正反面朝上的概率各为一半时,不确定性最大,信息熵为1。若有人将硬币改装,使正面出现的概率固定为1,反面出现的 概率固定为0,此时投硬币不确定性最小,信息熵为0。 同样,如果正面出现的概率固定为0,反面出现的概率固定为1,此时投硬币不确定性亦为最小,信息熵为0。图三表示投掷硬币不确定性的信息熵分布曲线。
图三 投掷硬币的不确定性:信息熵分布曲线
在申农的信息理论具体应用方面, 1988年笔者使用信息熵表达复杂系统结构有序度,并提出相应算法[9],国内不少同仁也有相应的研究成果,恕不一一列举。2011年笔者团队推出网熵指数(W-entropy
Index)模型和系统来评价社交网络成员影响力[10]。本文试图使用信息熵来反映各搜索引擎网页评级的差异,提出网熵分级方法。
5.2 网熵分级模型
假设某网站的网页评级用 Pj 表示, j = 1, …, n,共有 n 个搜索引擎参与评级。 表达各搜索引擎重要程度的权重集合为:{ a1, a2, ..., an},∑ aj = 1。由此,该网站的平均分级为:
MP = ∑ aj Pj,j = 1, ...,
n,
(2)
如果把各搜索引擎网页分级的差异理解为信息传递的分布现象,信息熵可以用来衡量这种不均匀特性,综合网页分级的负熵修正系数由此而来。
在使用信息熵计算公式之前,应先将 Pj 进行相应转换, pj = Pj /10, 有集合{p1, p2, ..., pn}。
m = ∑ aj pj ,j = 1, ... n, (3)
令 qj = pj / (n+1) , q1, q2, ..., qn, 表示该网站的某搜索引擎评级 pj 的已发生信息传递的指标,q n+1 表示未发生信息传递的指标之和,则有: q n+1 = 1 - ∑ qj, j = 1, ..., n; 以及∑ qj = 1, j = 1, ..., n+1。如果某网站的各搜索引擎分级均为最大值10,有 ∑ qj = 1, j = 1, ..., n;和q n+1 = 0。可定义网站分级分布修正系数为:
h (q1, q2, ..., qn, qn+1) = ∑ - qj Logn+1 (qj), j = 1, ..., n+1, (4)
式中,Logn+1 为以n+1为底的对数。h值介于[0,1]之间。
由(3)和(4)式,网站的绝对网熵分级定义为:
W-entropy rank = h * m
(5)
以网熵分级的最大值为基数,得出相对网熵分级为(6)式。
RW-entropy rank = W-entropy rank / W-entropy rankmax (6)
为表达方便,式(6)乘以100, 其值介于[0,100]。简单起见,称相对网熵分级为网熵分级。用户可根据需要,采用百位制,或采用十位制。可保留两位小数,也可不保留。本文暂时采用百位制,并保留两位小数。
5.3 网熵分级特性验证
网站分级分布修正系数,即(4)式信息熵 h,应具备以下特性:当各搜索引擎对网站分级均为10,说明各搜索引擎对此网站的评级高且信息均匀分布,平均分级 MP 亦为10, m = 1,修正系数 h = 1。 如果各搜索引擎对网站分级均为0,说明此网站评级低且信息不均匀分布,平均分级 MP 亦为0, m =0,修正系数 h = 0。网站的平均分级MP值域为[0, 10],m
值域为[0, 1],分级分布修正系 h 数值域为[0, 1] 。
为了验证网页分级分布修正系数 h 的有效性和普适性,下面设计六组数据, n=3,来观察其的分布变化情况[11]。
第一组:p1 [0, 0.1, 0.2, ...,
1],p2
[0, 0, 0, ..., 0] , p3 [0, 0, 0,
..., 0]
第二组:p1
[1, 1, 1, ..., 1], p2 [0,
0.1, 0.2, ..., 1],p3 [0, 0, 0, ..., 0]
第三组:p1
[1, 1, 1, ..., 1], p2 [1, 1,
1, ..., 1],
p3 [0, 0.1, 0.2, ..., 1]
第四组:p1
[1, 0.9, 0.8, ..., 0],p2 [1, 1, 1, ..., 1],
p3 [1, 1, 1, ..., 1]
第五组:p1
[0, 0, 0, ..., 0], p2 [1,
0.9, 0.8, ..., 0],p3 [1, 1, 1, ..., 1]
第六组:p1
[0, 0, 0, ..., 0], p2 [0, 0,
0, ..., 0] ,
p3 [1, 0.9, 0.8, ..., 0]
由此可见,在前三组数据,诸网页分级平均统计值m的分布为[0, 1],修正系数h的分布也应为[0, 1]。在后三组数据,平均统计值m的分布为[1, 0],分布修正系数h的分布也应为[1, 0]。h * m数和网熵分级应是以相同趋势分布。表15列出若干数据的各项指标演变情况,图四是此六组数据m 和h 、m 和h* m的分布情况。
图四 六组数据h*m 和h 的分布情况,m为横轴
结合图4,观察表15第3行和第11行,m值均为0.3333,尽管{p1, p2, p3}值的分布不一样,但由于h的对称性,其值是一样的,h=0.4056,h * m = 0.1352 。如果{p1, p2, p3}的值分布为:{0.3333, 0.3333, 0.3333},此情况下,m值均为0.3333,h=0.6037,h * m = 0.2012。明显大于表15第3行和第11行的情况。这说明了修正系数的有效性和普适性。
1) 各搜索引擎网页分级大小不同情况
在实际应用,如表16示,百度、腾讯和谷歌三网站的平均分级都是9,但各搜索引擎对其的评级分布不一样。网熵分级可以反映出这些不均匀分布,如百度网站的分布系数h为0.9898,网熵分级为100;腾讯和谷歌网站的分布系数h为 0.9878,网熵分级为99.80。
表中还显示,中科大和中科院两网站的平均分级都是6,但各搜索引擎对其的评级分布不一样。中科大网站的分布系数为0.8444,网熵分级为56.87。中科院的两项指标分别为:0.8407和56.63。由此看出,网熵分级反映出这种不均匀性。
表十六 若干网站网熵分级数据分析
2) 各搜索引擎网页分级次序不同情况
对于腾讯和谷歌两个网站,平均分级都是9,网熵分级都是99.80但各搜索引擎对其评级分布不一样,如腾讯网站的分级次序为10、9和8;而谷歌网站的分布为8、9和10。如参考上述中国互联网搜索引擎使用率,进行加权分级,百度权重占81.1%;搜狗评级和谷歌PageRank的权重分别9.45%。则腾讯网站的加权分级为9.72,绝对网熵分级为9.60;谷歌网站的加权分级为8.28,绝对网熵分级为8.18;百度网站的加权分级为 8.91,绝对网熵分级为9。相比之下,腾讯的绝对网熵分级最大,则其相对网熵分级为100。百度相对网熵分级为92.80,谷歌为85.20。
本节简述申农信息理论,提出网熵分级的负熵算法,并分析其分布特性,以说明有效性和适用性。下节《网络大同,任重道远》将作为全文的总结,对搜索引擎的网页分级提出若干建议。欢迎各位专家和网友提出珍贵意见。
参考资料
[7] Shannon, Claude, A Mathematical Theory of Communication [J]. Bell System Technical Journal, Vol. 27, pp. 379–423, 623–656, 1948.
[8] 欧阳峰, 数字通信介绍(2) 香农与信息论 , 科学网博客文章, 2009, accessed in 2011。http://blog.sciencenet.cn/home.php?mod=space&uid=309766&do=blog&id=275997
[9] 李伟钢,复杂系统结构有序度--负熵算法[J]. 系统工程理论与实践,1988, 8(4): 15-22。
Li Weigang,An Algorithm for Negative Entropy–The Sequence of the Complex System Structure [J].Systems Engineering Theory & Practice,(Quarterly) 1988,8(4):15-22.
[10] Li Weigang, Zheng Jianya and Daniel Li, W-entropy Index: the Impact of Members on Social Networks, WISM 2011, Taiyuan, China. Gong et al. (Eds.): WISM 2011, Part I, LNCS 6987, pp. 226—233, Springer-Verlag Berlin Heidelberg。
[11] Li Weigang, Zheng Jianya and Daniel Li, Analysis of W-entropy Index: the Impact of Members on Social Networks. In Proceedings of The IADIS International Conference WWW/INTERNET 2011, pp.171-178, Rio de Janeiro, Brazil, November 05 –08, 2011. Best Paper Award.
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-7-28 00:54
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社