正交对与正交向量的关系

朱晓敏,祁建军



正交对与正交向量的关系

朱晓敏,祁建军*

西安电子科技大学计算机学院，西安 710071

正交对表示集合之间的正交性，正交向量表示向量之间的正交性，它们在一定程度上具有相似性，但目前尚无关于这一问题所展开的研究。针对此问题，以正交对的基本定义为基础给出正交对的基本性质，提出正交集合组以及正交关系系统的概念，建立信息系统以及形式背景与正交关系系统的联系。构造集合到向量的映射，使得集合的任意子集都有唯一一个布尔向量与之对应，根据此映射关系构建正交关系系统，进而在正交对与正交向量之间以及正交集合组与正交向量组之间建立一一对应关系。

正交对；正交向量；正交集合组；正交关系系统

引言

正交向量表示向量之间的正交性，在欧氏空间中表现为相互垂直。正交向量的发展已相对成熟，向量正交性已得到广泛应用[1-3]，并且在正交性与向量空间性质关系的研究中得到了很多重要的结论。

Ciucci于2011年提出正交对的概念[4]，针对粗糙集，区间集，阴影集等不确定性集合建立正交对模型，并在正交对的基础上定义不同偏序关系。进而研究了正交对在不确定性集合上的应用，如基于正交对处理不完善信息[5,6]，提出正交对于粒计算方面的应用研究[7]。

正交对在很多领域都有体现，比如在机器学习[8]中对数据集进行分类或者对大量的元素进行聚类时[9]，最终得到的各个子集可相互构成正交对；在三支决策理论[10]中，各个决策集之间也可构成正交对。

正交向量表示向量之间的正交关系，而正交对表示集合之间的正交关系，它们都表示对象之间的正交性，具有一定的相似性。本文借鉴正交向量的研究方法，对正交对展开研究。事实上，正交向量的部分研究是基于向量可量化的特性，为了将正交向量的性质应用于正交对，首先以Ciucci提出的正交对的概念为基础给出正交对的相关性质，并首次提出正交集合组以及正交关系系统的概念，根据正交对和正交向量都具有的正交性，构造集合与向量之间的映射，在此基础上构建相应的正交关系系统，从而建立起正交对与正交向量之间的联系，进而量化正交对，并在此基础上给出一些相关结论。

1 预备知识

正交向量的定义及基本知识在普通高校的教材中皆可找到。

定义1.1[11]如果向量，β的内积为零，即()=0，那么α，β称为正交或互相垂直，记为αβ。

由定义可知，若=0，则α与任何向量都正交。

定义1.2[4]设，为全集的子集，如果，满足：=，则称集合与集合正交，集合对(,)称为正交对。

2 正交对性质及基础研究

2.1 正交对的性质

根据正交对的定义可以得到正交对的基本性质。

为了便于表示，将正交对(,)记为，为了与正交向量的表示予以区分，文中用向量的内积为零来表示正交向量。

性质2.1.1设为全集，若,,,，则以下性质成立：

其中，A表示集合的补集。

证明根据正交对的定义可得出以上性质。

下面在正交对性质的基础上对多个集合之间的正交性进行研究。

2.2 正交集合组

正交对表示两个集合之间的正交性，为了同时表示多个集合之间的正交性，首先给出正交集合组的定义，然后在此基础上研究正交集合组的相关性质。

定义2.2.1如果非空集合1,2,...,A两两正交，那么集合组1,2, ...,A称为正交集合组。

正交对即=2的正交集合组。

例2.2.1 设={,,,,,},1={,,}，2={,}，3={}。因为集合组1,2,3满足12，13，23，所以集合组1,2,3为正交集合组。

下面给出关于正交集合组之间的正交关系的定义。

定义2.2.2 如果正交集合组1,2,...,A与正交集合组1,2, ...,B满足：

(=1,2,...,，=1,2,...,)

则称正交集合组1,2,...,A与正交集合组1,2,...,B正交。

推论2.2.1若正交集合组1,2,...,A与正交集合组1,2,...,B正交，则1,2,...,A,1,2,...,B也是一个正交集合组。

证明：根据定义2.2.1和定义2.2.2可知以上结论成立。

定理2.2.1如果正交集合组1,2, ...,A与正交集合组1,2, ...,B正交，且集合组1,2,...,C中的任意集合都可以由1,2, ...,A通过集合运算表示出来，那么1,2,...,C与1,2,...,B正交。

证明 因为1,2,...,A与1,2,...,B正交，所以，其中，=1,2,...,，=1,2,...,。

于是，

(...A)B=，

又因为1,2,...,C可由1,2,...,A表示，所以，对于任意的=1,2,...,，

C...A

所以，

CB

即1,2,...,C与1,2,...,B正交。

根据向量空间中正交基的概念，我们提出集合的正交基的概念。

定义2.2.3 若正交集合组1,2,...,A满足：

...A=

则称1,2,...,A为的正交基。

由定义2.2.3可知，集合的正交基的本质就是的划分。下面在集合划分的基础上对集合的正交基展开研究。

推论2.2.2集合的等价类个数大于等于2的划分是集合的正交基，反之亦然。

证明由于集合的正交基的元素个数至少为2，所以这里只讨论集合的等价类个数大于等于2的划分。

设1,2,...,A为的任意一个划分(≥ 2)，则：

...A=(2.1)

AA=(,=1,2,...,，) (2.2)

由式(2.2)可知，1,2,...,A为正交集合组，由式(2.1)以及正交基的定义可知，1,2,...,A为的正交基。

反之，若1,2,...,A为的正交基，同样满足式(2.1)和式(2.2)，同理可证1,2,...,A为的一个划分。

由推论2.2.2可知，的正交基和的等价类个数大于等于2的划分是等价的，它们是不唯一的，且的由不同的非空子集组成的正交基的组数与子集数以及||相关。

性质2.2.1 全集(||=)的由(≥ 2)个非空子集组成的正交基的组数(,)为：

证明该结论可利用推论2.2.2以及集合划分知识获得，(,)实为第二类Stirling数[12]。

例2.2.2 分析集合={,,}的正交基：

所以，由2个非空子集组成的正交基有三组，由3个非空子集组成的正交基只有一组。由2个非空子集组成的正交基有三组：

{{,},{}}，{{,},{}}，{{,},{}}。由3个非空子集组成的正交基有一组：{{},{},{}}

利用推论2.2.2和性质2.2.1可得以下结论。

推论2.2.3 设集合的所有的正交基的组数为B()，其中||=。则：

B()(,2)+...+(,)

例2.2.3集合={,,}的所有的正交基的组数为：

3() =(3,2)+(3,3) = 4

其中，(3,2)和(3,3)可由例2.2.2得出。

定义2.2.4设1,2,...,A为全集的正交基，如果|A|= 1(=1,2,...,)，则称正交集合组1,2,...,A为全集的标准正交基。

推论2.2.4集合的标准正交基是唯一的。

证明由性质2.2.1和定义2.2.4可知，集合的标准正交基数为：(,1)=1，其中||=。所以该推论成立。

性质2.2.2若正交集合组1,2,...,A为全集的标准正交基，则=||。

定理2.2.2集合中的任意子集都可由集合的标准正交基通过集合运算表示出来。

证明设集合为集合的一个子集，={1,2,...,a}，1,2,...,A为集合的标准正交基，1={1}，2={a}，...，A={a}，则集合可由标准正交基表示如下：

=(11)(22)...()

其中：

例2.2.4 设={,,,,}，={,,}，集合的标准正交基为：1={}，2={}，3={}，4={}，5={}，则子集可由全集的标准正交基表示如下：

={,,}

=134

3 正交关系系统

为了同时表达出正交对之间以及正交对与正交向量之间的联系，我们首次提出正交关系系统的定义。

定义3.1 设()为集合的幂集，若在()上存在一对映射，使得：()，()，()与()正交。则称=(,,)为正交关系系统。

由以上定义可知，通过改变正交关系系统中和的映射关系，可以分别表示出集合与集合之间以及集合与向量之间的正交关系。性质3.1给出具体描述。

性质3.1 设(,,)为正交关系系统。为集合，,()，()与()正交。则：

(),()()()()；

(),()((),())=0;

例3.1 设={,,,}，定义映射和映射满足：=，=，其中为恒等映射。

所以，=(,,) 为正交关系系统。

粗糙集理论中的信息系统与三支概念分析中的形式背景也可以表示为正交关系系统的形式。

例3.2在粗糙集理论[13]中使用信息系统(,,,)同时表示对象集，属性集，属性值域以及对象与属性之间的映射关系。表3.1为信息系统实例。

表3.1 信息系统(U,Q,V,f)

为上的一种等价关系。若,，(,)，则表明,是不可区分的。根据不可区分关系定义集合的下近似集，上近似集和边界集，具体如下：

*()={:()}

*()表示根据现有知识可以判断一定属于的对象所组成的最大集合。

集合关于的上近似集为：

*()={:()}

*()表示可能属于的对象组成的最小集合。

集合关于的边界集为：

()=*()-*().

在粗糙集理论中习惯利用图3.1的形式表达上下近似集之间的关系。

图3.1 粗糙集上下近似

由图3.1可知，*()与*()-*()是正交的，而正交关系系统就是表示两个对象之间具有的正交关系，所以可以利用正交关系系统表示图3.1。

下面基于信息系统以及不可区分关系构造正交关系系统。

令映射1，2满足：

1()=*()，

2()=()=*()-*()

则(,1,2)为正交关系系统。

正交关系系统(,1,2)同时表达了定义在上的映射关系以及*()和*()-*()之间具有的正交关系。

例3.3 在形式概念分析(FCA)[14]和三支概念分析(TWCA)[15,16]中利用形式背景(,,)同时表示属性集，对象集，以及二者之间的二元关系，表3.2是具体的形式背景。

表3.2 形式背景(U,V,R)

二元关系体现的是对象与属性之间的“具有”关系。若，，R表示对象具有属性。根据对象与属性之间的“具有”关系，定义不同的映射。

FCA中正算子[15]，表示对象子集与属性子集之间的“具有”关系：

其中，

正算子将属性集分成了互不相交的两部分：X*和U-X*，三支算子将属性集分成了互不相交的三部分：Y*，和U-Y*-，即X*与U-X*，Y*与都具有正交关系，但在FCA（TWCA）中并没有显示地表示出它们之间具有的正交关系。下面利用正交关系系统的形式同时表示对象集与属性集之间的映射关系以及映射象集中具有的正交关系。

基于形式背景以及对象集与属性集之间的“具有”关系构造正交关系系统。

令映射1，2满足：

1()=*，2()=-*

映射1，2满足：

1()=*，2()=

则(,1,2)，(,1,2)均为正交关系系统。

相应地，可以根据从属性集到对象集的映射关系构造出相应的正交关系系统。方法同上，这里不给出详述。

综上可知，利用正交关系系统可同时表示出对象集与属性集之间具有的映射关系以及对象集之间以及属性集之间具有的正交关系。

4 正交对与正交向量

由于正交对和正交向量都表示对象之间的正交性，可根据此特性建立起正交对与正交向量之间的联系。

4.1正交对与正交向量的联系

正交对和正交向量在一定程度上具有相似性，构造集合与向量之间的相互对应关系进而建立正交对与正交向量之间的联系。

定义4.1设={1,2,...,a}。构造从的幂集到向量空间的映射：()R，()，()=[1,2,...,x]，其中：

例4.1.1集合={,,,,}，={,,}，则()=[0,1,0,1,1]。

综上可知，映射为双射。

4.2 正交关系系统的建立

根据定义4.1建立正交关系系统。进而表示出正交对与正交向量之间的联系。

定理4.2.1=(,,)为正交关系系统。

证明 设={1,2,...,a}，为的任意子集，=，设：

()=[1,2, ...,x]

()=[1,2, ...,y]

即： ((),())=0，根据定义定义3.1可知，=(,,)为正交关系系统。

事实上，通过映射可以将集合量化，从而可以将正交向量中的部分性质应用于正交对，结合正交对和正交向量共同具有的正交性，可以得出以下定理。

证明 设={1,2,...,a}，={1,2,...,

b}，1≤,≤，||=。()=[1,2, ...,x]

()=[1,2, ...,y]。

由((),())=0，可得：

((),())=0

即

例4.2.1 设={,,,,,}，={,}，={,,}，，根据映射的定义可知：

()=[0,1,0,1,0,0]

()=[1,0,0,0,1,1]

则((),())=0。

反之，若已知：

()=[0,1,0,1,0,0]

()=[1,0,0,0,1,1]

则由((),())=0可知。

由定理4.2.2可知，当判断两个较大的集合是否互斥时，不需要对两个集合中的元素进行一一比较。可直接根据映射将集合转化为两个布尔向量，然后对其进行内积运算，根据运算结果判断两个集合是否互斥。

4.3 正交集合组与正交向量组的联系

映射建立了正交对与正交向量的一一对应关系。同样地，根据映射可以建立起正交集合组和正交向量组的对应关系。

推论4.3.1设1,2,..,()，1,2,...,A为正交集合组的充分必要条件为：(1),(2),...,(A)为正交向量组。

证明 由定理3.2.1可知，

((A),(A))=0

其中，，=1,2,...,

再根据定义1.5和2.2.1可知，1,2,...,A为正交集合组的充分必要条件为：(1),(2),...,(A)为正交向量组。

推论4.3.2设1,2,...,()，若1,2,...,A为正交集合组，则(1),(2),...,(A)线性无关。

证明 由推论4.3.1可知，(1),(2),...,(A)为正交向量组，又因为正交向量组是线性无关的，所以可得该推论。

例4.3.2 设={,,,}，1={,}，2={}，3={}，集合组1,2,3为正交集合组。相应地，

(1)=[1,1,0,0]

(2)=[0,0,1,0]

(3)=[0,0,0,1]

由线性无关的定义可知，(1),(2),(3)是线性无关的。

下例表明定理3.2.2的逆命题是不成立的。

例4.3.3设1,2,3,4()，其中，={,,,}，且：

(1)=[1,1,0,0]，(2)=[0,1,0,0]

(3)=[0,0,1,0]，(4)=[0,0,0,1]

由线性无关的定义可知，向量组(1),(2),(3),(4)是线性无关的。又根据映射的定义可知：

1={,}，2={}，

3={}，4={}，

其中：

1∩2={}，

所以1,2,3,4不是正交集合组。

推论4.3.3若正交集合组1,2, ...,A与正交集合组1,2,...,B正交，则(1),(2),...,(A),(1),(2),...,(B)线性无关。

证明 由根据推论2.2.1可知，1,2,...,A,1,2,...,B是一个正交集合组。又由定理3.2.2可知，(1),(2),...,(A),(1),(2),...,(B)线性无关。

定理4.3.31,2,...,A为全集的标准正交基的充分必要条件是(1),(2),...,(A)为R的标准正交基。

证明 设={1,2,...,a}，1,2,...,A为全集的标准正交基，不妨设A={a}，1≤≤。

必要性：

根据映射的定义可得：

(1)=[1,0,0,...,0]

(2)=[0,1,0,...,0]

...

(A)=[0,0,0,...,1]

根据欧氏空间的标准正交基的定义可知，

(1),(2),...,(A)为R的标准正交基。

充分性：

由(1),(2),...,(A)为R的标准正交基可得：

((A),(A))=0

所以，1,2,...,A为正交集合组，又因为

|A|= 1(=1,2,...,)，所以，1,2,...,A为全集的标准正交基。

5 结论

本文针对正交对进行研究，并在正交对的基础上给出了正交集合组的定义以及相关性质，为了建立正交对与正交向量之间的联系提出正交关系系统的概念。构造集合到向量的映射，建立相应的正交关系系统并在此基础上给出正交对与正交向量之间以及正交集合组和正交向量组之间的联系。事实上，由于正交向量和正交对的相似性，由前人得出的许多关于正交向量的性质对于正交对也是适用的，并且在数据分析中，许多算法中出现的集合都可以构成正交对，比如决策树，神经网络等，所以针对正交对的研究具有很大的意义。未来我们将针对此问题进行进一步深入的研究。

[1] 王静,马方明. 基于向量正交性的组播密钥管 理方案[J]. 计算机工程, 2013, v. 39; No. 42606: 162-165.

[2] 林伟,孟凡荣,王志晓. 基于概念特征的语义文本分类[J].计算机工程与应用, 2011, v. 47; No. 73128: 139-142.

[3] 孔万增,孙志海,杨灿,戴国骏,孙昌思核. 基于本 征间隙与正交特征向量的自动谱聚类[J]. 电子学报, 2010, v. 38; No. 32908: 1880-1885, 1891.

[4] Ciucci D. Orthopairs: A simple and widely usedway to model uncertainty [J]. Fundamenta Informaticae, 2011, 108(3-4): 287-304.

[5] Ciucci D, Dubois D, Lawry J. Borderline vs. unknown: comparing three-valued representations of imperfect information[J]. International Journal of Approximate Reasoning, 2014, 55(9): 1866-1889.

[6] Ciucci D. Orthopairs in the 1960s: historical remarks and new ideas[C]//Rough Sets and Current Trends in Computing. Springer International Publishing, 2014: 1-12.

[7] Ciucci D. Orthopairs and granular computing[J]. Granular Computing, 2016: 1-12.

[8] Witten I H, Frank E. Data Mining: Practical machine learning tools and techniques[M]. Morgan Kaufmann, 2005.

[9] Sebastiani F. Machine learning in automated text categorization[J]. ACM computing surveys (CSUR), 2002, 34(1): 1-47.

[10] Yao Y. An Outline of a Theory of Three-Way Decisions// Proceedings of 2012 International

[11] Conference on Rough Sets and Current Trends in Computing (LNCS 7413), Chengdu, China, 2012: 1-17.

[12] 北京大学数学系几何与代数教研室前代数 小组编王萼芳,石生明修订. 高等代数 第三版[M]. 北京: 高等教育出版社, 2003. 120-366.

[13] 姜建国,岳建国. 组合数学[M]. 2版. 西安: 西安电子科技大学出版社, 2007: 71-77.

[14] Pawlak Z. Rough sets: Theoretical aspects of reasoning about data[M]. Springer Science & Business Media, 2012.

[15] Wille R. Restructuring lattices theory: An approach on hierarchies of concepts [C]//Rival I. Ordered Sets. Dordrecht-Boston: Reidel Publishing Company, 1982: 445-470.

[16] Qi J.J., Wei L, Yao Y.Y. Three-Way Formal Concept Analysis [C]//Miao D, Pedrycz W, Ślȩzak D, et al. Proceedings of 2014 International Conference on Rough Sets and Knowledge Technology (LNCS 8818). Springer International Publishing, 2014: 732-741.

[17] Qi J.J., Qian T, Wei L. The connections between three-way and classical concept lattices [J]. Knowledge-Based Systems, 2016, 91: 143-151.

The Connection between Orthopairs and Orthogonal Vectors

ZHU Xiaomin,QI Jianjun*

(School of Computer Science ＆ Technology, Xidian University, Xi'an, 710071)

Orthopairs express the orthogonality between sets, and orthogonal vectors express the orthogonality between vectors, so they are similar in a way, but so far there is no study into the matter. For this problem, on the basis of definition of orthopairs, some properties of orthopairs are given firstly. Then the concept of orthogonal set group and orthogonal relation system are proposed, based on which, the relationship between orthogonal relation system and information system (formal context) are established respectively. Creating a mapping between the vector and set to make an arbitrary subset of set correspond to only one Boolean vector, and on this basis the orthogonal relation system is constructed, finally, two one-to-one mappings, from orthopairs to orthogonal vectors and from orthogonal set group to orthogonal vector group are established.

orthopairs; orthogonal vectors; orthogonal set group; orthogonal relation system

1672-9129(2016)01-00022-06

TP391

A

2016-06-29

2016-07-19

国家自然科学基金项目(11371014，11071281)，陕西省自然科学基础研究计划资助项目（项目批准号2014JM8306）。

朱晓敏，女，1993年出生，硕士研究生，主要研究方向为三支概念分析。通讯作者简介：祁建军，男，1970年出生，博士，副教授，主要研究方向为三支概念分析、概念格、三支决策、粒计算等.

(*通信作者电子邮箱：qijj@mail.xidian.edu.cn)