A brief introduction to K-trend algorithm

今年二月,又是一个飘雪的黑夜,在一个民国旧公馆改建的小酒吧里,没有烛光,也没有约会,只有早已失去温热的咖啡和三个躁动的灵魂,旁边是一团乱绕着的电源线。窗外小巷的昏暗灯光灯照在稿纸本上,低沉吉他伴奏的电脑键盘声仿佛衬托着灵感爆发前那一瞬间思维的寂静…

这是美赛的第二个晚上,沉寂了一天的三个人终于找到了问题的核心突破口,虽然整个比赛由于队友之间协作的问题导致出品了一篇很毛糙的论文而最终与F失之交臂,但作为那四天里我们最自信的作品–原创算法“K-trend”,我个人觉得还是值得写一写的。

0x00 问题场景:

这个问题来自今年数学建模美赛的Problem C:

the foundation intends to donate a total of $100,000,000 (US100 million) to an appropriate group of schools per year, for five years, starting July 2016. In doing so, they do not want to duplicate the investments and focus of other large grant organizations such as the Gates Foundation and Lumina Foundation.

Your team has been asked by the Goodgrant Foundation to develop a model to determine an optimal investment strategy that identifies the schools, the investment amount per school, the return on that investment, and the time duration that the organization’s money should be provided to have the highest likelihood of producing a strong positive effect on student performance. This strategy should contain a 1 to N optimized and prioritized candidate list of schools you are recommending for investment based on each candidate school’s demonstrated potential for effective use of private funding, and an estimated return on investment (ROI) defined in a manner appropriate for a charitable organization such as the Goodgrant Foundation.

在附件中给了一堆多维度的数据,用来描述每一个候选学校的各项指标,我们三个队友的思维都认为应该找到一种对多维度数据进行预测的方法,将投资额度作为变量,分别预测所有投资对象在不同投资情况下的表现,最后根据这个表现排序,找到最佳的一组投资候选对象。OK,那么问题简化一下,就是有n组多维度带权数据(权值用来衡量价值),需要分别改变每一组数据的某一个或多个维度的值(投资直接影响的参数),然后预测这n组数据在被变动后(被投资后)权值的变化(被投资后价值的变化),最后根据所有的预测结果找出权值增量最大的m组数据(投资后价值提升越多的对象,即ROI最高)。

0x01 核心问题:

根据这个思维,首先我们要定义一个投资的指标,也就是定义最核心的那个权值,最靠谱的方案是把一个学校的社会价值作为衡量学校好坏的标准,即权值,于是就要根据描述的数据建立一个公式来量化各个学校的社会价值,比如可以参考数据中给出的入学率,毕业率,毕业生工资水平等建立一个权值公式用于衡量一个学校的好坏;然后还要制定不同的投资额度和投资方案,比如投资用于提高奖学金,那么投资实际上就是在提高学校参数中的奖学金一项的值,亦或者用于增聘教师,那么投资就变成了提高学校参数中教师一项的值。

如此一来,这个问题进一步简化就成了:有n组m维的带权数据,对某一组的其中o个维度的参数进行变动,预测在变动后权值的变化。在中间如果涉及投资额度或者投资策略的不同,就有不同的变动方案,同时还需要预测哪一个变动方案最好,即权值差最大。

0x02 K-trend:

对于这样一个问题,其实最有效的思路应该是监督学习。因为问题给出的dataset的形式让人不由得联想到K-NN和K-Means。其实这个问题的背景和两个“K-某某”算法的应用背景都出奇相似,所以我们基于这两个经典的“K-某某”组合创新,折腾出了一个新的“K-某某”–“K-trend”。

OK,此处摘选一段我们当时的论文:

In this case, we only know one variable “graduation rate” or “enrollment,” but we need to make a forecast to the performance of students after the investment. The reference value of the predict is the other point’s (other institution’s) distribution of its eigenvalues. Under the inspired of K-means algorithm, we establish a new algorithm to make regression forecast. The main function of our algorithm is that making arbitration and prediction for multiple competition variables under the condition of the presence of supervisor.

Because of the inspiration of the algorithm comes from the K-NN and the K-Means, so it named “K-Trend”. Based on our model and the performances of students before our investment, the target of K-Trend algorithm is to predict the addition of student’s performances. And we could find the target which has the trend of highest addition by the comparison of the conditions.

Because that the number of eigenvalues of each institution is a constance m. So the algorithm is going to establishing a vector which has m dimensions. This vector could indicate a point in euclidean space with m dimensions. In this case, the algorithm could abstract all institutions in the list(Problem C – Most Recent Cohorts Data (Scorecard Elements)) by points.

In this case, we could pay attention to the points in the candidate list(Problem C – IPEDSUID for Potential Candidate Schools.xlsx) and abstract these points in an euclidean space. At this time, we has finished the establish of our model. First of all, we select a point and get the addition of it in one dimension (graduation rates or enrollment) by our model. Secondly, the algorithm shift this point and get a new point. regard this point as the center point(P0) and find the nearest k points(if we set k as 3,we could get p1,p2,p3 as below).Then we set the average of the k points as the new weights of this point. And regard the new weight as “the prediction of weight” (Like the method to get the “center of gravity” in K-Means algorithm).

Thirdly, we define the differences between the new point’s weight and the weight of the point which hasn’t been shift as the “addition of weight” of this point. Finally, calculate the additions of weight of all points in the list and put all the numbers in descending order, then we selects x points which has highest value, that is the results of our model.

As we know the theorem following:

Profit after the investment = Profit before the investment = The investment profit – Profit growth caused by investment

We could know that K-Trend algorithm can screen out the targets in the candidate list which has the best trend on the addition of profit (they may not have the highest profit now but the highest development potential when investment intervenes).

这里借用了K-NN和K-means的一些思想,将数据集的整体作为监督元,并且也采用了求“最近的k个点取平均值”来估算未知权值点的权值。

0x03 通俗点讲:

投资在一个学校的某一方面会导致这个方面的指标发生直接的变化,比如提高奖学金额度,那么直接改变的肯定就是奖学金这个参数。但是一个参数的改变会带来其他很多参数的联动变化,这个变化的内部机理是很复杂而且很难去研究的。但是要预测的最终社会价值度量(权值)的改变是取决于这些蝴蝶效应般间接改变的参数的。而我们的K-trend算法就是用来解决这种预测问题的。

K-trend算法最核心的一点就是把n组m维度的数据映射到一个m维的欧几里得空间中,那么每一组数据都可以表示为该欧几里得空间中的一组坐标,也就是空间中的一个点,那么n组坐标自然就能得到n个点。这n个点各自有一个空间中的绝对位置(坐标),也相对于任何一个点有一个相对位置(空间向量),而这个相对空间向量的模长就是该点与参考点的欧氏距离:

D=\sqrt{\sum_{i=1}^{m}(x_{i}-y_{i})^{2}}

在这个问题中,欧几里得空间的每一个维度对应了学校的每一个参数指标,而每一给点对应每一个候选的学校,每一个点有一个权值,即该学校的社会价值度量。当需要对一次投资进行预测的时候,可以把这次投资所能直接影响的那一部分参数在这个空间中表示出来,比如我投资让这个学校提高它的奖学金额度,那么这个点在奖学金额度这个维度上的参数就会发生变化,从而会导致这个点在整个空间中发生偏移。假设投资前这个点为P,那么偏移后的新位置就相当于一个新点P_{\alpha}。接下来我们再考虑第二种投资方案:增修校舍,提高学校规模,那么这个点在空间中的学生数量这个参数就会发生变化,那么又会偏移出另一个新点P_{\beta}。接下来又可以考虑其他的方案,或者修改投资额度,那么就可以相应的偏移出P_{\gamma}P_{\delta}P_{\epsilon}

举个例子,如果欧式空间的维度为2,那么就可以把这个空间在平面上表示出来。接下来要做的事情就是预测P_{\alpha}P_{\beta}P_{\gamma}…的权值,K-trend在这里的方法是对偏移出的点取周围距离最近的k个点:P_{1}P_{2}P_{3}…然后把这k个点权值的算术平均值作为这个偏移点的预测权值,图为设k=3时的情景:

image-famcpy
W_{f}=\frac{\sum_{i=1}^{k}w_{i}}{k}

在算得每个偏移点的预测权值后再算这个便宜的到的预测值和原有权值的差,差值最大的那个点就是K-trend输出的针对该投资目标的最佳投资方案。

按这个步骤算得所有投资对象的最佳投资方案和对应的预测权值差后再把所有的预测权值差做一个排序,那么最后得到的前x个的排序结果就是最终的“Top x”最佳投资对象。

0x04 合理性:

K-trend前半部分的几何空间的抽象过程并不存在假设。合理性的讨论关键在于预测的方法:“取偏移点周围离它最近的k个点,取其权值的算术平均值作为预测值”,这个其实是原封不动的借用了K-NN的做法。至于这种做法在K-trend中的合理性,是有一个前提假设的,就是k的取值,如果k取值太小产生的误差会太大,但是如果k取得过大了又会使得不同偏移出来的新值过于接近,不利于区分。其实就算是在K-NN中,对于k值的取值也是在不同情况下有不同的策略,比如贝叶斯,Cross Validation。

K-Trend的利用向量欧氏距离比较的思想则是继承自K-means,但其实个人觉得整个算法更接近K-NN,算是两种算法的一个混合变种吧。所以K-trend大部分的合理性的假设也是继承自K-NN和K-means。

0x05 补充一点东西:

K-means算法:http://home.deib.polimi.it/matteucc/Clustering/tutorial_html/kmeans.html

K-NN算法:http://www.saedsayad.com/k_nearest_neighbors.htm

MCM/ICM 2016:http://www.comap.com/undergraduate/contests/mcm/contests/2016/problems/

Leave a Reply

Your email address will not be published. Required fields are marked *