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

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

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

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

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

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

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

7、順序取決于它們右邊界的 位置;如果區(qū)間x和y的右邊界的位置相同，則x和y的先后順序取決于它們左邊界的位置。 表達(dá)式xSy表示區(qū)間x “幾乎”在區(qū)間y的后面，也就是說，區(qū)間x中至少有一個(gè)數(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ù)的特點(diǎn)和實(shí) 際用途，來確定所使用區(qū)間型數(shù)據(jù)排序方法。區(qū)間中心和區(qū)間長度排序法最簡單的區(qū)間型數(shù)據(jù)的比較方法是根據(jù)區(qū)間的中心值(期望值)和區(qū)間長度進(jìn)行排序。l (x) + r (x) 每個(gè)區(qū)間的中心值(期望值)和區(qū)間長度計(jì)算如公式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ìn)行排序；如果中心值相同，則可以根據(jù) 區(qū)間長度推算左右邊界值，進(jìn)而應(yīng)用方法(1)和(2)判斷。3、總結(jié)以上三種方法中，我們認(rèn)為區(qū)

9、間中心和區(qū)間長度排序法是最直觀和系統(tǒng)的。理由是，由 區(qū)間的中心值和區(qū)間長度，我們可以推斷出區(qū)間的左邊界值、右邊界值，進(jìn)而可以判斷區(qū)間 之間的嚴(yán)格優(yōu)先、弱優(yōu)先和無優(yōu)先關(guān)系，并運(yù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