区间型数据排序方法及其比较.doc

区间型数据排序方法及其比较徐欣信息系统工程重点实验室，南京 210007张桂林信息系统工程重点实验室，南京 210007摘要：本文针对排序任务，总结了几种比较常用的区间型数据排序方法，并对其进行了比较和归纳。优先排序法、左边界和右边界排序法可以看作区间中心和区间长度排序法的特殊情况。1、背景介绍由于客观事物的复杂性和不确定性，以及人类认识的模糊性，目标类型的特征指标测量不到精确的数值。在许多实际应用中 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 Analysis, Vol. 3, 2005。，数据点（数据对象）是被粗略描绘的，而不再局限于传统的数据结构，如连续型、离散型（枚举型）和序数型。区间型数据就是其中一类更为复杂的表达某种不确定性的变量结构。在符号数据分析（symbolic data analysis）中，变量就可以是区间型的。比如，其变量可以是用信任区间所表示。采集微阵列数据的时候，由于实验条件有很多的干扰因素，相同的实验通常有一些重复数据。这就使得我们可以用包含相关重复数据的最小超矩阵（hyper-rectangle）来描述。再如，我们可以用最低和最高温度组成的区间来表示某一天的温度。在数学上，这些不确定区间可以表示为一个名义数据矩阵（nominal data matrix）和一个同样大小的表示相应标准化误差和界限的矩阵来表示。这就是所谓的数据的区间型矩阵模型（interval matrix model）。2、常用区间型数据的排序方法在实践应用中，如基于区间型数据来构建决策树构建2，区间型解释变量必须首先进行排序，不然难以运用，如运用KS准则和Gini准则构建决策树。目前，区间型数据的排序方法并不存在一个确定的规范和标准。关于区间型数据的定义以及表示的有关方法如下。假设是所有样本的集合，w是中的样本。我们把变量称为一个区间型变量，其中和是两个实数，并且。也就是说，每个样本在Y变量上是一个实数的闭合区间。我们可以用来表示这样的一个区间，其中l表示左边界，r表示右边界，并且。区间型数据的排序方法主要有下面几种。（1） 优先排序法区间型数据的比较具有反自反性和传递性。假设有两个区间和，若x=y则意味着，并且。一些学者认为，当且仅当的时候，xy（x在y的后面）。对于有相交部分的区间x和y，文献 TSOUKIAS, A.，THE, N. A.，Numerical representation of PQI interval orders，LAMSADE Universite Paris Dauphine，2001，184, 1-27。提出了“优先”（preference）概念。该文作者定义了三种二元关系：P（严格优先，strict preference）、Q（弱优先，weak preference）和I（无优先，indifference）。对于一个有限的区间型数据集合A，文献3定义了对A内的元素x和y进行优先比较的必要和充分条件：如果一个区间x完全在另一区间y的右侧，即，我们说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的元素之间存在相交关系，我们则不能对集合A中的元素严格确定一个顺序。因为这个原因，文献2并没有完全赞同以上介绍的区间型数据比较方法。文献2给出了一个严格确定区间型数据集合A内所有元素顺序的方法。运用该方法的排序准则具备反自反性和传递性。具体包括两个方案，根据左边界排序和根据右边界排序。a. 根据左边界排序如果区间x和y的左边界的位置是不相同的，则x和y的先后顺序取决于它们左边界的位置；如果区间x和y的左边界的位置相同，则x和y的先后顺序取决于它们右边界的位置。表达式表示区间x“几乎”在区间y的前面，也就是说，区间x中至少有一个数值是小于等于区间y中的任何数值的。b. 根据右边界排序如果区间x和y的右边界的位置是不相同的，则x和y的先后顺序取决于它们右边界的位置；如果区间x和y的右边界的位置相同，则x和y的先后顺序取决于它们左边界的位置。表达式表示区间x“几乎”在区间y的后面，也就是说，区间x中至少有一个数值是大于等于区间y中的任何数值的。图 2 并且的例子 图 2的例子中，区间y被完全包含在区间x的内部，根据关系I，区间x“几乎”在区间y的前面，即；根据关系S，区间x“几乎”在区间y的后面，即。一般来说，如果区间x“几乎”在区间y的前面，则我们也可能得出区间y“几乎”在区间x的后面的结论。I和S的关系主要取决于这些区间是否互相包含。使用者应该根据数据的特点和实际用途，来确定所使用区间型数据排序方法。（3） 区间中心和区间长度排序法最简单的区间型数据的比较方法是根据区间的中心值（期望值）和区间长度进行排序。每个区间的中心值（期望值）和区间长度计算如公式 （1）和 （2）所示： （1） （2）例如，区间型数据可以根据区间中心值的大小进行排序；如果中心值相同，则可以根据区间长度推算左右边界值，进而应用方法（1）和（2）判断。3、总结以上三种方法中，我们认为区间中心和区