第1期 朱林，等：鲁棒的模糊方向相似性聚类算法 ·49· 定理2证明 证明：1)因为0≤h≤1,0<m<1,所以 JRFDSC达到最小，即求在 =1, (1、)中每一项（均大于等于 0<4<m,∈0,1]以及ww=1条件下 0,因此f(h,b,…w0.f(h,e,w)=0当 的峰值，为此引入Lagrange乘子入，b并定义 Lagrange目标函数L(w,入，a,y: 且仅当，4(·)中的每一项均为0，即 h("1-1)=00≤i≤d,那么必有h=0或 Lfsa.)a+ “=1由于有，山=1的限制，则f(a,e,“ E(X4)+s少.14 e)=0只能有某一个h=1,其他w=0(k卡)的 对Lw,人，a,b关于求偏导，令其值为零得 情况。 山=[ 15 m("-a) 2)考虑f(h,也，)=】 将式15)代入卫=1，消去4/m得 0≤山≤)在约束条件∑“=1下的极值.应用 拉格朗日乘数法构造函数：G=∑u(w1·)- 16) ,4.令G股…均为0得4= 当e-a<0,出现负值，隶属度也会为负.故 d ue 自适应提升4，使得e-4为正。 地=4=上，A=mc小m.1. c 定义a=min/e"|i∈1，c}-1,(I>0), 又因为f(M,也，在0,1下上是连续的， 代入式10)从而得到 故f(n,,一定有最值，而最值一定在驻点 u=(es"min e 或边界点处取得 e.mine以.+nvey. (17) 下面分别求f(h,,)在驻点或边界点 对Lw,人，a,b关于w求偏导数，并令其值为零得 处的函数值 y当n=e==1时，fn,e,)= 0=,25e+26m=0. (18) cm-1. 则有： 2)对于0,1的边界点(h,也，，e),设h, w=】 ae/126. (19) 地，h中有p1≤p≤个w为0，q0≤g)个 由于ww=1,由式(19)可以进一步推出： h为1. xue ①若p+q=c,则∑4w1-)=0. W= 证毕 ②若p+q<c,将w=0,1代入f(M,, ue )中，不失一般性，不防假设前p+g个u,为0或1， 则f(n,,…)转化为c·p·q维的形如 参考文献： (1·)的函数.由反证法很容易证明 [1]DHILLON I S,MODHA D S.Concept decompositions -p1 for large sparse text data using clustering [J].Machine ∑w(w1-1)<cm.1 Learning,2001,42(1):143175. - [2]BANERJEE A,DHILLON I S,GHOST J,et al.Gem 综上所述，f(h,b,k)在m==g= erative model based clustering of directional data [C]// 七时取最大值。.1 证毕 Conference on Knowledge Discovery in Data.Washing- ton,DC,2003. 定理3证明 [3]LI H X,WANG S T,XIU Y.Applying robust direc- 证明使RFDSC算法的目标函数即式(5)中 tional similarity based clustering approach RDSC to clas- 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net定理 2 证明 证明 : 1) 因为 0 ≤ ui ≤1 ,0 < m < 1 , 所以 ∑ c i = 1 ui ( u m- 1 i - 1) 中每一项 ui ( u m- 1 i - 1) 均大于等于 0 ,因此 f ( u1 , u2 , …, uc ) ≥0. f ( u1 , u2 , …, uc ) = 0当 且仅当 ∑ c i = 1 ui ( u m- 1 i - 1) 中的每一项 均为 0 , 即 ui ( u m- 1 i - 1) = 0 (0 ≤i ≤c) ,那么必有 ui = 0 或 ui = 1. 由于有 ∑ c i =1 ui = 1 的限制 , 则 f ( u1 , u2 , …, uc ) = 0 只能有某一个 ui = 1 ,其他 uk = 0 ( k ≠i) 的 情况. 2) 考虑 f ( u1 , u2 , …, uc ) = ∑ c i = 1 ui ( u m- 1 i - 1) (0 ≤ui ≤1) 在约束条件 ∑ c i =1 ui = 1 下的极值. 应用 拉格朗日乘数法构造函数 : G = ∑ c i = 1 ui ( u m- 1 i - 1) - λ( ∑ c i = 1 ui - 1) . 令 9 G 9 u1 , 9 G 9 u2 , …, 9 G 9 uc 均为 0 , 得 u1 = u2 = …uc = 1 c ,λ = mc 1 - m - 1. 又因为 f ( u1 , u2 , …, uc ) 在[0 , 1 ] c 上是连续的 , 故 f ( u1 , u2 , …, uc ) 一定有最值 ,而最值一定在驻点 或边界点处取得. 下面分别求 f ( u1 , u2 , …, uc ) 在驻点或边界点 处的函数值. 1) 当 u1 = u2 = …uc = 1 c 时 , f ( u1 , u2 , …, uc ) = c 1 - m - 1. 2) 对于[0 ,1 ] c 的边界点 ( u1 , u2 , …, uc ) ,设 u1 , u2 , …, uc 中有 p (1 ≤p ≤c) 个 ui 为 0 , q(0 ≤q ≤1) 个 ui 为 1. ①若 p + q = c ,则 ∑ c i = 1 ui ( u m- 1 i - 1) = 0. ②若 p + q < c ,将 ui = 0 ,1 代入 f ( u1 , u2 , …, uc ) 中 ,不失一般性 ,不防假设前 p + q个 ui 为0或1 , 则 f ( u1 , u2 , …, uc ) 转化为 c - p - q 维的形如 ∑ c i = p+q+1 ui ( u m- 1 i - 1) 的函数. 由反证法很容易证明 ∑ c i = p+q+1 ui ( u m- 1 i - 1) < c 1 - m - 1. 综上所述 , f ( u1 , u2 , …, uc ) 在 u1 j = u2 j = …ucj = 1 c 时取最大值 c 1 - m - 1. 证毕. 定理 3 证明 证明 使 RFDSC 算法的目标函数即式 (5) 中 J RFDSC 达 到 最 小 , 即 求 在 ∑ c i =1 uij = 1 , 0 < ∑ n j =1 uij < n , uij ∈[0 ,1 ] 以及 w T i wi = 1 条件下 的峰值 , 为 此 引 入 Lagrange 乘 子 λ, b. 并 定 义 Lagrange 目标函数 L (w,λ, a , b) : L(w,λ, a,b) = ∑ c i =1 ∑ n j =1 u m ij (e kx T j wi ) - ∑ n j =1 aj ∑ c i =1 uij ( u m- 1 ij - 1) + ∑ n j = 1 λj ( ∑ c i = 1 uij - 1) + ∑ c i = 1 bi (w T i wi - 1) . (14) 对 L (w,λ, a , b) 关于 uij求偏导 ,令其值为零得 uij = [ - aj - λj m (e kx T j wi - aj) ] 1/ ( m- 1) . (15) 将式(15) 代入 ∑ c i = 1 uij = 1 , 消去( - aj - λj) / m 得 uij = (e kx T j wi - aj) - 1/ ( m- 1) / ∑ c i = 1 (e kx T j wi - aj) - 1/ ( m- 1) . (16) 当 e kx T j wi - aj < 0 ,出现负值 ,隶属度 uij 也会为负. 故 自适应提升 aj ,使得 e kx T j wi - aj 为正. 定义 aj = min{ e kx T j wi | i ∈{ 1 , …, c}} - η, (η> 0) , 代入式(10) 从而得到 uij = (e kx T j wi - min e kx T j w 3 +η) - 1/ ( m- 1) / ∑ c i =1 (e kx T j wi - min e kx T j w 3 +η) - 1/ ( m- 1) . (17) 对 L (w,λ, a , b) 关于 wi 求偏导数 ,并令其值为零得 9L 9wi = ∑ n j =1 kx T j u m ij e kx T j wi + 2biwi = 0. (18) 则有 : wi = ∑ n j = 1 kx T j u m ij e kx T j wi / ( - 2bi) . (19) 由于 w T i wi = 1 ,由式(19) 可以进一步推出 : wi = ∑ n j = 1 x T j u m ij e kx T j wi ‖∑ n j = 1 x T j u m ij e kx T j wi ‖ . 证毕. 参考文献 : [1 ]D HILLON I S , MODHA D S. Concept decompositions for large sparse text data using clustering [J ]. Machine Learning , 2001 , 42 (1) :1432175. [2 ]BAN ERJ EE A , DHILLON I S , GHOST J , et al. Gen2 erative model based clustering of directional data [ C]/ / Conference on Knowledge Discovery in Data. Washing2 ton , DC , 2003. [3 ]L I H X , WAN G S T , XIU Y. Applying robust direc2 tional similarity based clustering approach RDSC to clas2 第 1 期 朱 林 ,等 :鲁棒的模糊方向相似性聚类算法 ·49 ·