區(qū)間型數(shù)據(jù)排序方法及其比較

1、區(qū)間型數(shù)據(jù)排序方法及其比較徐欣信息系統(tǒng)工程重點實驗室，南京210007張桂林信息系統(tǒng)工程重點實驗室，南京210007摘要：本文針對排序任務(wù)，總結(jié)了幾種比較常用的區(qū)間型數(shù)據(jù)排序方法，并對其進行了比較 和歸納。優(yōu)先排序法、左邊界和右邊界排序法可以看作區(qū)間中心和區(qū)間長度排序法的特殊情 況。1、背景介紹由于客觀事物的復(fù)雜性和不確定性，以及人類認識的模糊性，目標類型的特征指標測 量不到精確的數(shù)值。在許多實際應(yīng)用中1，2，數(shù)據(jù)點(數(shù)據(jù)對象)是被粗略描繪的，而 不再局限于傳統(tǒng)的數(shù)據(jù)結(jié)構(gòu)，如連續(xù)型、離散型(枚舉型)和序數(shù)型。區(qū)間型數(shù)據(jù)就是其中 一類更為復(fù)雜的表達某種不確定性的變量結(jié)構(gòu)。在符號數(shù)據(jù)分析(symb

2、olic data analysis) 中，變量就可以是區(qū)間型的。比如，其變量可以是用信任區(qū)間所表示。采集微陣列數(shù)據(jù)的時 候，由于實驗條件有很多的干擾因素，相同的實驗通常有一些重復(fù)數(shù)據(jù)。這就使得我們可以 用包含相關(guān)重復(fù)數(shù)據(jù)的最小超矩陣(hyper-rectangle)來描述。再如，我們可以用最低和最 高溫度組成的區(qū)間來表示某一天的溫度。在數(shù)學上，這些不確定區(qū)間可以表示為一個名義數(shù) 據(jù)矩陣(nominal data matrix)和一個同樣大小的表示相應(yīng)標準化誤差和界限的矩陣來表示。 這就是所謂的數(shù)據(jù)的區(qū)間型矩陣模型(interval matrix model)。2、常用區(qū)間型數(shù)據(jù)的排序方法在實

3、踐應(yīng)用中，如基于區(qū)間型數(shù)據(jù)來構(gòu)建決策樹構(gòu)建2，區(qū)間型解釋變量必須首先進 行排序，不然難以運用，如運用KS準則和Gini準則構(gòu)建決策樹。目前，區(qū)間型數(shù)據(jù)的排 序方法并不存在一個確定的規(guī)范和標準。關(guān)于區(qū)間型數(shù)據(jù)的定義以及表示的有關(guān)方法如下。假設(shè)Q是所有樣本的集合，w是Q中 的樣本。我們把變量Y (w)=以,P , Vw eQ稱為一個區(qū)間型變量，其中a和p是兩個實數(shù)，并且a p。也就是說，每個樣本在Y變量上是一個實數(shù)的閉合區(qū)間。我們可以用尤=/3),r3)來表示這樣的一個區(qū)間，其中l(wèi)表示左邊界，r表示右邊界，并且13) r3)。區(qū)間型數(shù)據(jù)的排序方法主要有下面幾種。優(yōu)先排序法區(qū)間型數(shù)據(jù)的比較具有反自反

4、性和傳遞性。假設(shè)有兩個區(qū)間尤=/3),r(W和y = l(y),r(y)，若x=y則意味著l(x) = l(y)，并且r(x) = r(y)。一些學者認為，當且僅 當r(x) V l(y)的時候，xy(x在y的前面)；同理，當且僅當r(y) y(x 在y的后面)。對于有相交部分的區(qū)間x和y，文獻3提出了 “優(yōu)先”(preference)概念。該文作者定 義了三種二元關(guān)系：P (嚴格優(yōu)先，strict preference)、Q (弱優(yōu)先，weak preference)和I (無 優(yōu)先，indifference)。對于一個有限的區(qū)間型數(shù)據(jù)集合A,文獻3定義了對A內(nèi)的元素x和 y進行優(yōu)先比較的必

5、要和充分條件：如果一個區(qū)間 x完全在另一區(qū)間y的右側(cè)，即r(y) 13)，我們說x獲得嚴格優(yōu)先P；如果區(qū)間x完全被包含在區(qū)間y之內(nèi)，我們說x獲得無優(yōu)先I；如果區(qū)間x在區(qū)間y的右邊，但是x和y的交集不為空，我們稱x獲得弱優(yōu) 先Q。圖1給出了區(qū)間型比較中，xy，或者說x相對y獲得嚴格優(yōu)先的一個例子。這里， x和y分別表示一個時間區(qū)間變量，而區(qū)間x在區(qū)間y開始之前就已經(jīng)結(jié)束了。圖1區(qū)間型數(shù)據(jù)比較xy左邊界和右邊界排序法對于沒有相交部分的區(qū)間型元素，根據(jù)文獻3和其他文獻中提出的上述原則，我們能 夠嚴格確定區(qū)間型集合A內(nèi)所有元素之間的順序。然而，如果集合A的元素之間存在相交 關(guān)系，我們則不能對集合A中的

6、元素嚴格確定一個順序。因為這個原因，文獻2并沒有完 全贊同以上介紹的區(qū)間型數(shù)據(jù)比較方法。文獻2給出了一個嚴格確定區(qū)間型數(shù)據(jù)集合A內(nèi)所有元素順序的方法。運用該方法的 排序準則具備反自反性和傳遞性。具體包括兩個方案，根據(jù)左邊界排序和根據(jù)右邊界排序。根據(jù)左邊界排序如果區(qū)間x和y的左邊界的位置是不相同的，則x和y的先后順序取決于它們左邊界的 位置;如果區(qū)間x和y的左邊界的位置相同，則x和y的先后順序取決于它們右邊界的位置。表達式xIy表示區(qū)間x “幾乎”在區(qū)間y的前面，也就是說，區(qū)間x中至少有一個數(shù)值是小 于等于區(qū)間y中的任何數(shù)值的。根據(jù)右邊界排序如果區(qū)間x和y的右邊界的位置是不相同的，則x和y的先后

7、順序取決于它們右邊界的 位置;如果區(qū)間x和y的右邊界的位置相同，則x和y的先后順序取決于它們左邊界的位置。 表達式xSy表示區(qū)間x “幾乎”在區(qū)間y的后面，也就是說，區(qū)間x中至少有一個數(shù)值是大 于等于區(qū)間y中的任何數(shù)值的。煩 l(y)r(y)r(x)圖2 xIy并且xSy的例子圖2的例子中，區(qū)間y被完全包含在區(qū)間x的內(nèi)部，根據(jù)關(guān)系I，區(qū)間x “幾乎”在區(qū) 間y的前面，即xIy ；根據(jù)關(guān)系S，區(qū)間x “幾乎”在區(qū)間y的后面，即xSy。一般來說， 如果區(qū)間x “幾乎”在區(qū)間y的前面，則我們也可能得出區(qū)間y “幾乎”在區(qū)間x的后面 的結(jié)論。I和S的關(guān)系主要取決于這些區(qū)間是否互相包含。使用者應(yīng)該根據(jù)數(shù)

8、據(jù)的特點和實 際用途，來確定所使用區(qū)間型數(shù)據(jù)排序方法。區(qū)間中心和區(qū)間長度排序法最簡單的區(qū)間型數(shù)據(jù)的比較方法是根據(jù)區(qū)間的中心值(期望值)和區(qū)間長度進行排序。l (x) + r (x) 每個區(qū)間的中心值(期望值)和區(qū)間長度計算如公式center =(1)和span _ length = r (x) -1 (x)(2)所示：1 (x) + r (x)center = (1)2span _ length = r(x) -1 (x)(2)例如，區(qū)間型數(shù)據(jù)可以根據(jù)區(qū)間中心值的大小進行排序；如果中心值相同，則可以根據(jù) 區(qū)間長度推算左右邊界值，進而應(yīng)用方法(1)和(2)判斷。3、總結(jié)以上三種方法中，我們認為區(qū)

9、間中心和區(qū)間長度排序法是最直觀和系統(tǒng)的。理由是，由 區(qū)間的中心值和區(qū)間長度，我們可以推斷出區(qū)間的左邊界值、右邊界值，進而可以判斷區(qū)間 之間的嚴格優(yōu)先、弱優(yōu)先和無優(yōu)先關(guān)系，并運用左邊界和右邊界排序法判斷。優(yōu)先排序法、 左邊界和右邊界排序法可以看作區(qū)間中心和區(qū)間長度排序法的特殊情況。Robust Classification with Interval Data，Laurent El Ghaoui，Gert R.G. Lanckriet and Georges Natsoulis，Report，UCB/CSD-03-1279，2003。Cherif Mballo and Edwin Diday, Decision trees on interval valued variables, the Electronic Journal of Symbolic Data An