|
虽然算法3 没有归一化处理步骤，但由于算法3 的迭代矩阵AT 是一个概率转移矩阵， 根据上面的分析可知算法3 能够收敛。在算法2 中，虽然并不能保证迭代矩阵AT 是一个概 率转移矩阵，但在算法2 的每一步迭代中都存在着一个归一化处理步骤，这说明算法2 和算 290 法3 的迭代过程大体上相似。虽然目前没有从理论上得到算法2 的收敛性结果，但从几个仿 真实验中我们看到，算法1 和算法2 都能正常结束。 如果将算法1 中每个点Xi(i=1,…,n)的迭代范围从原来的δ 近邻有向关联点集δ(Xi)扩充 为整个数据点集S={X1,X2,…,Xn}，那么算法1 的迭代形式完全可以表示为算法2 的矩阵迭代 形式，从而表明算法1 与算法2 是等价的，2 个仿真实验也验证了这一点。 295 3 模型及算法的应用 3.1 网站重要性分析 将每个进入网站重要性排序操作的设定为一个结点，则所有的入围网站就形成了一个集 合，设为S={X1,X2,…,Xn}。将dis(·,·)设定为网站之间的差异程度，则可将本文提出的模型及 算法应用于网站的重要性排序分析。 300 这种网站重要性排序问题所对应的有向图一般会存在圈。通过3 个算法形式的时空复杂 度分析可知，采用δ 近邻有向图模型比全连通的有向图模型或递归神经网络模型具有更小的 时空代价。 对于这类问题，网站Xi 到网站Xj 的有向关联相似性度量s<Xi,Xj>可采用定义3 来计算。 当参数δ 设定为0 时，网站Xi 的近邻有向关联点集δ(Xi)就是那些关联链接到网站Xi 的其他 305 网站了。当δ>0 时，网站Xi 的近邻有向关联点集δ(Xi)就是由那些关联链接到网站Xi 且到网 站Xi 的有向关联相似性度量不小于参数δ 的其他网站组成的。形式化为：δ(Xi) = {Xj | s<Xj,Xi> ≥ δ, Xj≠Xi, Xj∈S}。 在建立一个所有网站的δ 近邻有向关联图Gδ(S)之后，对每一个网站Xi(i=1,…,n)，δ(Xi) 易于通过Gδ(S)的入向邻接表存储结构构造出来。 310 现有的经典网站排序算法有：PageRank 算法，主题敏感的PageRank 算法(Topic-Sensitive PageRank)，Inside PageRank 算法[7]和HITS 算法。我们认为，本文提出的δ 近邻有向图模 型实现起来更简单，时空复杂度也比较小(低于矩阵式Θ(n2)的时空代价)。 3.2 基于δ 近邻有向关联势的关键结点发现算法文献引用关联关系分析 在文献库中，文献之间存在一定的关联关系，不同文献的作用和地位也不尽相同。为尽 315 快地发现关键文献或推荐出重要文献，可对文献库中的所有文献进行文献引用关联关系分 析。这个分析问题所对应的有向图数学模型一般不会存在圈，而且整体趋势上存在着一种单 向的指向关系，所以它一般会是一种有向网络图。 同样的道理，采用δ 近邻有向图模型比全连通的有向图模型或递归神经网络模型具有更 小的时空代价。其数据结构设计及模型的迭代计算方法与上面的网站重要性排序分析问题完 320 全相同。 3.3 人际关联关系分析 在社会生活中，人与人之间的关系会自然地形成了一个关联关系网。这种人际关联关系 分析问题通常可采用一种有向图模型来描述，这种类型问题的有向图模型一般会存在多个 圈，而且在整体趋势上会形成多个簇。 325 同样的道理，采用δ 近邻有向图模型比全连通的有向图模型或递归神经网络模型具有更 小的时空代价。其数据结构设计及模型的迭代计算方法与上面的网站重要性排序分析问题完 全相同。 4 仿真实验 4.1 仿真实验设计 330 4.1.1 实验环境 相关实验均在Pentium(R) Dual-Core CPU E5400 2.69GHz 上进行，配备2G 内存，在 Windows 7 下的Visual C++6.0 开发环境下采用C 语言来进行仿真实验验证。 4.1.2 实验数据集 A. 1 个人工构造的例子：5 个结点形成了一个有向图如图1 所示，其有向关联相似性度 335 量矩阵为： s = (sij)5×5 = ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ ⎛ 0 0 0.5 0.4 0 0 0 0.4 0 0 0 0.5 0 0 0 0 0 0 0 0 0 0.2 0 0.3 0 图1. 一个由5 个结点构成的有向图(未绘制出每个结点指向自身的有向边) 340 B. 1 个规整化后的UCI 标准数据集Iris[8]：设定一个距离关联阈值γ=0.5，当Iris 数据集 中两个点之间的距离相异性度量小于γ 时，这两个点之间存在着关联边；否则就不存在着关 联边。显然，按照这种方案构造出来的图将是一个具有150 个结点的对称图。 4.1.3 实验方法 通过上面人工构造的例子和Iris 数据集来验证在5 种情形(在下节中列举出)下，算法1、 345 算法2 和算法3 是否收敛，算法1、算法2 是否等价，这3 个算法的最终结果对比。 4.2 仿真实验结果 4.2.1 人工构造的例子的仿真实验结果 这里可以将δ 设置为一个极小的正数，甚至可以设为0。根据定义4 和参数δ 的设置， 在第一种情形下(case 1)，三个算法的实验结果如表1 所示，其余四种情形的实验结果可依 350 次类推。 (1) case 1(算法1、算法2 和算法3 描述出的一种情形): 在这种情形下，算法1 中每个点 的δ 近邻有向关联点集包含自身，算法2 和算法3 中每个点的自身关联相似性度量设定为1， 即：未归一化的迭代矩阵对角线元素设定为s<Xi,Xi> = 1(i=1,…,n)。这种情形的实验结果如 表1 所示： 355 表1 5 个结点及其δ 近邻有向关联点集(case 1) 点标记 δ(Xi) A1 的I(Xi)值 NI=77457 A2 的I(Xi)值 NI=77458 A2*的I(Xi)值 NI=66 X1 {X1} 0 0 0 X2 {X1, X2, X3} 0.999923 0.999923 1 X3 {X3, X4, X5} 0.000077 0.000077 0 X4 {X1, X4, X5} 0 0 0 X5 {X5} 0 0 0 此时，未归一化的迭代矩阵的转置矩阵(即所有点对的有向关联相似性度量矩阵)为： s = (sij)5×5 = ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ ⎛ 0 0 0.5 0.4 1 0 0 0.4 1 0 0 0.5 1 0 0 0 1 0 0 0 1 0.2 0 0.3 0 360 (2) case 2: 在这种情形下，算法1 中每个点的δ 近邻有向关联点集不包含自身，算法2 和算法3 中每个点的自身关联相似性度量设定为0，即：未归一化的迭代矩阵对角线元素设 定为s<Xi,Xi> = 0(i=1,…,n)。这种情形的实验结果如表2 所示： 表2 5 个结点及其δ 近邻有向关联点集(case 2) 点标记 δ(Xi) A1 的I(Xi)值 NI=4 A2 的I(Xi)值 NI=5 A2*的I(Xi)值 NI=5 X1 Φ 0 0 0 X2 {X1, X3} 0 0 0 X3 { X4, X5} 0 0 0 X4 {X1, X5} 0 0 0 X5 Φ 0 0 0 365 此时，未归一化的迭代矩阵的转置矩阵(即所有点对的有向关联相似性度量矩阵)为： s = (sij)5×5 = ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ ⎛ 0 0 0.5 0.4 0 0 0 0.4 0 0 0 0.5 0 0 0 0 0 0 0 0 0 0.2 0 0.3 0 (3) case 3: 在这种情形下，若点Xi 无出向边，则算法1 中点Xi 的δ(Xi)包含自身；若点 Xi 存在出向边，则算法1 中点Xi 的δ(Xi)不包含自身。相似的，若点Xi 无出向边，则算法2 370 和算法3 的未归一化的迭代矩阵对角线元素设定为s<Xi,Xi> = 1(i=1,…,n)；若点Xi 存在出向 边，则算法2 和算法3 的未归一化的迭代矩阵对角线元素设定为s<Xi,Xi> = 0(i=1,…,n)。这 种情形的实验结果如表3 所示： 表3 5 个结点及其δ 近邻有向关联点集(case 3) 点标记 δ(Xi) A1 的I(Xi)值 NI=3 A2 的I(Xi)值 NI=4 A2*的I(Xi)值 NI=4 X1 Φ 0 0 0 X2 {X1, X2, X3} 1 1 1 X3 {X4, X5} 0 0 0 X4 {X1, X5} 0 0 0 X5 Φ 0 0 0 375 此时，未归一化的迭代矩阵的转置矩阵(即所有点对的有向关联相似性度量矩阵)为： s = (sij)5×5 = ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ ⎛ 0 0 0.5 0.4 0 0 0 0.4 0 0 0 0.5 0 0 0 0 1 0 0 0 0 0.2 0 0.3 0 (4) case 4: 在这种情形下，若点Xi 无出向边，则算法1 中点Xi 的δ(Xi)不包含自身；若 点Xi 存在出向边，则算法1 中点Xi 的δ(Xi)包含自身。相似的，若点Xi 无出向边，则算法2 和算法3 的未归一化的迭代矩阵对角线元素设定为s<Xi,Xi> = 0(i=1,…,n)；若点Xi 存在出向 380 边，则算法2 和算法3 的未归一化的迭代矩阵对角线元素设定为s<Xi,Xi> = 1(i=1,…,n)。这 种情形的实验结果如表4 所示： 表4 5 个结点及其δ 近邻有向关联点集(case 4) 点标记 δ(Xi) A1 的I(Xi)值 NI=57728 A2 的I(Xi)值 NI=57729 A2*的I(Xi)值 NI=65 X1 {X1} 0 0 0 X2 {X1, X3} 0.333306 0.333306 0 X3 {X3, X4, X5} 0.666636 0.666636 0 X4 {X1, X4, X5} 0.000058 0.000058 0 X5 {X5} 0 0 0 385 此时，未归一化的迭代矩阵的转置矩阵(即所有点对的有向关联相似性度量矩阵)为： (5) case 5: 在这种情形下，若点Xi 无入向边，则算法1 中点Xi 的δ(Xi)包含自身；若点 Xi 存在入向边，则算法1 中点Xi 的δ(Xi)不包含自身。相似的，若点Xi 无入向边，则算法2 和算法3 的未归一化的迭代矩阵对角线元素设定为s<Xi,Xi> = 1(i=1,…,n)；若点Xi 存在入向 390 边，则算法2 和算法3 的未归一化的迭代矩阵对角线元素设定为s<Xi,Xi> = 0(i=1,…,n)。这 种情形的实验结果如表5 所示： 表5 5 个结点及其δ 近邻有向关联点集(case 5) 点标记 δ(Xi) A1 的I(Xi)值 NI=3 A2 的I(Xi)值 NI=4 A2*的I(Xi)值 NI=46 X1 {X1} 0.245700 0.245700 0 X2 {X1, X3} 0.144963 0.144963 0 X3 {X4, X5} 0.191646 0.191646 0 X4 {X1, X5} 0.171990 0.171990 0 X5 {X5} 0.245700 0.245700 0 395 此时，未归一化的迭代矩阵的转置矩阵(即所有点对的有向关联相似性度量矩阵)为： 算法2 中的迭代矩阵AT 的转置矩阵A 就是原始的关联相似性度量矩阵s。 算法3 中的迭代矩阵AT 的转置矩阵A 为对原始的关联相似性度量矩阵s 进行行归一化 得到的。例如，对应case 3 的矩阵A 进行行归一化后的结果为： 4.2.2 Iris 数据集的仿真实验结果 5 种情形下的仿真实验结果都是：算法1 与算法2 的实验结果是相同的，算法3 与算法 2 的最终实验结果不同。另外，因为根据Iris 数据集构造出的是一个具有150 个结点的对称 学术论文网Tag：代写论文 代写代发论文 论文发表 代发论文 |
