《区间型数据排序方法及其比较》由会员分享，可在线阅读，更多相关《区间型数据排序方法及其比较（3页珍藏版）》请在装配图网上搜索。
1、区间型数据排序方法及其比较徐欣信息系统工程重点实验室，南京210007张桂林信息系统工程重点实验室，南京210007摘要：本文针对排序任务，总结了几种比较常用的区间型数据排序方法，并对其进行了比较 和归纳。优先排序法、左边界和右边界排序法可以看作区间中心和区间长度排序法的特殊情 况。1、背景介绍由于客观事物的复杂性和不确定性，以及人类认识的模糊性，目标类型的特征指标测 量不到精确的数值。在许多实际应用中1，2，数据点(数据对象)是被粗略描绘的，而 不再局限于传统的数据结构，如连续型、离散型(枚举型)和序数型。区间型数据就是其中 一类更为复杂的表达某种不确定性的变量结构。在符号数据分析(symb
2、olic data analysis) 中，变量就可以是区间型的。比如，其变量可以是用信任区间所表示。采集微阵列数据的时 候，由于实验条件有很多的干扰因素，相同的实验通常有一些重复数据。这就使得我们可以 用包含相关重复数据的最小超矩阵(hyper-rectangle)来描述。再如，我们可以用最低和最 高温度组成的区间来表示某一天的温度。在数学上，这些不确定区间可以表示为一个名义数 据矩阵(nominal data matrix)和一个同样大小的表示相应标准化误差和界限的矩阵来表示。 这就是所谓的数据的区间型矩阵模型(interval matrix model)。2、常用区间型数据的排序方法在实
3、践应用中，如基于区间型数据来构建决策树构建2，区间型解释变量必须首先进 行排序，不然难以运用，如运用KS准则和Gini准则构建决策树。目前，区间型数据的排 序方法并不存在一个确定的规范和标准。关于区间型数据的定义以及表示的有关方法如下。假设Q是所有样本的集合，w是Q中 的样本。我们把变量Y (w)=以,P , Vw eQ称为一个区间型变量，其中a和p是两个实数，并且a p。也就是说，每个样本在Y变量上是一个实数的闭合区间。我们可以用尤=/3),r3)来表示这样的一个区间，其中l表示左边界，r表示右边界，并且13) r3)。区间型数据的排序方法主要有下面几种。(1) 优先排序法区间型数据的比较具
4、有反自反性和传递性。假设有两个区间尤=/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的后面)。对于有相交部分的区间x和y，文献3提出了 “优先”(preference)概念。该文作者定 义了三种二元关系：P (严格优先，strict preference)、Q (弱优先，weak preference)和I (无 优先，indifference)。对于一个有限的区间型数据集合A,文献3定义了对A内的元素x和 y进行优先
5、比较的必要和充分条件：如果一个区间 x完全在另一区间y的右侧，即r(y) 13)，我们说x获得严格优先P；如果区间x完全被包含在区间y之内，我们说x获得无优先I；如果区间x在区间y的右边，但是x和y的交集不为空，我们称x获得弱优 先Q。图1给出了区间型比较中，xy，或者说x相对y获得严格优先的一个例子。这里， x和y分别表示一个时间区间变量，而区间x在区间y开始之前就已经结束了。图1区间型数据比较xy(2) 左边界和右边界排序法对于没有相交部分的区间型元素，根据文献3和其他文献中提出的上述原则，我们能 够严格确定区间型集合A内所有元素之间的顺序。然而，如果集合A的元素之间存在相交 关系，我们则
6、不能对集合A中的元素严格确定一个顺序。因为这个原因，文献2并没有完 全赞同以上介绍的区间型数据比较方法。文献2给出了一个严格确定区间型数据集合A内所有元素顺序的方法。运用该方法的 排序准则具备反自反性和传递性。具体包括两个方案，根据左边界排序和根据右边界排序。a. 根据左边界排序如果区间x和y的左边界的位置是不相同的，则x和y的先后顺序取决于它们左边界的 位置;如果区间x和y的左边界的位置相同，则x和y的先后顺序取决于它们右边界的位置。表达式xIy表示区间x “几乎”在区间y的前面，也就是说，区间x中至少有一个数值是小 于等于区间y中的任何数值的。b. 根据右边界排序如果区间x和y的右边界的位
7、置是不相同的，则x和y的先后顺序取决于它们右边界的 位置;如果区间x和y的右边界的位置相同，则x和y的先后顺序取决于它们左边界的位置。 表达式xSy表示区间x “几乎”在区间y的后面，也就是说，区间x中至少有一个数值是大 于等于区间y中的任何数值的。烦 l(y)r(y)r(x)图2 xIy并且xSy的例子图2的例子中，区间y被完全包含在区间x的内部，根据关系I，区间x “几乎”在区 间y的前面，即xIy ；根据关系S，区间x “几乎”在区间y的后面，即xSy。一般来说， 如果区间x “几乎”在区间y的前面，则我们也可能得出区间y “几乎”在区间x的后面 的结论。I和S的关系主要取决于这些区间是
8、否互相包含。使用者应该根据数据的特点和实 际用途，来确定所使用区间型数据排序方法。(3) 区间中心和区间长度排序法最简单的区间型数据的比较方法是根据区间的中心值(期望值)和区间长度进行排序。l (x) + r (x) 每个区间的中心值(期望值)和区间长度计算如公式center =(1)和span _ length = r (x) -1 (x)(2)所示：1 (x) + r (x)center = (1)2span _ length = r(x) -1 (x)(2)例如，区间型数据可以根据区间中心值的大小进行排序；如果中心值相同，则可以根据 区间长度推算左右边界值，进而应用方法(1)和(2)判断
9、。3、总结以上三种方法中，我们认为区间中心和区间长度排序法是最直观和系统的。理由是，由 区间的中心值和区间长度，我们可以推断出区间的左边界值、右边界值，进而可以判断区间 之间的严格优先、弱优先和无优先关系，并运用左边界和右边界排序法判断。优先排序法、 左边界和右边界排序法可以看作区间中心和区间长度排序法的特殊情况。1 Robust Classification with Interval Data，Laurent El Ghaoui，Gert R.G. Lanckriet and Georges Natsoulis，Report，UCB/CSD-03-1279，2003。2 Cherif Mballo and Edwin Diday, Decision trees on interval valued variables, the Electronic Journal of Symbolic Data Analysis, Vol. 3, 2005。3 TSOUKIAS, A.， THE, N. A.， Numerical representation of PQI interval orders， LAMSADE Universite Paris Dauphine， 2001， 184,1-27。
区间型数据排序方法及其比较
