《算法导论》学习总结——快速排序

《算法导论》学习总结——快速排序（精选5篇）

篇1：《算法导论》学习总结——快速排序

冒泡和递归一样，不管大家水平怎么样，基本上都能凑合的写写，快速排序其实主要的也是数据的交换，都算是交换排序，不过快排需要了解分治思想，实现的时候需要递归一下，导致很多时候看快排的时候都看的云里雾里，假设有一个无序的整型数组

索引0123456

数值1532899121736，

①取出0位的15作为基准值，然后倒序从后往前找小于15的，将12赋值给0位;

②从前往后找大于15的将32放置到位置4;

③位置1空出来，然后继续倒序找小于15的，正序找大于15的，最后索引到大3的时候重复以上过程。

冒泡排序

冒泡基本上没有什么好说的，直接看代码吧，新建了Sort类处理排序:

//

//Sort.h

//Algorithm

//www.cnblogs.com/xiaofeixiang

//Created by keso on 15/3/15.

//Copyright (c) 2015年 keso. All rights reserved.

//

#import

@interface Sort : NSObject

@property (nonatomic,strong)NSMutableArray *dataSource;

-(void)bubbleSort:(NSMutableArray*)dataSource;

-(void)quickSort:(NSInteger)start endIndex:(NSInteger)end;

@end

Sort.m中的bubbleSort实现:

//冒泡排序

-(void)bubbleSort:(NSMutableArray*)dataSource{

NSUInteger count=[dataSource count];

for(int i=0;i

for (int j=0; j

if ([dataSource[j] intValue]>[dataSource[j+1] intValue]) {

NSString*temp=dataSource[j];

dataSource[j]=dataSource[j+1];

dataSource[j+1]=temp;

}

}

}

for (NSInteger i=0; i<[dataSource count]; i++) {

NSLog(@”排序--%@“,dataSource[i]);

}

}

冒泡排序比较稳定，但是每次只是移动两个数字比较慢，如果是正序的话时间复杂度是O(n)，如果是逆序的需要弄成正序的，那么事件复杂度O(n*n)，会经过n(n-1)/2次比较，平均事件复杂度O(n*n);

快速排序

快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)，

基本思路如下:

1.先从数组中取出一个数作为基准数值，也可以理解为中间变量。

2.分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

3.再对左右区间重复第二步，直到各区间只有一个数。

快速排序由于排序效率在同为O(n*logn)的几种排序方法中效率较高，因此经常被采用，再加上快速排序思想----分治法也确实实用，也算是出门居家必备的算法了，理解比较好理解，具体的实现能写出来基本上算是理解的，至于更深的就要看工作中实际的操作过程啦。

Sort.h中定义了一个QuickSort方法，还有一个NSMutabArray是为了保存最后的结果的,具体实现:

//快速排序

-(void)quickSort:(NSInteger)start endIndex:(NSInteger)end{

if (start

NSInteger standardValue=[_dataSource[start] intValue];

NSInteger left=start,right=end;

while (start

//从后往前找，如果后面的数值大于基准值，递减

while (startstandardValue) {

end--;

}

//小于基准值的时候，给数组中索引为start赋值

if (start

_dataSource[start]=_dataSource[end];

start=start+1;

}

//从前往后找，如果数值小于基准值，递增

while (start

start++;

}

//大于基准值，给数组中索引为end的数据赋值

if (start

_dataSource[end]=_dataSource[start];

end=end-1;

}

}

//退出的时候值start和end相等

_dataSource[start]=[NSString stringWithFormat:@”%ld“,(long)standardValue];

[self quickSort:left endIndex:end-1];//处理左边

[self quickSort:end+1 endIndex:right];//处理右边

}

}

主函数中的调用如下:

NSMutableArray *data=[[NSMutableArray alloc] initWithObjects:@”10“,@”88“,@”97“,@”33“,@”8“,@”73“,@”18“, nil];

[sort bubbleSort:data];

sort.dataSource=data;

[sort quickSort:0 endIndex:[data count]-1];

for (int i=0; i<[data count]; i++) {

NSLog(@”排序:%@",data[i]);

}

return 0;

代码可能不是最简洁的，但是应该是比较好理解的，如果有问题，随时可以在评论区与我交流~

篇2：快速排序算法的分析与研究

本文在对传统快速排序算法的优点及缺点进行充分分析的基础上，指出影响快速排序的关键因素，提出一种随机化的高效排序方法。它对待排序的数据初态没有任何要求，或者说可以让任何的数据初态在排序时达到均匀分布，从而使任何输入数据达到O(nlog n)的时间复杂度。

1 传统的快速排序算法与分析

1.1 传统的快速排序算法

快速排序算法采用了分治技术，其分治步骤为：首先，问题划分。将求解问题分成若干大小不等的子问题;其次，递归求解。独立地解决这些子问题;最后，合并解。将子问题的解归并成原问题的解。由于快速排序可以采用就地重排，合并解不需要花费时间。因此影响算法的最关键的问题是支点元素的选择方法是否适当，是否可以将问题均等的划分。

传统的快速排序算法是从待排数据两端选取一个元素作为支点元素，其递归快速排序算法QuickSort如下：

对待排元素集S进行排序，最初的调用是QuickSort(S,1,length[S])。而快速排序算法的关键是PARTI-TION过程，它对子元素集S[L..H]进行一趟快速排序或一次划分：

一次划分PARTITION的算法步骤为：

Step1首先定义两个变量i和j，并初始化i=L,j=H;

Step2选取第一个待排元素S[L]作为支点元素，并将支点元赋值给pivot，即执行pivot=S[L];

Step3从j位置开始由后向前比较(j--)，找到第一个小于key(支点元素的关键字)的元素S[j]，交换S[i]与S[j];同时，i++。

Step4从i位置开始由前向后比较(i++)，找到第一个大于key(支点元素的关键字)的S[i],S[i]与S[j]交换;同时，j--。

Step5重复执行Step3,Step4，直到i=j。并将S[i]←pivot，返回i值。

1.2 传统快速排序算法的效率分析

算法的时间开销主要花费在划分PARTITION操作上，对长度为n的数据元素进行一次划分，共需n-1次元素的比较。

(1)最好情况时间复杂度

最好情况下，快速排序的每次划分所选取的支点元素恰好都是当前待排数据的“中值”元素，每次划分的结果为：支点元素的左、右两个子表的长度大致相等，即对半划分。在此情况下，可得知快速排序要做lg n趟划分，时间复杂度为C(n)=O(nlg n)。

(2)最坏情况时间复杂度

最坏情况下，快速排序的每次划分选取的支点元素恰好都是当前待排数据中关键字最小(或最大)的元素，每次划分的结果为：支点左边的子表为空(或右边的子表为空)，而另一个非空的子表中元素个数仅比划分前的待排数据中元素个数少1个。在此情况下，快速排序就要做n-1次划分，而第i次划分开始时区间长度为n-i+1，所需的比较次数为n-i(1≤i≤n-1)，故总的比较次数达到最大值：

如果按上面给出的划分算法，当待排元素集S已按递增有序(或递减有序)排列时，每次取当前待排数据的第1个元素为支点，那么每次划分所取的支点就是当前待排数据中关键字最小(或最大)的记录，则快速排序所需的比较次数达到最多。即当元素基本有序时，快速排序的效率反而很低，不及冒泡排序及插入排序。

(3)平均时间复杂度

尽管快速排序的最坏时间为O(n2)，但就平均性能而言，它是基于关键字比较的内部排序算法中速度最快的，快速排序亦因此而得名。它的平均时间复杂度为O(nlg n)[4]。

在此选择同一量级的堆排序进行了比较测试。在相同的环境下，基于C++语言平台，分以不同规模(100,1 000,10 000,100 000)的随机数作为测试数据集。在程序中根据数据个数的不同产生的随机整型数组，然后分别让不同的排序算法来进行从小到大的排序。这里两种排序算法在相同的输入规模中原始无序数据都是一样的，以此来保证实验的公正性。每个排序算法中加入计数器来记录排序过程中的比较次数，同时利用计时函数得出排序时间。

表1为输入数据规模分别为100,1 000,10 000,100 000时两个算法的排序时间对比。实验结果表明，一般情况下，快速排序的效率的确比堆排序要高。

ms

(4)空间复杂度

快速排序算法是一个递归算法，因此，系统会自动开辟一个栈来辅助算法的执行。最坏情况下，递归树的高度为O(n)，所需附加栈的空间为线性量级O(n)。一般情况下，如图2所示其递归树的高度为O(lg n)，执行算法所需附加栈的空间为对数量级O(lg n)。

2 快速排序算法的改进

影响快速排序算法效率的主要因素是支点元素的选取。若所选择的支点元素应能够将数组S分成大小几乎相等的部分，就能保证快速排序算法的高效性。

假设S由n个不同元素组成，最好的选择方法是选择S中元素的中值作为支点元素。比如，初始元素的关键字为：333,4,11,23,57，要应选择23中值作为支点元素。尽管有些理论上好的算法可以找到待排元素的中值，但由于开销过大使得快速排序无法在实际中得到实用[7]。比如，先对待排序的数据进行统计、求平均来选取出最佳的支点元素，以确保快速排序的每一次划分位置都正好处于待排序序列的正中间。其算法的本质是选取了最合适的支点，但选取合适的支点本身是一个很浪费时间的操作，因此其方法只能在某些特定情况下提高排序效率，而在另一些情况下反而效率低于基本快速排序。

针对快速排序支点元素的选取，能够有效改进排序的效率，而又不额外增加开销的主要有以下两种方法。

第1种方法是“三者取中”的规则[8,9]。普遍使用的方法：首先，比较待排数据中第一、中间和最后一个位置上元素的关键字，取三者之中值为支点元素。其次，在划分开始前将该支点元素和该区间的第1个元素进行交换，此后的划分过程与1.1所给的PARTITION算法完全相同。实践表明，采用三元素取中值的规则只需要几条if语句的判断即可，在时间上、空间上不会增加额外的开销，但结果可以大大改善快速排序在最坏情况下的性能。第2种方法就是本文所提出的随机化快速排序。算法思路：每趟划分选取哪一位置上的元素作为支点不是固定的，而是用随机数产生器Random(l,h)随机选取位于l和h之间的随机数t(l≤t≤h)，用S[t]作为支点元素。这就打破了传统快速排序对数据元素初始输入的依赖，相当于S[l..h]中的元素是随机分布的。

可以看出，随机化的快速排序与一般的快速排序算法差别很小。选择l和h之间中任意一个元素作为支点。只需要将选中的支点元素与第一个位置上的元素互换swap(S[t],S[l])，之后同样调用PARTITION(S,l,h)算法进行划分。随机化之后，算法的时间空间开销没有增加，但性能却得到了改善，尤其是对待排序元素基本有序的情况下，不可能导致最坏情况的发生。可以严格地证明划分的每一步以非常大的概率导致均匀划分，与初始输入分布无关[10]。经实验对比，在元素有序情况下，两种排序算法在规模分别为100,200,500时比较次数的统计情况对比，如表2所示。

同时，算法的随机化不仅仅适用于快速排序，也适用于其他需要数据随机分布的算法。

3 结语

快速排序是一种经典的排序算法，实例验证了在数据分布均匀的情况下，其排序的效率优于同量级nlbn的堆排序。但在一些特殊情形，如待排序数据有序，其效率低于或者远远低于nlbn数量级，甚至蜕变为n2数量级，相对地限制了快速排序的广泛应用。因此，针对影响快速排序关键问题支点元素的选取，提出了一种随机选取支点元素的方法，改进了快速排序对待排元素初态的敏感性，通过实验验证了该算法的正确性和实用性。但是若输入数据中有很多的相同数据，随机化的效果也将直接减弱。

摘要：快速排序是排序算法中性能较好的一种,但存在对数据基本有序的情形下的性能瓶颈问题。为了保证快速排序在任何情况下的高效性,在对快速排序算法的时间效率进行充分的分析的基础上,指出支点元素的选取是影响快速排序算法效率的主要因素。提出了一种随机选择支点元素的快速快排方法,很好地避免了最坏情况的发生。通过实验验证了改进算法的正确性和高效性。

关键词：快速排序算法,支点元素,时间效率,随机化快速排序

参考文献

[1]汤亚玲^,秦锋.高效快速排序算法研究[J].计算机工程^,2011⁽6^):77-79.

^[2^{]刘娜,佟冶.浅析C语言快速排序算法的改进[J].计算机系统应用,2}008⁽1^):113-115.

[3]周建钦.超快速排序[J].计算机工程与应用,2006,42(9):41-42.

[4]连顺金.快速排序的一种改进算法[J].三明学院学报,2009(4):43-45.

[5]宋鸿修.分割方式的多线程快速排序算法[J].计算机应用,2010(9):2374-2378.

[6]庹清.改进的按位拆分快速排序算法[J].计算机应用,2011(1):55-57.

[7]王善坤,陶祯蓉.一种三路划分快速排序的改进算法[J].计算机应用研究,2012(7):2513-2516.

[8]严蔚敏,吴伟民.数据结构[M].北京:清华大学出版社,2008.

[9]秦锋.数据结构[M].合肥:中国科学技术大学出版社,2007.

篇3：基于快速排序算法的文献检索技术

1 文献资料搜索引擎技术特点

当用户以关键词查找信息时,搜索引擎会在数据库中进行搜寻,如果找到与用户要求内容相符的信息,便采用特殊的算法,根据文献中关键词的匹配程度,如出现的次数、频率等计算出各文献的排名等级,然后根据关联度高低,按顺序将这些资源接返回给用户。

与网络搜索引擎不同,因用户需求为数据资料而非网络资源,因此文献检索主要依据为相关关键词、内容的相关度等,对域名、外链等因素考虑较少。可利用关键词匹配算法,计算出各文献特征值,以特征值作为依据,对检索文献排序删选,满足用户需求。为便于理解,该文利用词频和位置加权算法计算特征值,采用快速排序算法进行整理输出,数据库可高效检索出与用户需求匹配程度较高的文献[2]。

2 快速排序算法规则及性能分析

快速排序是由托尼·霍尔于1962年(Tony Hoare)所发展的一种递归排序算法,采用分治的思想。在平均状况下,排序n个项目需Ο(n log )要Ο(n log n)次比较。

其算法规则可表述为:

1) 从数列中挑出一个元素,称为 "基准"(pivot);

2) 所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面,称为分区(partition)操作。如数列[5, 38, 1, 6, 7, 9, 4, 2],以首元素作为基准,经一趟操作后,变为 [2, 3, 4, 1, 5, 7, 9, 6, 8];

3) 递归地(recursive)把小于基准值元素的子数列[2, 3, 4, 1]和大于基准值元素的子数列[7, 9, 6, 8]排序。递归至最终情形,即子数列的长度是0或1。01

在文献检索过程中,根据词频和位置加权算法计算出各文献特征值,特征值构成无序数列,以其为索引,对文献重新整理排序,将匹配程度高的置于顶端,满足用户检索需求。

这一过程为排序操作,传统排序算法,如交换排序、选择排序、插入排序等,平均时间复杂度均为O (n2。如图1所示,为分别采用传统排序算法与快速排序算法,在检索过程中计算时间复杂度的比较。

可以看到快速排序算法在计算时间复杂度方面明显优于传统排序算法,特别在相关文献数目不断增长的情况下,优势体现更为明显。这一点能够很好适应当前各文献检索数据库信息资源迅速扩充的现实情况。

3 算法设计与仿真

首先建立包含十五篇文献的资料库,根据用户需求,随机输入关键词,在此可将关键词视为子串,对各文献进行字符串匹配操作。文献为A串,即目标串,关键词为B串,即模式串。若A串中存在和B相等的子串( 若干连续的字符组成的子序列) ,则匹配成功,,否则,称匹配不成功[3]。

匹配过程如图2所示,将模式串设置为滑动窗口。在第一次匹配过程中,第三个字符出现不相同情况,此时根据KMP算法原则,利用已经得到的部分匹配的结果,将模式串窗口向后滑动一段距离后,继续进行比较[4]。

同时需要考虑关键词匹配成功的具体位置。在文献检索过程中,如在标题匹配成功,要远比在正文部分匹配成功重要。如表1所示,位置设置包括:标题、副标记、关键词、正文,不同位置分别设置权值,在字符匹配的同时进行加权处理,计算出各文献的特征值,特征值应体现出文献的重要性和与用户需求匹配程度这两个关键指标。

基于网页检索Page Rank算法中的学术引文机制[5],当文献1引用到文献2时,就认为文献1投了文献2一票,增加了文献2的重要性,。首先将资料库中资源通过文章参考文献建立链接关系,如图3所示,当输入检索关键词“搜索引擎”,在目标文献的参考文献部分匹配成功,此时不应增加目标文献的重要性指标,应将重要性特征值的增长量赋予文献“搜索引擎及其发展”,即文献2。这一算法设计体现出,被引用次数越多,则该文献权威性越高,特别适用于结构化文档,如期刊数据等。

应充分考虑用户行为反馈,即被下载次数越多的文献,说明该文献的重要性。被下载次数的统计,可设计为一动态投票系统,被下载一次,即进行投票处理,系统累计每篇文献投票次数,形成一个排序系统[6]。

根据以上原则搭建信息检索系统结构,如图4所示,当用户输入需求检索信息后,程序开始启动,分析计算出资源库中各文献7特征值,特征值计算原则为此时文献就会携带关于自身评价的信息,包括权威性、匹配吻合度、受欢迎度等,但仍无序排列。需要以文献特征值为依据,引入快速排序算法,提高系统运行效率,对资源库中文献整理、筛选、输出,使用户优先获得较优良资源。

经特征值算法分析计算,模拟资源库中十五篇文献资料获得各自特征值,分别记录在每篇文献上,如表2所示,但仍处于无序状态,无法提供用户使用,此时快速排序算法开始执行。

快速排序算法的基本出发点是把某个需要解决的庞大问题, 化作若干个在尺寸上小于原问题而在形式上和原问题又完全相同的问题, 层层分解逐次逼近。在排序过程中,引入该思想,可有效提高检索效率。具体执行过程如下所示:

1 [3, 9, 10, 7, 4, 11, 13, 9, 9, 9, 0, 1, 0, 8, 13]

第一次执行,将首篇文献R[1]作为基准,分区操作,特征值大于其的文献列左,其余列右:

2 [0, 1, 0, 3, 4, 11, 13, 9, 9, 9, 7, 10, 9, 8, 13]

第二次执行,将R[5]作为基准,分区操作:

3 [0, 1, 0, 3, 4, 11, 13, 9, 9, 9, 7, 10, 9, 8, 13]

第三次执行,将R[1]作为基准,分区操作:

4 [0, 0, 1, 3, 4, 11, 13, 9, 9, 9, 7, 10, 9, 8, 13]R[6]

第四次执行,将R[6]作为基准,分区操作:

5 [0, 0, 1, 3, 4, 8, 9, 9, 9, 9, 7, 10, 11, 13, 13]

第五次执行,将R[6]作为基准,分区操作:

6 [0, 0, 1, 3, 4, 7, 8, 9, 9, 9, 9, 10, 11, 13, 13]

经过五次操作,排序完成,明显优于传统排序算法O (n2)的时间复杂度。如表[7]3所示,此时资源库形成有续表,可以顺序输出,满足用户检索需求。

4 结束语

伴随近年来文献检索平台信息数量、种类的不断增加、服务需求水平的不断提高,对文献检索算法提出更高的要求。在本检索系统设计思路中,充分参考当前网页搜索引擎中较为普遍应用的位置加权、用户行为反馈、KMP算法和Pagerank算法等设计思路,并结合数字期刊检索的自身特点,增强检索文献的匹配程度、权威性、重要性等综合指标。在提高检索准确率的同时,引入快速排序算法,改善信息处理效率,优化系统性能。

参考文献

[1]张兴华.搜索引擎技术及研究[J].现代情报,2002(2):142.

[2]黄知义,周宁.几类搜索引擎的原理剖析、比较研究及发展趋势探讨[J].图书馆学研究,2005(3):61-62.

[3]李静.字符串的模式匹配算法[J].青岛化工学院学报,2002(2):80.

[4]俞文洋,张连堂,段淑敏.KM P模式匹配算法的研究[J].郑州轻工业学院报,2007(5):65.

[5]黄德才,戚华春.PageRank算法研究[J].计算机工程,2006(2):145-146.

[6]王奇才,宋国新才,邵志清.信息检索中基于链接的网页排序算法[J].华东理工大学学报,2000(5):456.

[7]王海源.分治算法的两种思路和形式[J].上海师范大学学报:自然科学版,2003(1):40-41.

篇4：《算法导论》学习总结——快速排序

1 关键字在特定范围内的快速排序算法（FastSort)

1.1 FastSort排序算法基本思想

为待排序的数据记录分配相应的辅助存储空间，由待排序的关键字直接得到其对应的存储位置，再按存储位置顺序输出数据记录，就直接得到排序效果，其间不需进行任何数据的比较交换。

1.2 FastSort算法描述

1.2.1 数据结构描述

在具体应用时，一般考虑关键字类型为整型的情况，因为对很多实型数据，按照小数点的舍入方式，同样可转换成整型处理。

1.2.2 算法描述

要完成对一个待排序记录表的排序，可采用以下函数，将待排序表作为参数。而在此函数中，只用到了一个很简单的单循环即完成了“排序”操作。

在上面函数中的使用了一个循环对临时表tempTable赋初值，若已知待排序表关键字的范围，则可使用数组的方式，并在定义数组时赋初值，这样，在本函数中即可去掉这个循环。下面的这个函数完成排序关键字的输出。

1.3 实例对比分析

下面以学生成绩(百分制)排序为例，将此算法和几种常见的内部排序算法进行对比分析。

在主程序中，首先定义一个存放成绩数据的对象，并对keyMin,keyMax,eleLen,tmpTable进行初始化：

然后,随机地产生一系列0～100内的数据以代表成绩数据,可用如下程序段实现:

最后分别调用不同的排序算法对这些数据进行排序。由于数据量较少可能导致比较结果不显著，所以，我们对排序数据都进行500000次排序，并且用time()函数分别取得排序开始时间和终止时间，比较结果如表1所示。

由表1可见，在数据量较大时，FastSort的排序速度明显比其他任何一种内部排序算法都要高出很多。下面对此算法的时间复杂度及空间复杂度进行分析。

1.4 算法复杂度对比分析

算法的时间通常以算法中基本操作重复执行的次数来量度，记作：T(n)=O(f(n))

简称时间复杂度。对FastSort算法，T(n)=O(n)。在几种常见内部排序中，冒泡排序和简单选择排序的时间复杂度都是O(n2)，就平均时间而言，快速排序被认为是最好的一种内部排序方法，其平均时间也为Tavg(n)=knlnn[1]。可见FastSort算法在时间效率上明显优越于传统内部排序算法。

空间复杂度作为算法所需存储空间的量度，记作：

S(n)=O(f(n))

其中n为问题的规模(或大小)[1]。与传统内部排序算法相比，FastSort算法在对关键字范围远远小于记录数的一类问题进行处理时将大大节省辅助存储空间。如对1000个学生按成绩(百分制成绩范围：0～100)排序，传统内部排序算法需用1000个记录的辅助存储空间，而FastSort算法只需101个记录的辅助存储空间。只是在处理关键字范围很大，但记录较少一类问题时，本算法存在需消耗较多多余辅助存储空间的缺点。因此FastSort算法最适于处理记录数大于关键字范围的问题。

2 结束语

FastSort算法不需对数据进行任何的比较交换，只是通过输入、输出操作就可实现对数据的排序。对关键字范围远远小于记录数的数据，此算法最为有效。不管是对排序算法的教学，还是对实际问题的处理都有很大的参考应用价值。

参考文献

[1]严蔚敏,等.数据结构(C语言版)[M].北京:清华大学出版社,1997-04.

[2]孟令奎,金先级,张江陵.一种新的并行排序算法研究[J].武汉:华中理工大学学报,1994,22(6).

[3]钱能.C++程序设计教程[M].第二版.北京:清华大学出版社,2005-09.

[4]Knuth D E.The art of computer programming[M].Sorting and Searching.Addison Wesley Publishing Company,Inc.,1973-03:145-158.

篇5：排序学习算法的一般模型研究

一、排序学习的一般前提[3]

设X为给定的样本空间。对任意的样本对, 表示在排序 (优先次序) 上x排在x'之前, 或者说x的排序得分比x'高。函数称为排序 (得分) 函数, 如果。排序学习的目的就是基于经验数据, 设计机器学习算法来找到排序函数f*的一个好的逼近。

给定训练数据集合A, 我们采用有向关系图G= (V, E) 来表示数据间的序关系。同时用表示假设函数集合。详细来说, 关系如下:

1.训练数据

2.图G= (V, E) 的每一个节点对应一个类别Aj。若存在一条从Ai→Aj的边Eij意味着Aj中的所有训练样本比Ai中的排序更高。简言之,

这里描述的排序背景适合于分析和处理许多不同类型的经典排序模型。

二、几种排序模型

本节介绍几种常见的排序学习的目标函数, 基于这些目标函数设计的排序学习算法在经验数据实验中显示了良好的性能。

1. 二划分排序[1]

二划分排序问题是一种经典的排序问题, 这里类别数只有两类。学习的目的就是使两类数据能顺利的区分开来。其对应的优化目标函数为

这里yi表示对应于xi的得分, I (A) 为0-1损失函数, 当A成立时取1, 否则取0。

2. K-划分排序 (详见[2])

在K-划分排序排序问题中, 给定的样本往往具有K个序标。因此, 对应的优化目标函数为二排序优化目标函数的推广, 其表达式如下

虽然基于此目标的推广误差的界已经在[2]中建立, 但是该目标仅适合处理全相关的排序情形, 在实际应用中受到很多限制。

3. 推广的Wilcoxon-Mann-Whitney (W M W) 统计

WMW统计原用于获得分类学习问题大偏差的界, 近来被引入排序学习问题中。推广的W M W定义如下

基于此目标, 一类快速的梯度下降算法在[3]中被提出, 并且在数据实验中显示了良好的性能。然而, 在实际排序问题中, 往往更关注顶端的排序准确性, 因而推广该目标到关注顶端排序问题是很有意义的一个课题。

4. p模排序

在文献[4]中, 作者提出了一种新的优化目标函数, 其优点在于能有效的强调排序问题顶端的排序性能。对应的目标函数定义为:

显然p模排序是基于二排序问题, 其应用范围因此也受到较大限制。

三、排序学习的一般模型

基于以上几种排序优化函数, 提出如下排序学习算法的一般模型:

该目标函数不仅能通过调整p值的大小来强调顶端排序的准确性, 也适合于处理各种排序关系问题, 从而有更广泛的前景。

同时, 从算法的理论分析来看, 通过该模型的研究, 有助于建立排序学习算法推广性能分析的统一理论基础, 为进一步模型选择, 算法设计以及参数选择提供理论指导。

该目标函数与前面几种目标函数的关系总结如下表:

四、小结

排序学习的理论和应用研究是近来机器学习和数据挖掘研究的热点问题之一。如何设计合理的算法模型是排序问题的关键。本文结合已有的模型, 给出了一般条件下的优化目标模型。该模型适用更广泛的应用领域, 且有助于建立排序学习算法统一的理论基础。

摘要：排序学习问题是机器学习与数据挖掘领域近来的研究热点之一。本文通过分析和比较几种排序学习模型, 提出基于这些模型的一般框架, 从而为进一步的算法设计和理论分析奠定基础。

关键词：排序,机器学习,模型选择

参考文献

[1]S.Agarwal, et.al.Generalization bounds forthe area under the ROC curve[J].JMLR, 2005, 6:393-425

[2]S.Rajaram, S.Agarwal.Generalization boundsfor k-partite ranking[J].In NIPS, 2005

[3]V.C.Raykar, et.al.A fast algorithm forlearning a ranking function from large-scaledata sets[J].TPAMI, 2009, 30:1158--1170