矩阵本原不动点研讨

开篇：润墨网以专业的文秘视角，为您筛选了一篇矩阵本原不动点研讨范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

本文作者：马 垣 张学东 沈娟华 单位：辽宁科技大学软件学院 辽宁科技大学电子与信息工程学院 辽宁科技大学理学院

1引言

聚类是数据库知识发现领域的重要课题，已有很多方法，例如：分裂法、层次法、密度法、网格法、模型法等，各种方法有不同的基本思想[1]．文献[2]中提出了一种CONCOR聚类，这种聚类的基本思想与其它方法不同，这种聚类是借助矩阵的CONCOR变换．若A=(aij)n×m是一个n行m列的矩阵，则以A的i行与j行的相关系数为矩阵B=(bij)n×n的i行j列元素，这里σi,σj分别是A的第i行及第j行的平均值，矩阵B称为是A的CONCOR变换，记作B=CONCOR(A)．利用CONCOR变换来做CONCOR聚类的方法如下：首先把n个对象在m个属性上的取值vij(1in,1jm)写成一个n×m矩阵V=(vij)n×m．然后令C1=CONCOR(V),•••,Cn=CONCOR(Cn1),•••，已证明迭代序列C1,C2,•••,Cn,•••一定在有限次收敛[2]，注意到迭代时除V是n×m阶外，C1,C2,•••,Cn,•••都是n×n阶．将这个极限矩阵中相等的各行所对应的对象作为一类，就是对n个对象的CONCOR聚类．还可以对每一类对应的子阵再进行CONCOR聚类，将每一类再进一步细分．将细分的每类再进行CONCOR聚类，如此下去直到满足用户的某种要求，例如，组数大于多少或各组的元素个数少于多少等要求为止．显然这是一种很新颖的聚类方法，这种聚类方法对数据没有特别要求，任何数据都可使用．目前这个方法的聚类主要用在“块模型”(Blockmodel)分析方法方面，运用CONCOR聚类方法分成子群体(subgroup)，或称为块(block)，得到树型图，发现体系中的结构特点，然后对结果进行分析理解[3-16]．相关系数矩阵迭代的收敛性最早是McQuitty在1968年发现的[17]．后来Breiger等于1975年将这种迭代方法命名为CONCOR算法[18]，取相关收敛，convergentcorrelations，每个字的前3个字母．近来人们将其用于聚类，并称为CONCOR聚类[2]．此后CONCOR聚类的方法得到非常广泛的应用[3-16]．文献[2,3]中还对CONCOR聚类特点及意义作了深入的研究．以上众多领域工作的依据都是通过CONCOR变换迭代序列收敛获得的矩阵，而这个矩阵显然是CONCOR变换的不动点．于是为了深入地研究CONCOR聚类，了解它都有哪些不动点是非常重要的，这显然是CONCOR聚类研究的最核心问题之一．我们在大量实际计算的基础上，发现n×n矩阵的CONCOR变换不动点有两类．一类我们定义为n阶本原不动点，另一类我们定义为n阶组合不动点．n阶组合不动点是由一些小于n阶的本原不动点组合而成的．我们提出了n阶本原不动点的结构型式，它包括完美矩阵及我们提出的朴素矩阵，并给出了它们都是不动点的严格证明；我们进而还提出了0均值不动点的全新概念，以及组合不动点的组合方法，严格地证明了它们确实是不动点．这些结果使人们对CONCOR聚类方法的不动点有了进一步深入的了解，也使CONCOR聚类研究得以进一步推动．本文组织情况如下：第1节引言；第2节给出了CONCOR变换的一个等价定义，给出完美矩阵的定义并提出了朴素矩阵的新概念，还证明了它们的一些性质；第3节讨论了不动点，给出完美阵及朴素阵是变换本原不动点的严格证明，并提出了0均值不动点的概念，提出了生成组合不动点的方法，严格证明了它们确实是不动点；第4节是对这个研究工作的进一步展望．

2CONCOR变换

为了便于之后的证明，我们将矩阵A的CONCOR变换等价地定义为由“准CONCOR变换”及“CONCOR变换”两步组成．定义1设A=(aij)n×m是任意n×m矩阵，记其第i行的行向量为ai，记第i行的元素和ai1+ai2+•••+aim为σi(i=1,2,•••,n)，记第i行的元素的平均值σi/n为σi(i=1,2,•••,n)，则A的准CONCOR变换，记作CON(A)，是矩阵B=(bij)n×n，其中这里Jnn是n×n的全“1”阵．定义2若A是一个n×n矩阵，且CONCOR(A)=A，则称A为CONCOR变换的不动点，简称不动点．若A是不动点，而且对所有1in,1jn都有aij=0，则称A为n阶本原不动点，否则称A为组合不动点(组合一词的来源请见定理3)．

3本原不动点与组合不动点

定理1n阶完美阵是CONCOR变换的n阶本原不动点．为了证明阶朴素阵都是n阶本原不动点及后面证明定理3的需要，我们先证以下引理．引理3设A是n阶朴素阵或n阶全“1”阵，每行元素和的绝对值为σ．根据引理2，在朴素阵或全“1”阵中每行元素和的绝对值都是相同的，Jnn是一个n×n全“1”阵，则：1)A×A=nA；2)A×Jnn×A=σ2A；3)A×Jnn×Jnn×A=nσ2A．定理2每个n阶朴素阵都是n阶本原不动点．我们研究发现由本原不动点可组合成更高阶数的新的不动点．为此先给出以下定义：若A是n阶本原不动点，而且σ1=σ2=•••=σn=0，则称其为0均值不动点．以下再给出两个引理．引理4设A是n阶0均值本原不动点，Jnm,Jnm分别是n×m,m×n的全“1”阵，则：1)AJnm=0nm；2)JmnA=0mn；3)A×A=ρ2Amn，这里0nm,0mn分别是n×m,m×n的全“0”阵，ρ是A各行的模．注意到由引理2知，不论完美阵还是朴素阵，各行的模都是相同的．引理5设A是一个n阶本原不动点或A阶全“1”阵，Jnm,Jmn分别是n×m,m×n的全“1”阵，则AJnmJmnA=mσ2A，这里σ是A的各行元素和的绝对值，注意到引理2，不论完美阵、朴素阵还是全“1”阵，各行元素和的绝对值都是相同的．下面给出阶组合不动点的组合方法．定理3设具有以下形式的n×n矩阵A其中下标为0的A(n1)0,A(n2)0,•••,A(nk)0分别是n1阶,n2阶,•••,nk阶的0均值本原不动点；下标为1的只有一个A(n0)1．A(n0)1是n0阶任意本原不动点或n0阶全“1”阵，而且n0+n1+•••+nk=n，则A是n阶不动点，并称为n阶组合不动点．

4展望

近年来CONCOR聚类方法的应用越来越多，但对其不动点的研究一直进展不大．我们这里给出了一种不动点完整的定义，提出了朴素矩阵、均值不动点、本原不动点及组合不动点的全新概念，并给出它们是CONCOR聚类不动点的严格证明．这使得对CONCOR聚类不动点的认识大大深化了．我们不仅证明了本文给出的矩阵都是CONCOR变换不动点，而且我们还将研究n阶互不等价的不动点的个数是多少．例如由现在的结果看n=1时有1个，n=2时有1个，n=3时有3个，n=4时有6个，n=5时有10个，n=6时有17个，等等，在未来的研究中，我们将进一步探讨个数值的递推公式．