·554· 智能系统学报 第14卷 ={h其 1/ln(x,6儿，x∈n(x, (12) 4)root.setChild (,x); 5)U=U-{x,x 算法1 PageRank排名计算算法 6)else then 输入决策信息系统S=(U,C,d): 7)计算与root最相似的样本xeU; 输出排名向量Rank。 8)计算与x最不相似的样本x,∈U； l)for(eachx∈U)do 9)root.setChild () 2)for (eachyU)do 10)U=U-{x,x, 3)根据式(2)计算dis(xy; 11)end if 4)根据式(3)计算sim(x,y 12)U=0,U,=0 5)end for l3)for(eachx∈U)do 6)根据式(4)计算n(x): 14)if (sim(x,x )sim(x,x,))then 7)end for 15)U,=U,U{x: 8)根据式(12)计算邻接矩阵A: 16)else then 9)k=1: 17)U,=U,U{x 10)T=A+(1-y)E1m: 18)end if 11)P=111 19)end for 12)while (IP -Pl >do 20)对x,U继续调用算法2： 13)P=TPML 21)对x,U继续调用算法2； 14)k++: 22)end while 15)end while 23)return root; 16)Rank sort(P); 35)寻找root的孩子节点，即U中最不相似 17)return Rank: 的一对样本；7)~10)寻找非root节点的孩子节点； 算法1描述了样本的排名向量的计算过程。 12)定义x和x,的样本集合；13)19)通过比较集 1)人7通过计算样本间的相似度，确定每个样本的 合U”中样本与x、x相似度大小，实现集合的划 邻域；10)根据式(9)计算状态转移矩阵T;11) 分：20小21)递归调用算法2。 定义初始分值向量Po;12)15)计算收敛条件下分 2.2.3二叉树聚类算法 值矩阵P:16)对分值矩阵P进行降序排序。 ·般来说，聚类簇数K与聚类质量关系密 2.2.2二又树生成算法 切，然而大多数聚类算法只能通过经验或者试凑 主动学习阶段在二叉树上进行，为了避免离 指定簇数K。本文采用一种执行边缘分离的聚类 群点对该阶段标签查询、预测的影响，保证查询 策略，不需要将K作为输入，而是根据二叉树的 到的样本均具有较高的信息量，仅利用排名前 内部结构自然地分簇。 R的代表样本去构建二叉树。同时，树形结构能 通过计算二叉树节点间的相似度，将二叉树 够充分体现数据的层次关系，便于数据分析，从 的边划分为分割边或者非分割边。假设两节点足 而得到更好的聚类结果。 够相似，可将该连边定义成非分割边，反之定义 二叉树生成算法是一个典型递归算法。其构 为分割边。这种边界划分方式基于一个阈值。第 建过程分为两步：寻找孩子节点，根据孩子节点 一轮迭代时，阈值是二叉树相连节点间相似度的 划分集合。根结点root的孩子节点是U中最不 最小值。 相似的两个样本，其余节点x的左孩子是当前集 算法3二叉树聚类算法 合中与x最相似的样本x,右节点是当前集合中 输入二叉树根节点root: 与x最不相似的节点x,。 输出聚类信息块bl=blbl2bl]o 算法2二叉树生成算法 1)clusterT(root.Ic,count,threshold)start 输入排名前R的代表集合U; 2)cnroot.lc]count; 输出二叉树root。 3)if (root.Ic.Ic!null)then 1)while(U!=0)then 4)if (sim (root.lc,root.lc.lc)s threshold) 2)if(root)then 5)clusterT (root.Ic.Ic.++count,threshold): 3)计算最不相似的一对样本x,x,∈U; 6)else thena ′ i j = { 1/|n(xi , θ)|, xj ∈ n(xi , θ) 0, 其他 (12) 算法 1 PageRank 排名计算算法 输入 决策信息系统 S = (U, C, d)； 输出 排名向量 Rank。 1) for (each x∈U) do 2) for (each y∈U) do 3) 根据式 (2) 计算 dis(x y); 4) 根据式 (3) 计算 sim(x, y); 5) end for 6) 根据式 (4) 计算 n(x); 7) end for 8) 根据式 (12) 计算邻接矩阵 A; 9) k = 1; 10) T = γA T + (1 − γ)E/n; P0 = [11···1] T 11) 1×n ; 12) while (|Pk − Pk-1| > ε) do 13) Pk = TPk-1; 14) k++; 15) end while 16) Rank = sort(Pk ); 17) return Rank; 算法 1 描述了样本的排名向量的计算过程。 1)~7) 通过计算样本间的相似度，确定每个样本的 邻域； 10) 根据式 (9) 计算状态转移矩阵 T；11) 定义初始分值向量 P0；12)~15) 计算收敛条件下分 值矩阵 P；16) 对分值矩阵 P 进行降序排序。 2.2.2 二叉树生成算法 主动学习阶段在二叉树上进行，为了避免离 群点对该阶段标签查询、预测的影响，保证查询 到的样本均具有较高的信息量，仅利用排名前 R 的代表样本去构建二叉树。同时，树形结构能 够充分体现数据的层次关系，便于数据分析，从 而得到更好的聚类结果。 二叉树生成算法是一个典型递归算法。其构 建过程分为两步：寻找孩子节点，根据孩子节点 划分集合。根结点 root 的孩子节点是 U′中最不 相似的两个样本，其余节点 x 的左孩子是当前集 合中与 x 最相似的样本 xl，右节点是当前集合中 与 xl 最不相似的节点 xr。 算法 2 二叉树生成算法 输入 排名前 R 的代表集合 U′； 输出 二叉树 root。 1) while (U′ != Ø) then 2) if (root) then 3) 计算最不相似的一对样本 xl , xr∈U′; 4) root. setChild (xl , xr ); 5) U′ = U′ − {xl , xr}; 6) else then 7) 计算与 root 最相似的样本 xl∈U′; 8) 计算与 xl 最不相似的样本 xr∈U′; 9) root. setChild (xl , xr ); 10) U′ = U′ − {xl , xr}; 11) end if 12) Ul = Ø, Ur = Ø; 13) for (each x∈U′) do 14) if (sim(x, xl ) > sim(x, xr )) then 15) Ul = Ul ∪ {x}; 16) else then 17) Ur = Ur ∪ {x}; 18) end if 19) end for 20) 对 xl，Ul 继续调用算法 2; 21) 对 xr，Ur 继续调用算法 2; 22) end while 23) return root； 3)~5) 寻找 root 的孩子节点，即 U′中最不相似 的一对样本；7)~10) 寻找非 root 节点的孩子节点； 12) 定义 xl 和 xr 的样本集合；13)~19) 通过比较集 合 U′中样本与 xl、x 相似度大小，实现集合的划 分；20)~21) 递归调用算法 2。 2.2.3 二叉树聚类算法 一般来说，聚类簇数 K 与聚类质量关系密 切，然而大多数聚类算法只能通过经验或者试凑 指定簇数 K。本文采用一种执行边缘分离的聚类 策略，不需要将 K 作为输入，而是根据二叉树的 内部结构自然地分簇。 通过计算二叉树节点间的相似度，将二叉树 的边划分为分割边或者非分割边。假设两节点足 够相似，可将该连边定义成非分割边，反之定义 为分割边。这种边界划分方式基于一个阈值。第 一轮迭代时，阈值是二叉树相连节点间相似度的 最小值。 算法 3 二叉树聚类算法 输入 二叉树根节点 root； bl = [bl1 bl2 ···bl 输出 聚类信息块 k]。 1) clusterT (root.lc，count，threshold) start 2) cn[root.lc] = count; 3) if (root.lc.lc! = null) then 4) if (sim (root.lc, root.lc.lc) ≤ threshold) 5) clusterT (root.lc.lc, ++count, threshold); 6) else then ·554· 智 能 系 统 学 报 第 14 卷