正交對與正交向量的關系

朱曉敏,祁建軍

?

正交對與正交向量的關系

朱曉敏,祁建軍*

西安電子科技大學計算機學院，西安 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)