【原创】机器学习之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 }

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

 1 /// <summary>按照列向量进行归一化</summary>
 2 /// <param name="data"></param>
 3 /// <returns></returns>
 4 public static double[,] GetNormalizedByColumn(double[,] data)
 5 {
 6     int N = data.GetLength(0);
 7     double[,] result = new double[N, N];
 8     #region 各个列向量归一化
 9     for (int i = 0; i < N; i++) //
10     {
11         double sum = 0;
12         //
13         for (int j = 0; j < N; j++) sum += data[j, i];
14         for (int j = 0; j < N; j++)
15         {
16             if (sum != 0) result[j, i] = data[j, i] / (double)sum;//归一化,每列除以和值
17             else result[j, i] = data[j, i];
18         }
19     }
20     #endregion
21 
22     return result;
23 }
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的原始数据:

 1 /// <summary>
 2 /// 获取测试的数据集,key=对1-对2,value = int[,] 为比分
 3 /// </summary>
 4 public static Dictionary<String, Int32[][]> GetTestData()
 5 {
 6     Dictionary<String, Int32[][]> data = new Dictionary<string, int[][]>();
 7     #region 依次添加数据
 8     #region T1
 9     data.Add("1-2", new Int32[][]{ new Int32[] { 0, 1 }, new Int32[] { 1, 0 }, new Int32[] { 0, 0 } });
10     data.Add("1-3", new Int32[][] { new Int32[] { 2, 2 }, new Int32[] { 1, 0 }, new Int32[] { 0, 2 } });
11     data.Add("1-4", new Int32[][] { new Int32[] { 2, 0 }, new Int32[] { 3, 1 }, new Int32[] { 1, 0 } });
12     data.Add("1-5", new Int32[][] { new Int32[] { 3, 1 } });
13     data.Add("1-6", new Int32[][] { new Int32[] { 1, 0 } });
14     data.Add("1-7", new Int32[][] { new Int32[] { 0, 1 }, new Int32[] { 1, 3 } });
15     data.Add("1-8", new Int32[][] { new Int32[] { 0, 2 }, new Int32[] { 2, 1 } });
16     data.Add("1-9", new Int32[][]{ new Int32[] { 1, 0 }, new Int32[]  { 4, 0 } });
17     data.Add("1-10", new Int32[][]{  new Int32[] { 1, 1 },  new Int32[] { 1, 1 } });
18     #endregion
19 
20     #region T2
21     data.Add("2-3", new Int32[][] { new Int32[] { 2, 0 }, new Int32[] { 0, 1 }, new Int32[] { 1, 3 } });
22     data.Add("2-4", new Int32[][] { new Int32[] { 0, 0 }, new Int32[] { 2, 0 }, new Int32[] { 0, 0 } });
23     data.Add("2-5", new Int32[][] { new Int32[] { 1, 1 } });
24     data.Add("2-6", new Int32[][] { new Int32[] { 2, 1 } });
25     data.Add("2-7", new Int32[][] { new Int32[] { 1, 1 }, new Int32[] { 1, 1 } });
26     data.Add("2-8", new Int32[][] { new Int32[] { 0, 0 }, new Int32[] { 0, 0 } });
27     data.Add("2-9", new Int32[][] { new Int32[] { 2, 0 }, new Int32[] { 1, 1 } });
28     data.Add("2-10", new Int32[][] { new Int32[] { 0, 2 }, new Int32[] { 0, 0 } });
29     #endregion
30 
31     #region T3
32     data.Add("3-4", new Int32[][] { new Int32[] { 4, 2 }, new Int32[] { 1, 1 }, new Int32[] { 0, 0 } });
33     data.Add("3-5", new Int32[][] { new Int32[] { 2, 1 } });
34     data.Add("3-6", new Int32[][] { new Int32[] { 3, 0 } });
35     data.Add("3-7", new Int32[][] { new Int32[] { 1, 0 }, new Int32[] { 1, 4 } });
36     data.Add("3-8", new Int32[][] { new Int32[] { 0, 1 }, new Int32[] { 3, 1 } });
37     data.Add("3-9", new Int32[][] { new Int32[] { 1, 0 }, new Int32[] { 2, 3 } });
38     data.Add("3-10", new Int32[][] { new Int32[] { 0, 1 }, new Int32[] { 2, 0 } });
39     #endregion
40 
41     #region T4
42     data.Add("4-5", new Int32[][] { new Int32[] { 2, 3 } });
43     data.Add("4-6", new Int32[][] { new Int32[] { 0, 1 } });
44     data.Add("4-7", new Int32[][] { new Int32[] { 0, 5 }, new Int32[] { 2, 3 } });
45     data.Add("4-8", new Int32[][] { new Int32[] { 2, 1 }, new Int32[] { 1, 3 } });
46     data.Add("4-9", new Int32[][] { new Int32[] { 0, 1 }, new Int32[] { 0, 0 } });
47     data.Add("4-10", new Int32[][] { new Int32[] { 0, 1 }, new Int32[] { 1, 1 } });
48     #endregion
49 
50     #region T5
51     data.Add("5-6", new Int32[][] { new Int32[] { 0, 1 } });
52     data.Add("5-11", new Int32[][] { new Int32[] { 1, 0 }, new Int32[] { 1, 2 } });
53     data.Add("5-12", new Int32[][] { new Int32[] { 0, 1 }, new Int32[] { 1, 1 } });
54     #endregion
55 
56     #region T7
57     data.Add("7-8", new Int32[][] { new Int32[] { 1, 0 }, new Int32[] { 2, 0 }, new Int32[] { 0, 0 } });
58     data.Add("7-9", new Int32[][] { new Int32[] { 2, 1 }, new Int32[] { 3, 0 }, new Int32[] { 1, 0 } });
59     data.Add("7-10", new Int32[][] { new Int32[] { 3, 1 }, new Int32[] { 3, 0 }, new Int32[] { 2, 2 } });
60     data.Add("7-11", new Int32[][] { new Int32[] { 3, 1 } });
61     data.Add("7-12", new Int32[][] { new Int32[] { 2, 0 } });
62     #endregion
63 
64     #region T8
65     data.Add("8-9", new Int32[][] { new Int32[] { 0, 1 }, new Int32[] { 1, 2 }, new Int32[] { 2, 0 } });
66     data.Add("8-10", new Int32[][] { new Int32[] { 1, 1 }, new Int32[] { 1, 0 }, new Int32[] { 0, 1 } });
67     data.Add("8-11", new Int32[][] { new Int32[] { 3, 1 } });
68     data.Add("8-12", new Int32[][] { new Int32[] { 0, 0 } });
69     #endregion
70 
71     #region T9
72     data.Add("9-10", new Int32[][] { new Int32[] { 3, 0 }, new Int32[] { 1, 0 }, new Int32[] { 0, 0 } });
73     data.Add("9-11", new Int32[][] { new Int32[] { 1, 0 } });
74     data.Add("9-12", new Int32[][] { new Int32[] { 1, 0 } });
75     #endregion
76 
77     #region T10
78     data.Add("10-11", new Int32[][] { new Int32[] { 1, 0 } });
79     data.Add("10-12", new Int32[][] { new Int32[] { 2, 0 } });
80     #endregion
81 
82     #region T11
83     data.Add("11-12", new Int32[][] { new Int32[] { 1, 1 }, new Int32[] { 1, 2 }, new Int32[] { 1, 1 } });
84     #endregion
85     #endregion
86     return data;
87 }
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在球队排名和比赛预测结果中的应用情况。看时间安排,大概思路和本文类似,只不过在细节上要处理一下。

相关文章
|
3天前
|
机器学习/深度学习 数据采集 算法
探索机器学习在图像识别中的应用
【7月更文挑战第19天】机器学习技术在图像识别领域的应用日益成熟,本文将介绍机器学习如何通过算法和模型处理图像数据,提高识别准确性。我们将探讨从基本的数据预处理到复杂的深度学习网络的构建过程,并分享一些实用的技巧和最佳实践,帮助读者理解和实现自己的图像识别项目。
|
1天前
|
机器学习/深度学习 数据可视化 数据挖掘
数据可视化大不同!Python数据分析与机器学习中的Matplotlib、Seaborn应用新视角!
【7月更文挑战第22天】数据可视化在Python数据科学中至关重要,Matplotlib和Seaborn提供强大工具。案例展示如何用它们分析房屋售价数据:Matplotlib绘制面积与售价散点图揭示正相关,Seaborn的pairplot展示多变量关系。在建模阶段,特征重要性通过条形图可视化,辅助模型优化。这两库是理解数据和提升模型性能的关键。
10 3
|
1天前
|
机器学习/深度学习 数据采集 人工智能
机器学习算法入门与实践
【7月更文挑战第22天】机器学习算法入门与实践是一个既充满挑战又极具吸引力的过程。通过掌握基础知识、理解常见算法、注重数据预处理和模型选择、持续学习新技术和参与实践项目,你可以逐步提高自己的机器学习技能,并在实际应用中取得优异的成绩。记住,机器学习是一个不断迭代和改进的过程,保持好奇心和耐心,你将在这个领域走得更远。
|
2天前
|
机器学习/深度学习 数据采集 监控
探索机器学习在金融风控中的应用
【7月更文挑战第21天】随着科技的飞速发展,机器学习已成为金融领域风险管理的重要工具。本文将深入探讨机器学习如何革新传统风控模式,提升风险识别和决策效率,并分析其在实际应用中面临的挑战与未来发展趋势。
|
6天前
|
机器学习/深度学习 算法 算法框架/工具
模型训练实战:选择合适的优化算法
【7月更文第17天】在模型训练这场智慧与计算力的较量中,优化算法就像是一位精明的向导,引领着我们穿越复杂的损失函数地形,寻找那最低点的“宝藏”——最优解。今天,我们就来一场模型训练的实战之旅,探讨两位明星级的优化算法:梯度下降和Adam,看看它们在不同战场上的英姿。
35 5
|
7天前
|
机器学习/深度学习 数据采集 运维
智能化运维:机器学习在故障预测中的应用
【7月更文挑战第16天】随着信息技术的飞速发展,企业对IT系统的依赖程度不断加深。传统的运维模式已经难以满足现代业务的需求,智能化运维应运而生。本文将探讨如何通过机器学习技术提高故障预测的准确性,减少系统停机时间,并提升运维效率。我们将分析机器学习在故障预测中的具体应用案例,讨论实施过程中的挑战与对策,以及评估机器学习模型的性能。文章旨在为运维人员提供一种全新的视角和方法,以期达到优化系统稳定性和提升用户体验的目的。
|
7天前
|
机器学习/深度学习 人工智能 算法
探索机器学习的边界:深度学习技术在图像识别中的应用
本文将深入探讨深度学习技术在图像识别领域的应用,揭示其背后的原理和实现方式。通过具体的案例分析,我们将展示深度学习如何推动图像识别技术的发展,并讨论当前面临的挑战和未来的发展方向。 【7月更文挑战第16天】
18 4
|
6天前
|
机器学习/深度学习 人工智能 自然语言处理
|
6天前
|
机器学习/深度学习 数据采集 运维
探索机器学习在金融风控中的应用与挑战
本文深入探讨了机器学习技术在金融风险控制领域的应用及其所面临的挑战。通过分析当前金融市场的风险特点,结合机器学习算法的优势与局限,文章揭示了机器学习如何助力金融机构提高风险识别的精准度和决策效率。同时,讨论了实施过程中的数据隐私、模型透明度和监管合规等关键问题,并提出了相应的解决策略。最后,文章展望了机器学习技术未来在金融风控领域的发展趋势,为金融科技从业者提供了实践指导和思考方向。
16 0
|
5天前
|
传感器 算法
基于无线传感器网络的MCKP-MMF算法matlab仿真
MCKP-MMF算法是一种启发式流量估计方法,用于寻找无线传感器网络的局部最优解。它从最小配置开始,逐步优化部分解,调整访问点的状态。算法处理访问点的动态影响半径,根据带宽需求调整,以避免拥塞。在MATLAB 2022a中进行了仿真,显示了访问点半径请求变化和代价函数随时间的演变。算法分两阶段:慢启动阶段识别瓶颈并重设半径,随后进入周期性调整阶段,追求最大最小公平性。
基于无线传感器网络的MCKP-MMF算法matlab仿真

热门文章

最新文章