|
数据点集S={X1,X2,…,Xn}中的所有点所形成的有向图的边数目，一般存在着：|E| << n2。 145 在Step2 中，若将每个点Xi(i=1,…,n)的δ 近邻有向关联势Iδ(Xi)简单地初始化为1/n，只 需要Time=Θ(n)，Space=Θ(n)。若采用算法中的初始化方法，需要Time=O(kn)，Space=O(kn)。 这里k 为数据点集S={X1,X2,…,Xn}中的所有点的δ 近邻有向关联点集集中的最大元素个数。 在Step3 中，迭代更新每个点Xi(i=1,…,n)的δ 近邻有向关联势Iδ(Xi)需要Time=O(knt)， Space=O(kn)。归一化每个点Xi(i=1,…,n)的δ 近邻有向关联势Iδ(Xi)需要Time=Θ(nt)， 150 Space=Θ(n)。其中t 是do-while 循环中的迭代次数，k 为数据点集S={X1,X2,…,Xn}中的所有 点的δ 近邻有向关联点集集中的最大元素个数。 在Step4 中，需要Time=Θ(n)，Space=Θ(n)。 (2) 在该算法中，对于每个点Xi(i=1,…,n)的δ 近邻有向关联势Iδ(Xi)来说，根据其初始化 取值和迭代规则可知，不管是最终的结果，还是迭代过程中的取值，δ 近邻有向关联势Iδ(Xi) 155 都能保证一直取非负值。 (3) 在该算法的Step3 中，如果将δ 近邻有向关联势的迭代更新公式的计算范围扩大到 数据点集S={X1,X2,…,Xn}的所有数据点，此时就无需构造δ 近邻有向关联图Gδ(S)了。这种 扩展迭代范围的迭代更新方法可描述为如下的算法2。 2.2 基于全局有向关联势的关键结点发现算法 160 2.2.1 算法描述 算法名称：基于全局有向关联势的关键结点发现算法(算法2) 输入：数据点集S={X1,X2,…,Xn}，设定的相异性度量dis(·,·)，先验的关联度值u<·,·>， 势阈值Δ。 输出：数据点集S={X1,X2,…,Xn}的关键结点。 165 步骤： Step1. 根据定义3 和设定的相异性度量dis(·,·)，采用公式s<Xi, Xj> = u<Xi, Xj>/(1 + dis(Xi, Xj))计算出数据点集S={X1,X2,…,Xn}中每对相异点的有向关联相似性度量。 Step2. 初始化每个点Xi(i=1,…,n)的全局有向关联势I(Xi)。一种初始化方法为： for(i = 1; i ≤ n; i++) 170 { I(Xi) ← 1/n; //如果有先验信息，也可设置为其它的初始值。 } Step3. 在全局范围内，对数据点集S={X1,X2,…,Xn}的每个点进行全局有向关联势的迭代 更新操作。具体的操作步骤为： 175 do{ //迭代更新每个点Xi(i=1,…,n)的全局有向关联势I(Xi) for(i = 1; i ≤ n; i++) { I(Xi) ← ( ) Σ∈ < > P S i I(P) * s P, X ; (10) 180 /* 也可将上面的更新公式修改为带衰减因子α∈[0, 1]的迭代更新公式。即为： I(Xi) ← α * ( ) Σ∈ < > P S i I(P) * s P, X + (1 – α) * I(Xi);*/ } //归一化每个点Xi(i=1,…,n)的全局有向关联势I(Xi) SumI = Σ= n j j I X 1 ( ) ; 185 for(i = 1; i ≤ n; i++) { I(Xi) ← I(Xi) / SumI; } }while({I(X1), I(X2) , I(Xn)}全大于0，且仍未完全稳定下来); 190 Step4. 将数据点集S={X1,X2,…,Xn}中的全局有向关联势大于势阈值Δ的数据点判定为 关键结点。 2.2.2 算法的讨论及分析 (1) 算法的时空复杂度分析： 在Step1 中，需要Time=Θ(n2)，Space=Θ(n2)。 195 在Step2 中，需要Time=Θ(n)，Space=Θ(n)。 在Step3 中，迭代更新每个点Xi(i=1,…,n)的全局有向关联势I(Xi)需要Time=Θ(n2t)， Space=Θ(n2)。归一化每个点Xi(i=1,…,n)的全局有向关联势I(Xi)需要Time=Θ(nt)，Space=Θ(n)。 其中t 是do-while 循环中的迭代次数。 在Step4 中，需要Time=Θ(n)，Space=Θ(n)。 200 (2) 在Step2 中，算法2 的初始化与算法1 的初始化在本质上是一致的。算法2 的初始 化在迭代1 次后所得到的结果就与算法1 的初始化结果一致了。这里列出第二种初始化方法， 是为了说明这种类型算法的初始化，其形式的多样性与本质的一致性往往是统一的。 (4) 在Step3 中，若迭代更新公式采用向量/矩阵形式，则可描述如下。 在全局范围内，对数据点集S={X1,X2,…,Xn}进行全局有向关联势的迭代更新操作。具体 205 的操作步骤为： do{ //迭代更新数据点集S={X1,X2,…,Xn}的全局有向关联势向量I = (I(X1),I(X2),…,I(Xn))T I ← AT · I; (11) //矩阵A = (aij)n×n，设定aij = s<Xi,Xj>。特别的，当i=j 时，有aij = aii = 1。 /* 也可将上面的更新公式修改为带衰减因子α∈[0, 1]的迭代更新公式。即为： 210 I ← α * (AT · I)+ (1 – α) * I; */ //归一化全局有向关联势向量I = (I(X1),I(X2),…,I(Xn))T SumI = Σ= n j j I X 1 ( ) ; I ← I / SumI; }while(向量I = (I(X1),I(X2),…,I(Xn))T 的元素全大于0，且该向量仍未稳定下来); 215 2.3 算法2 的理论模型描述 算法2 中的全局有向关联势的迭代更新算法还可采用如下的两种模型来进行描述。 (1). 有向图模型 图1. 有向图模型(未绘制出每个结点指向自身的有向边) 220 有向图模型能直观地描述出数据点集S={X1,X2,…,Xn}的有向关联关系及有向关联相似 性度量。 (2). 递归神经网络模型 X1 Xn X2 s<X1, X2> s<X1, Xn> s<X2, X1> s<X1, Xn> 225 图2. 递归神经网络模型 在递归神经网络模型中，可使用的一个更新公式为： for(i = 1; i ≤ n; i++) { I(t+1)(Xi) = α * ( ) Σ∈ < > P S i 230 I (t) (P) * s P, X + (1 – α) * I(t)(Xi); (12) } 式(12)中，迭代次数t = 0, 1, 2, …。 递归神经网络模型能较好地表示出数据点集S={X1,X2,…,Xn}的迭代过程。这里，该递归 神经网络模型构成了一个迭代动力系统。由于向量I = (I(X1),I(X2),…,I(Xn))T 设定了其在迭代 235 更新过程中的取值范围，所以算法最终能够退出循环 对算法2 进行适当的修改，可得到算法3。接着根据文献[5]所介绍的马尔可夫链收敛性 分析方法和文献[6]所介绍的非负矩阵的若干性质，得到算法3 的一个收敛性分析结论。 2.4 修改的基于全局有向关联势的关键结点发现算法 2.4.1 算法2 的修改版描述 240 算法名称：基于全局有向关联势的关键结点发现算法的修改版(算法3) 输入：数据点集S={X1,X2,…,Xn}，设定的相异性度量dis(·,·)，先验的关联度值u<·,·>， 势阈值Δ。 输出：数据点集S={X1,X2,…,Xn}的关键结点。 步骤： 245 Step1. 根据设定的相异性度量dis(·,·)和定义3，采用公式s<Xi, Xj> = u<Xi, Xj>/(1 + dis(Xi, Xj))计算出数据点集S={X1,X2,…,Xn}的有向关联相似性度量。定义一个矩阵B = (bij)n×n，设定 bij = s<Xi,Xj>。特别的，当i=j 时，有bii = s<Xi,Xi> = 1。接着定义一个对矩阵B 的行元素之 和进行归一化后得到的矩阵A = (aij)n×n，即：采用标准变换公式Σ= ← n k ij ij ik a b b 1 / (在仿真实 验的另外几种情形中，当第i 行的元素之和为非零时，采用上面的标准归一化公式；当第i 250 行的元素之和为0 时，采用的变换公式为：aij ← bij)。对矩阵B 进行行元素之和的归一化处 理，是为了得到一个概率转移矩阵AT。 Step2. 初始化每个点Xi(i=1,…,n)的全局有向关联势I(Xi)。一种初始化方法为： X2 t X1 X2 Xn t+1 I(t)(X1) I(t)(X2) I(t)(Xn) I(t+1)(X1) I(t+1)(X2) I(t+1)(Xn) s<X1, Xn> Xn s<X1, X1> X1 for(i = 1; i ≤ n; i++) { /* 如果有先验信息，也可设置其它的初始值。设定‖I‖1 = 1 通常是为了提高该算 255 法在现有计算机上的实现精度。 */ I(Xi) ← 1/n; } Step3. 在全局范围内，对数据点集S={X1,X2,…,Xn}进行全局有向关联势的迭代更新操 作。具体的操作步骤为： 260 do{ /* 迭代更新数据点集S={X1,X2,…,Xn}的全局有向关联势向量I = (I(X1), I(X2) , I(Xn))T。AT 为一个进行线形变换的算子矩阵(这里也称为一个马尔可夫链的转移矩阵) */ I ← AT · I; /* 也可将上面的更新公式修改为带衰减因子α∈[0, 1]的迭代更新公式。即为： I ← α * (AT · I)+ (1 – α) * I; */ 265 }while(向量I = (I(X1), I(X2) , I(Xn))T 的元素全大于0，且该向量仍未稳定下来); Step4. 将数据点集S={X1,X2,…,Xn}中的全局有向关联势大于势阈值Δ的数据点判定为 关键结点。 2.4.2 算法3 的收敛性分析 根据矩阵A 的定义及其特征(矩阵AT 为一个转移概率矩阵，其每一列的元素值之和均为 270 1)来看，由矩阵和向量的乘法运算可知，do-while 循环中的每一次迭代都可保证全局有向关 联势向量I 的1 阶范数值不变。即：‖I‖1 = 1 对每一次迭代都成立。这样，算法3 就可省 去算法2 的归一化处理步骤了。这样的一个迭代过程形成了一个马尔可夫链。 根据矩阵A 的定义，可知矩阵AT 为一个非负矩阵。因为矩阵AT 是一个列随机矩阵， 当取λ = 1 时，可得|AT - λ·E| = |AT- E| = 0，从而可知方程(AT- E)·x = 0 存在非零解，说明λ = 275 1 为矩阵AT 的一个特征值，方程(AT- E)·x = 0 的非零解就是对应于特征值λ = 1 的特征向量。 这里E 为n×n 的单位矩阵，x 为n 阶向量，|·|为行列式记号。 根据文献[5]中的7.4 节的练习24 可知，矩阵AT 的所有特征值的绝对值小于等于1。由 于矩阵AT 存在着一个等于1 的特征值(这里λ = 1 为主特征值)，所以能保证该马尔可夫链存 在着一个稳态向量。根据文献[5]的定理6.3.3，该稳态向量即为矩阵AT 的对应于特征值λ = 1 280 的特征向量(根据文献[6]的式(8.3.1)主特征值所对应的特征向量为一个非负向量)。在这种情 况下，算法经过若干次迭代后，全局有向关联势向量I 必定收敛到该稳态向量。 根据上面的收敛性分析，我们可得到如下的定理1。 定理1. 由列随机矩阵构造的马尔可夫链必收敛于对应于主特征值λ = 1 的特征向量(该 特征向量称为稳态向量)。 285 证明：由上面算法3 的收敛性分析可知，该结论成立。 2.4.3 算法1 和算法2 的收敛性分析 学术论文网Tag：代写论文 代写代发论文 论文发表 代发论文 |
