正交對與正交向量的關(guān)系

朱曉敏,祁建軍

?

正交對與正交向量的關(guān)系

朱曉敏,祁建軍*

西安電子科技大學(xué)計算機學(xué)院，西安 710071

正交對表示集合之間的正交性，正交向量表示向量之間的正交性，它們在一定程度上具有相似性，但目前尚無關(guān)于這一問題所展開的研究。針對此問題，以正交對的基本定義為基礎(chǔ)給出正交對的基本性質(zhì)，提出正交集合組以及正交關(guān)系系統(tǒng)的概念，建立信息系統(tǒng)以及形式背景與正交關(guān)系系統(tǒng)的聯(lián)系。構(gòu)造集合到向量的映射，使得集合的任意子集都有唯一一個布爾向量與之對應(yīng)，根據(jù)此映射關(guān)系構(gòu)建正交關(guān)系系統(tǒng)，進而在正交對與正交向量之間以及正交集合組與正交向量組之間建立一一對應(yīng)關(guān)系。

正交對；正交向量；正交集合組；正交關(guān)系系統(tǒng)

引言

正交向量表示向量之間的正交性，在歐氏空間中表現(xiàn)為相互垂直。正交向量的發(fā)展已相對成熟，向量正交性已得到廣泛應(yīng)用[1-3]，并且在正交性與向量空間性質(zhì)關(guān)系的研究中得到了很多重要的結(jié)論。

Ciucci于2011年提出正交對的概念[4]，針對粗糙集，區(qū)間集，陰影集等不確定性集合建立正交對模型，并在正交對的基礎(chǔ)上定義不同偏序關(guān)系。進而研究了正交對在不確定性集合上的應(yīng)用，如基于正交對處理不完善信息[5,6]，提出正交對于粒計算方面的應(yīng)用研究[7]。

正交對在很多領(lǐng)域都有體現(xiàn)，比如在機器學(xué)習(xí)[8]中對數(shù)據(jù)集進行分類或者對大量的元素進行聚類時[9]，最終得到的各個子集可相互構(gòu)成正交對；在三支決策理論[10]中，各個決策集之間也可構(gòu)成正交對。

正交向量表示向量之間的正交關(guān)系，而正交對表示集合之間的正交關(guān)系，它們都表示對象之間的正交性，具有一定的相似性。本文借鑒正交向量的研究方法，對正交對展開研究。事實上，正交向量的部分研究是基于向量可量化的特性，為了將正交向量的性質(zhì)應(yīng)用于正交對，首先以Ciucci提出的正交對的概念為基礎(chǔ)給出正交對的相關(guān)性質(zhì)，并首次提出正交集合組以及正交關(guān)系系統(tǒng)的概念，根據(jù)正交對和正交向量都具有的正交性，構(gòu)造集合與向量之間的映射，在此基礎(chǔ)上構(gòu)建相應(yīng)的正交關(guān)系系統(tǒng)，從而建立起正交對與正交向量之間的聯(lián)系，進而量化正交對，并在此基礎(chǔ)上給出一些相關(guān)結(jié)論。

1 預(yù)備知識

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

定義1.1[11]如果向量，β的內(nèi)積為零，即()=0，那么α，β稱為正交或互相垂直，記為αβ。

由定義可知，若=0，則α與任何向量都正交。

定義1.2[4]設(shè)，為全集的子集，如果，滿足：=，則稱集合與集合正交，集合對(,)稱為正交對。

2 正交對性質(zhì)及基礎(chǔ)研究

2.1 正交對的性質(zhì)

根據(jù)正交對的定義可以得到正交對的基本性質(zhì)。

為了便于表示，將正交對(,)記為，為了與正交向量的表示予以區(qū)分，文中用向量的內(nèi)積為零來表示正交向量。

性質(zhì)2.1.1設(shè)為全集，若,,,，則以下性質(zhì)成立：

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

證明根據(jù)正交對的定義可得出以上性質(zhì)。

下面在正交對性質(zhì)的基礎(chǔ)上對多個集合之間的正交性進行研究。

2.2 正交集合組

正交對表示兩個集合之間的正交性，為了同時表示多個集合之間的正交性，首先給出正交集合組的定義，然后在此基礎(chǔ)上研究正交集合組的相關(guān)性質(zhì)。

定義2.2.1如果非空集合1,2,...,A兩兩正交，那么集合組1,2, ...,A稱為正交集合組。

正交對即=2的正交集合組。

例2.2.1 設(shè)={,,,,,},1={,,}，2={,}，3={}。因為集合組1,2,3滿足12，13，23，所以集合組1,2,3為正交集合組。

下面給出關(guān)于正交集合組之間的正交關(guān)系的定義。

定義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也是一個正交集合組。

證明：根據(jù)定義2.2.1和定義2.2.2可知以上結(jié)論成立。

定理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正交。

根據(jù)向量空間中正交基的概念，我們提出集合的正交基的概念。

定義2.2.3 若正交集合組1,2,...,A滿足：

...A=

則稱1,2,...,A為的正交基。

由定義2.2.3可知，集合的正交基的本質(zhì)就是的劃分。下面在集合劃分的基礎(chǔ)上對集合的正交基展開研究。

推論2.2.2集合的等價類個數(shù)大于等于2的劃分是集合的正交基，反之亦然。

證明由于集合的正交基的元素個數(shù)至少為2，所以這里只討論集合的等價類個數(shù)大于等于2的劃分。

設(shè)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可知，的正交基和的等價類個數(shù)大于等于2的劃分是等價的，它們是不唯一的，且的由不同的非空子集組成的正交基的組數(shù)與子集數(shù)以及||相關(guān)。

性質(zhì)2.2.1 全集(||=)的由(≥ 2)個非空子集組成的正交基的組數(shù)(,)為：

證明該結(jié)論可利用推論2.2.2以及集合劃分知識獲得，(,)實為第二類Stirling數(shù)[12]。

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

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

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

利用推論2.2.2和性質(zhì)2.2.1可得以下結(jié)論。

推論2.2.3 設(shè)集合的所有的正交基的組數(shù)為B()，其中||=。則：

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

例2.2.3集合={,,}的所有的正交基的組數(shù)為：

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

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

定義2.2.4設(shè)1,2,...,A為全集的正交基，如果|A|= 1(=1,2,...,)，則稱正交集合組1,2,...,A為全集的標(biāo)準(zhǔn)正交基。

推論2.2.4集合的標(biāo)準(zhǔn)正交基是唯一的。

證明由性質(zhì)2.2.1和定義2.2.4可知，集合的標(biāo)準(zhǔn)正交基數(shù)為：(,1)=1，其中||=。所以該推論成立。

性質(zhì)2.2.2若正交集合組1,2,...,A為全集的標(biāo)準(zhǔn)正交基，則=||。

定理2.2.2集合中的任意子集都可由集合的標(biāo)準(zhǔn)正交基通過集合運算表示出來。

證明設(shè)集合為集合的一個子集，={1,2,...,a}，1,2,...,A為集合的標(biāo)準(zhǔn)正交基，1={1}，2={a}，...，A={a}，則集合可由標(biāo)準(zhǔn)正交基表示如下：

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

其中：

例2.2.4 設(shè)={,,,,}，={,,}，集合的標(biāo)準(zhǔn)正交基為：1={}，2={}，3={}，4={}，5={}，則子集可由全集的標(biāo)準(zhǔn)正交基表示如下：

={,,}

=134

3 正交關(guān)系系統(tǒng)

為了同時表達出正交對之間以及正交對與正交向量之間的聯(lián)系，我們首次提出正交關(guān)系系統(tǒng)的定義。

定義3.1 設(shè)()為集合的冪集，若在()上存在一對映射，使得：()，()，()與()正交。則稱=(,,)為正交關(guān)系系統(tǒng)。

由以上定義可知，通過改變正交關(guān)系系統(tǒng)中和的映射關(guān)系，可以分別表示出集合與集合之間以及集合與向量之間的正交關(guān)系。性質(zhì)3.1給出具體描述。

性質(zhì)3.1 設(shè)(,,)為正交關(guān)系系統(tǒng)。為集合，,()，()與()正交。則：

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

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

例3.1 設(shè)={,,,}，定義映射和映射滿足：=，=，其中為恒等映射。

所以，=(,,) 為正交關(guān)系系統(tǒng)。

粗糙集理論中的信息系統(tǒng)與三支概念分析中的形式背景也可以表示為正交關(guān)系系統(tǒng)的形式。

例3.2在粗糙集理論[13]中使用信息系統(tǒng)(,,,)同時表示對象集，屬性集，屬性值域以及對象與屬性之間的映射關(guān)系。表3.1為信息系統(tǒng)實例。

表3.1 信息系統(tǒng)(U,Q,V,f)

為上的一種等價關(guān)系。若,，(,)，則表明,是不可區(qū)分的。根據(jù)不可區(qū)分關(guān)系定義集合的下近似集，上近似集和邊界集，具體如下：

*()={:()}

*()表示根據(jù)現(xiàn)有知識可以判斷一定屬于的對象所組成的最大集合。

集合關(guān)于的上近似集為：

*()={:()}

*()表示可能屬于的對象組成的最小集合。

集合關(guān)于的邊界集為：

()=*()-*().

在粗糙集理論中習(xí)慣利用圖3.1的形式表達上下近似集之間的關(guān)系。

圖3.1 粗糙集上下近似

由圖3.1可知，*()與*()-*()是正交的，而正交關(guān)系系統(tǒng)就是表示兩個對象之間具有的正交關(guān)系，所以可以利用正交關(guān)系系統(tǒng)表示圖3.1。

下面基于信息系統(tǒng)以及不可區(qū)分關(guān)系構(gòu)造正交關(guān)系系統(tǒng)。

令映射1，2滿足：

1()=*()，

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

則(,1,2)為正交關(guān)系系統(tǒng)。

正交關(guān)系系統(tǒng)(,1,2)同時表達了定義在上的映射關(guān)系以及*()和*()-*()之間具有的正交關(guān)系。

例3.3 在形式概念分析(FCA)[14]和三支概念分析(TWCA)[15,16]中利用形式背景(,,)同時表示屬性集，對象集，以及二者之間的二元關(guān)系，表3.2是具體的形式背景。

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

二元關(guān)系體現(xiàn)的是對象與屬性之間的“具有”關(guān)系。若，，R表示對象具有屬性。根據(jù)對象與屬性之間的“具有”關(guān)系，定義不同的映射。

FCA中正算子[15]，表示對象子集與屬性子集之間的“具有”關(guān)系：

其中，

正算子將屬性集分成了互不相交的兩部分：X*和U-X*，三支算子將屬性集分成了互不相交的三部分：Y*，和U-Y*-，即X*與U-X*，Y*與都具有正交關(guān)系，但在FCA（TWCA）中并沒有顯示地表示出它們之間具有的正交關(guān)系。下面利用正交關(guān)系系統(tǒng)的形式同時表示對象集與屬性集之間的映射關(guān)系以及映射象集中具有的正交關(guān)系。

基于形式背景以及對象集與屬性集之間的“具有”關(guān)系構(gòu)造正交關(guān)系系統(tǒng)。

令映射1，2滿足：

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

映射1，2滿足：

1()=*，2()=

則(,1,2)，(,1,2)均為正交關(guān)系系統(tǒng)。

相應(yīng)地，可以根據(jù)從屬性集到對象集的映射關(guān)系構(gòu)造出相應(yīng)的正交關(guān)系系統(tǒng)。方法同上，這里不給出詳述。

綜上可知，利用正交關(guān)系系統(tǒng)可同時表示出對象集與屬性集之間具有的映射關(guān)系以及對象集之間以及屬性集之間具有的正交關(guān)系。

4 正交對與正交向量

由于正交對和正交向量都表示對象之間的正交性，可根據(jù)此特性建立起正交對與正交向量之間的聯(lián)系。

4.1正交對與正交向量的聯(lián)系

正交對和正交向量在一定程度上具有相似性，構(gòu)造集合與向量之間的相互對應(yīng)關(guān)系進而建立正交對與正交向量之間的聯(lián)系。

定義4.1設(shè)={1,2,...,a}。構(gòu)造從的冪集到向量空間的映射：()R，()，()=[1,2,...,x]，其中：

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

綜上可知，映射為雙射。

4.2 正交關(guān)系系統(tǒng)的建立

根據(jù)定義4.1建立正交關(guān)系系統(tǒng)。進而表示出正交對與正交向量之間的聯(lián)系。

定理4.2.1=(,,)為正交關(guān)系系統(tǒng)。

證明 設(shè)={1,2,...,a}，為的任意子集，=，設(shè)：

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

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

即： ((),())=0，根據(jù)定義定義3.1可知，=(,,)為正交關(guān)系系統(tǒng)。

事實上，通過映射可以將集合量化，從而可以將正交向量中的部分性質(zhì)應(yīng)用于正交對，結(jié)合正交對和正交向量共同具有的正交性，可以得出以下定理。

證明 設(shè)={1,2,...,a}，={1,2,...,

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

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

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

((),())=0

即

例4.2.1 設(shè)={,,,,,}，={,}，={,,}，，根據(jù)映射的定義可知：

()=[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可知，當(dāng)判斷兩個較大的集合是否互斥時，不需要對兩個集合中的元素進行一一比較?？芍苯痈鶕?jù)映射將集合轉(zhuǎn)化為兩個布爾向量，然后對其進行內(nèi)積運算，根據(jù)運算結(jié)果判斷兩個集合是否互斥。

4.3 正交集合組與正交向量組的聯(lián)系

映射建立了正交對與正交向量的一一對應(yīng)關(guān)系。同樣地，根據(jù)映射可以建立起正交集合組和正交向量組的對應(yīng)關(guān)系。

推論4.3.1設(shè)1,2,..,()，1,2,...,A為正交集合組的充分必要條件為：(1),(2),...,(A)為正交向量組。

證明 由定理3.2.1可知，

((A),(A))=0

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

再根據(jù)定義1.5和2.2.1可知，1,2,...,A為正交集合組的充分必要條件為：(1),(2),...,(A)為正交向量組。

推論4.3.2設(shè)1,2,...,()，若1,2,...,A為正交集合組，則(1),(2),...,(A)線性無關(guān)。

證明 由推論4.3.1可知，(1),(2),...,(A)為正交向量組，又因為正交向量組是線性無關(guān)的，所以可得該推論。

例4.3.2 設(shè)={,,,}，1={,}，2={}，3={}，集合組1,2,3為正交集合組。相應(yīng)地，

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

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

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

由線性無關(guān)的定義可知，(1),(2),(3)是線性無關(guān)的。

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

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

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

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

由線性無關(guān)的定義可知，向量組(1),(2),(3),(4)是線性無關(guān)的。又根據(jù)映射的定義可知：

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)線性無關(guān)。

證明 由根據(jù)推論2.2.1可知，1,2,...,A,1,2,...,B是一個正交集合組。又由定理3.2.2可知，(1),(2),...,(A),(1),(2),...,(B)線性無關(guān)。

定理4.3.31,2,...,A為全集的標(biāo)準(zhǔn)正交基的充分必要條件是(1),(2),...,(A)為R的標(biāo)準(zhǔn)正交基。

證明 設(shè)={1,2,...,a}，1,2,...,A為全集的標(biāo)準(zhǔn)正交基，不妨設(shè)A={a}，1≤≤。

必要性：

根據(jù)映射的定義可得：

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

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

...

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

根據(jù)歐氏空間的標(biāo)準(zhǔn)正交基的定義可知，

(1),(2),...,(A)為R的標(biāo)準(zhǔn)正交基。

充分性：

由(1),(2),...,(A)為R的標(biāo)準(zhǔn)正交基可得：

((A),(A))=0

所以，1,2,...,A為正交集合組，又因為

|A|= 1(=1,2,...,)，所以，1,2,...,A為全集的標(biāo)準(zhǔn)正交基。

5 結(jié)論

本文針對正交對進行研究，并在正交對的基礎(chǔ)上給出了正交集合組的定義以及相關(guān)性質(zhì)，為了建立正交對與正交向量之間的聯(lián)系提出正交關(guān)系系統(tǒng)的概念。構(gòu)造集合到向量的映射，建立相應(yīng)的正交關(guān)系系統(tǒng)并在此基礎(chǔ)上給出正交對與正交向量之間以及正交集合組和正交向量組之間的聯(lián)系。事實上，由于正交向量和正交對的相似性，由前人得出的許多關(guān)于正交向量的性質(zhì)對于正交對也是適用的，并且在數(shù)據(jù)分析中，許多算法中出現(xiàn)的集合都可以構(gòu)成正交對，比如決策樹，神經(jīng)網(wǎng)絡(luò)等，所以針對正交對的研究具有很大的意義。未來我們將針對此問題進行進一步深入的研究。

[1] 王靜,馬方明. 基于向量正交性的組播密鑰管 理方案[J]. 計算機工程, 2013, v. 39; No. 42606: 162-165.

[2] 林偉,孟凡榮,王志曉. 基于概念特征的語義文本分類[J].計算機工程與應(yīng)用, 2011, v. 47; No. 73128: 139-142.

[3] 孔萬增,孫志海,楊燦,戴國駿,孫昌思核. 基于本 征間隙與正交特征向量的自動譜聚類[J]. 電子學(xué)報, 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] 北京大學(xué)數(shù)學(xué)系幾何與代數(shù)教研室前代數(shù) 小組編王萼芳,石生明修訂. 高等代數(shù) 第三版[M]. 北京: 高等教育出版社, 2003. 120-366.

[13] 姜建國,岳建國. 組合數(shù)學(xué)[M]. 2版. 西安: 西安電子科技大學(xué)出版社, 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

國家自然科學(xué)基金項目(11371014，11071281)，陜西省自然科學(xué)基礎(chǔ)研究計劃資助項目（項目批準(zhǔn)號2014JM8306）。

朱曉敏，女，1993年出生，碩士研究生，主要研究方向為三支概念分析。通訊作者簡介：祁建軍，男，1970年出生，博士，副教授，主要研究方向為三支概念分析、概念格、三支決策、粒計算等.

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