开发者社区> 老朱第八> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

【原创】机器学习之PageRank算法应用与C#实现(2)球队排名应用与C#代码

简介:
+关注继续查看

  在上一篇文章:机器学习之PageRank算法应用与C#实现(1)算法介绍 中,对PageRank算法的原理和过程进行了详细的介绍,并通过一个很简单的例子对过程进行了讲解。从上一篇文章可以很快的了解PageRank的基础知识。相比其他一些文献的介绍,上一篇文章的介绍非常简洁明了。说明:本文的主要内容都是来自“赵国,宋建成.Google搜索引擎的数学模型及其应用,西南民族大学学报自然科学版.2010,vol(36),3”这篇学术论文。鉴于文献中本身提供了一个非常简单容易理解和入门的案例,所以本文就使用文章的案例和思路来说明PageRank的应用,文章中的文字也大部分是复制该篇论文,个人研究是对文章的理解,以及最后一篇的使用C#实现该算法的过程,可以让读者更好的理解如何用程序来解决问题。所以特意对作者表示感谢。如果有认为侵权,请及时联系我,将及时删除处理。

  论文中的案例其实是来源于1993年全国大学生数学建模竞赛的B题—足球队排名问题。

本文原文链接:【原创】机器学习之PageRank算法应用与C#实现(2)球队排名应用与C#代码

1.足球队排名问题

  1993年的全国大学生数学建模竞赛B题就出了这道题目,不过当时PageRank算法还没有问世,所以现在用PageRank来求解也只能算马后炮,不过可以借鉴一下思路,顺便可以加深对算法的理解,并可以观察算法实际的效果怎么样。顺便说一下,全国大学生数学建模竞赛的确非常有用,我在大学期间,连续参加过2004和2005年的比赛,虽然只拿了一个省二等奖,但是这个过程对我的影响非常大。包括我现在的编程,解决问题的思路都是从建模培训开始的。希望在校大学生珍惜这些机会,如果能入选校队,参加集训,努力学习,对以后的学习,工作都非常有帮助。下面看看这个题目的具体问题:

具体数据由于篇幅较大,已经上传为图片,需要看的,点击链接:数据链接

2.利用PageRank算法的思路

2.1 问题分析

  足球队排名次问题要求我们建立一个客观的评估方法,只依据过去一段时间(几个赛季或几年)内每个球队的战绩给出各个球队的名次,具有很强的实际背景.通过分析题中12支足球队在联赛中的成绩,不难发现表中的数据残缺不全,队与队之间的比赛场数相差很大,直接根据比赛成绩来排名次比较困难。

  下面我们利用PageRank算法的随机冲浪模型来求解.类比PageRank算法,我们可以综合考虑各队的比赛成绩为每支球队计算相应的等级分(Rank),然后根据各队的等级分高低来确定名次,直观上看,给定球队的等级分应该由它所战胜和战平的球队的数量以及被战胜或战平的球队的实力共同决定.具体来说,确定球队Z的等级分的依据应为:一是看它战胜和战平了多少支球队;二要看它所战胜或战平球队的等级分的高低.这两条就是我们确定排名的基本原理.在实际中,若出现等级分相同的情况,可以进一步根据净胜球的多少来确定排名.由于表中包含的数据量庞大,我们先在不计平局,只考虑获胜局的情形下计算出各队的等级分,以说明算法原理。然后我们综合考虑获胜局和平局,加权后得到各队的等级分,并据此进行排名。考虑到竞技比赛的结果的不确定性,我们最后建立了等级分的随机冲浪模型,分析表明等级分排名结果具有良好的参数稳定性。

2.2 获取转移概率矩阵

   首先利用有向赋权图的权重矩阵来表达出各队之间的胜负关系.用图的顶点表示相应球队,用连接两个顶点的有向边表示两队的比赛结果。同时给边赋权重,表明占胜的次数。所以,可以得到数据表中给出的12支球队所对应的权重矩阵,这是计算转义概率矩阵的必要步骤,这里直接对论文中的截图进行引用:

2.3 关于加权等级分

  上述权重不够科学,在论文中,作者提出了加权等级分,就是考虑平局的影响,对2个矩阵进行加权得到权重矩阵,从而得到转移概率矩阵。这里由于篇幅比较大,但是思路比较简单,不再详细说明,如果需要详细了解,可以看论文。本文还是集中在C#的实现过程。

2.4 随机冲浪模型

  

3.C#编程实现过程

  下面我们将使用C#实现论文中的上述过程,注意,2.3和2.2的思想是类似的,只不过是多了一个加权的过程,对程序来说还是很简单的。下面还是按照步骤一个一个来,很多人看到问题写程序很难下手,其实习惯就好了,按照算法的步骤来,一个一个实现,总之要先动手,不要老是想,想来想去没有结果,浪费时间。只有实际行动起来,才能知道实际的问题,一个一个解决,持之以恒,思路会越来越清晰。

3.1 计算权重矩阵

  权重矩阵要根据测试数据,球队和每2个球队直接的比分来获取,所以我们使用一个字典来存储原始数据,将每个节点,2个队伍的比赛结果比分都写成数组的形式,来根据胜平负的场次计算积分,得到边的权重,看代码吧:

复制代码
 1 /// <summary>根据比赛成绩,直接根据积分来构造权重矩阵,根据i,对j比赛获取的分数</summary>
 2 /// <param name="data">key为2个对的边名称,value是比分列表,分别为主客进球数</param>
 3 /// <param name="teamInfo">球队的编号列表</param>
 4 /// <returns>权重矩阵</returns>
 5 public static double[,] CalcLevelTotalScore(Dictionary<String, Int32[][]> data, List<Int32> teamInfo)
 6 {
 7     Int32 N = teamInfo.Count;
 8     double[,] result = new double[N, N];
 9 
10     #region 利用对称性,只计算一半
11     for (int i = 1; i < N; i++)
12     {
13         for (int j = i + 1; j <= N; j++)
14         {
15             #region 循环计算
16             String key = String.Format("{0}-{1}", teamInfo[i - 1], teamInfo[j - 1]);
17             //不存在比赛成绩
18             if (!data.ContainsKey(key))
19             {
20                 result[i - 1, j - 1] = result[j - 1, i - 1] = 0;
21                 continue;
22             }
23             //计算i,j直接的互胜场次
24             var scores = data[key];//i,j直接的比分列表
25             var Si3 = scores.Where(n => n[0] > n[1]).ToList();//i胜场次
26             var S1 = scores.Where(n => n[0] == n[1]).ToList();//i平场次
27             var Si0 = scores.Where(n => n[0] < n[1]).ToList();//i负场次
28             result[i - 1, j - 1] = Si3.Count*3 + S1.Count ;
29             result[j - 1, i - 1] = Si0.Count *3 + S1.Count ;
30             #endregion
31         }
32     }
33     #endregion
34     //按照列向量进行归一化
35     return GetNormalizedByColumn(result);
36 }
复制代码

  上面最后返回调用了归一化的函数,比较简单,直接代码贴出来,折叠一下:

 View Code

3.2 计算最大特征值及特征向量

  计算特征值和特征向量是一个数学问题,我们采用了Math.NET数学计算组件,可以直接计算很方便。详细的使用可以参考下面代码,组件的其他信息可以参考本站导航栏上的专题目录,有大量的使用文章。看代码吧。

复制代码
 1 /// <summary>求最大特征值下的特征向量</summary>
 2 /// <param name="data"></param>
 3 /// <returns></returns>
 4 public static double[] GetEigenVectors(double[,] data)
 5 {
 6     var formatProvider = (CultureInfo)CultureInfo.InvariantCulture.Clone();
 7     formatProvider.TextInfo.ListSeparator = " ";
 8 
 9     int N = data.GetLength(0);
10     Matrix<double> A = DenseMatrix.OfArray(data);
11     var evd = A.Evd();
12     var vector = evd.EigenVectors;//特征向量
13     var ev = evd.EigenValues;//特征值,复数形式发
14 
15     if (ev[0].Imaginary > 0) throw new Exception("第一个特征值为复数");
16     //取 vector 第一列为最大特征向量
17     var result = new double[N];
18     for (int i = 0; i < N; i++)
19     {
20         result[i] =Math.Abs(vector[i, 0]);//第一列,取绝对值
21     }
22     return result;
23 }
复制代码

3.3 随机冲浪模型的实现

  随机冲浪模型主要是有一个比例,设置之后可以直接求解,也比较简单,函数如下:

复制代码
 1 /// <summary>获取随机冲浪模型的 转移矩阵:
 2 /// 作用很明显,结果有明显的改善
 3 /// </summary>
 4 /// <returns></returns>
 5 public static double[,] GetRandomModeVector(double[,] data ,double d = 0.35)
 6 {
 7     int N = data.GetLength(0);
 8     double k = (1.0 - d) / (double)N;
 9     double[,] result = new double[N, N];
10     for (int i = 0; i < N; i++)
11     {
12         for (int j = 0; j < N; j++) result[i, j] = data[i, j] * d + k;
13     }
14     return result;
15 }
复制代码

3.4 其他

  其他问题就是数据组合的过程,这里太多,不详细讲解。主要是构建测试数据以及排序后结果的处理,很简单。贴一个球队排序的函数,根据特征向量:

复制代码
 1 /// <summary>排序,输出球队编号</summary>
 2 /// <param name="w"></param>
 3 /// <param name="teamInfo"></param>
 4 /// <returns></returns>
 5 public static Int32[] TeamOrder(double[] w, List<Int32> teamInfo)
 6 {
 7     Dictionary<int, double> dic = new Dictionary<int, double>();
 8     for (int i = 1; i <= w.Length; i++) dic.Add(i , w[i-1]);
 9     return dic.OrderByDescending(n => n.Value).Select(n => n.Key).ToArray();
10 }
复制代码

4.算法测试

  我们使用问题1中的数据,进行测试,首先构建测试集合,代码如下,太长,折叠一下,主要是问题1的原始数据:

 View Code

测试的主要方法是:

复制代码
1 var team = new List<Int32>(){1,2,3,4,5,6,7,8,9,10,11,12};
2 var data = GetTestData();
3 var k3 = CalcLevelScore3(data,team);
4 var w3 = GetEigenVectors(k3);
5 
6 var teamOrder = TeamOrder(w3,team);
7 Console.WriteLine(teamOrder.ArrayToString());
复制代码

排序结果如下:

7,3,1,9,8,2,10,4,6,5,12,11

结果和论文差不多,差别在前面2个,队伍7和3的位置有点问题。具体应该是计算精度的关系如果前面的计算有一些精度损失的话,对后面的计算有一点点影响。

  PageRank的一个基本应用今天就到此为止,接下来如果大家感兴趣,我将继续介绍PageRank在球队排名和比赛预测结果中的应用情况。看时间安排,大概思路和本文类似,只不过在细节上要处理一下。


本文转自叶小钗 h数据之巅博客园博客,原文链接:http://www.cnblogs.com/asxinyu/p/MachineLearning_PageRank_TeamRank_2.html,如需转载请自行联系原作者


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
机器学习之Python开源教程——专栏介绍及理论知识概述
机器学习之Python开源教程——专栏介绍及理论知识概述
21 0
【Python】python 机器学习之 Numpy 使用总结(二)
【Python】python 机器学习之 Numpy 使用总结(二)
35 0
【Python】python 机器学习之 Numpy 使用总结(一)
【Python】python 机器学习之 Numpy 使用总结(一)
28 0
上线十年,吴恩达机器学习课程全面升级,Python教学+更多应用,本月开课
上线十年,吴恩达机器学习课程全面升级,Python教学+更多应用,本月开课
91 0
Python实现GIF动图以及视频卡通化,两脚踢碎次元壁 | 机器学习(2)
Python实现GIF动图以及视频卡通化,两脚踢碎次元壁 | 机器学习
56 0
Python实现GIF动图以及视频卡通化,两脚踢碎次元壁 | 机器学习(1)
Python实现GIF动图以及视频卡通化,两脚踢碎次元壁 | 机器学习
47 0
Python实现照片卡通化,一拳打破次元壁 | 机器学习
Python实现照片卡通化,一拳打破次元壁 | 机器学习
204 0
【人工智能】机器学习之Python使用KNN算法进行电影类型预测以及使用KNN算法对鸢尾花进行分类
使用KNN进行电影类型预测: 给定训练样本集合 解题步骤: 1.计算一个新样本与数据集中所有数据的距离 2.按照距离大小进行递增排序 3.选取距离最小的k个样本 4.确定前k个样本所在类别出现的频率,并输出出现频率最高的类别 编写代码,实现对iris数据集的KNN算法分类及预测 要求: (1)数据集划分为测试集占20%; (2)n_neighbors=5; (3)评价模型的准确率; (4)使用模型预测未知种类的鸢尾花。 (待预测数据:X1=[[1.5 , 3 , 5.8 , 2.2], [6.2 , 2.9 , 4.3 , 1.3]]) iris数据集有150组,每组4个数据。
237 0
【人工智能】机器学习及与智能数据处理Python使用朴素贝叶斯算法对垃圾短信数据集进行分类
朴素贝叶斯算法 输入:样本集合D={(x_1,y_1),(x_2,y_2)~(x_m,y_m); 待预测样本x; 样本标记的所有可能取值{c_1,c_2,c_3~c_k}; 样本输入变量X的每个属性变量X^i的所有可能取值{a_i1,a_i2,~,a_iAi}; 输出:待预测样本x所属的类别
228 0
+关注
文章
问答
文章排行榜
最热
最新
相关电子书
更多
信息检索与机器学习的华尔兹
立即下载
弱监督机器学习研究新进展
立即下载
基于Spark的大规模机器学习在微博的应用
立即下载