趋势预测文献阅读

趋势预测

---

Patterns of Temporal Variation in Online Media [1]

---

这篇文章主要是针对在线媒体（如新闻消息，博客，tweets等），研究了它们的时态变化模式。

研究对象

---

如上图，本文研究的对象是各大网站关于各种phrase（习语）以及tweeter的tag的流行度随着时间的演变，其流行度定义为在某个时刻该phrase（tag）在各大网站中提及的次数。本文想要研究的就是这些phrase（tag）随时间变化的模式。

研究过程及方法

---

1. 本文首先把phrase（tag）的流行度随时间的变化提取为时间序列
2. 然后把对这些时间序列的分析转化为对其进行聚类的问题。
3. 提出了一种新的时间序列的相似性测量指标
4. 根据上述的新的相似性指标来衡量两个时间序列的“距离”，类似于K-Means方法，提出了一种K-SC聚类算法用于对时间序列进行聚类。
5. 在K-SC的基础上再给予小波增量的方法对其进行了改进，即为Incemental K-SC。
6. 利用上述聚类算法对时间序列进行聚类得到了6种不同的时态模式，
7. 根据不同的特征建立logistic回归来对时间序列分类，来预测该时间序列属于哪一种时态模式。

研究结果

---

对K-SC算法的一些说明：
1. 时间序列相似度（距离）的定义为：$d(x,y) = min_{\alpha,q}\frac{||x-\alpha y_{(q)}||}{||x||}$。这种定义的好处在于解决了时间序列由于scale和shift变化而引起距离变大的问题，难度在于$q$和$\alpha$的确定。
2. 与K-Means算法的两点区别：a)定义的相似度距离不一样。b)在计算中心的时候不再是简单的求平均值，而是求使误差均方和最小的点。这样做是为了减小异常值所带来的影响。
3. Increament K-SC算法减小了K-SC算法的复杂度，并且解决了K-SC算法对初值选择的敏感性。
4. 聚类个数的选择，文中的解释是做了多组试验，根据两个评价指标Hartigan’s Index 和 the Average Silhouette，然后选择了K=6。

上图表示的是根据文中的方法的聚类结果，得到的6种不同的时态模式，图中的PNATB这些字母表示的在某一个类型中，被不同媒介首次提到的平均时间，作者由此分析了在不同类型中可能不同的信息传播模式。第二幅图表示的是根据不同的方法提取出的特征进行logistic回归分类的准确率，表中结果表明基于时间的特征分类效果最好。

Using a Model of Social Dynamics to Predict Popularity of News [2]

---

本文主要的工作是提出了一种基于社会动力学的模型来进行新闻的流行预测，并将这种方法与线性外推法和只基于社交影响的方法进行比较。

研究对象

---

如上图，本文的研究对象是社交新闻门户网站Digg，这个网站允许用户上传（submit）和投票/赞（vote）新闻，并且每个用户还可以follow好友的vote，也即该用户就是他的好友的fan，这样就引进了一种社交关系。此外，对于某一个新闻，当用户上传它之后，会出现在Digg的upcoming page从而可以得到用户的访问进而被vote，而当这个新闻被vote到一定次数之后，它可以进入Digg的front page，从而该新闻可以被认为是流行的（promoted）。因此，一个新闻可能通过三个途径用户观察到：upcoming page， front page， 用户的friend page。本文则是根据这些信息建立了基于社会动力学的模型来预测新闻是否会流行（promoted）。

研究过程及方法

---

1. 该文建立了如下微分方程：
   $$\frac{dN_{vote}(t)}{dt} = r(v_f(t)+v_u(t)+v_{friend}(t))$$
   其中$N_{vote}(t)$表示在时刻t某新闻得到的vote数，也即流行度；$r$表示该新闻的有趣程度，$v_f(t)$,$v_u(t)$,$v_{friend}(t)$分别表示该新闻通过front page， upcoming page和friend page的rate（速率）。
2. 为了求解上述微分方程，需要计算以下公式来得到$v_f(t)$,$v_u(t)$,$v_{friend}(t)$。这里不再列举其计算公式，其主要的思想是根据用户对各个页面访问的频率、新闻在各个页面的位置、新闻发布后经过的时间以及有多少人还没有看过这条新闻等信息来进行计算。
3. 有趣程度$r$定义为：We estimated r from the data as the value that minimizes the root-mean-square (RMS) difference between the observed votes and the model predictions. 即$r$是使模型预测值与实际值的军方平均值的平方根最小的值。
4. 将该模型与线性外推和只利用社交影响的方法进行比较

研究结果

---

上图表明如果一个用户的fans越少的话，那么他所提交的新闻就要越有趣才能够称为promoted商品，反之若用户的fans较多的话，那么其提交的商品成为流行的商品的门槛就会降低。第二幅图表示的是只根据前四次的观测来估算r值，r就是图中线的斜率。

上图表明如果对于一个刚刚发布的新闻，其最终得到的votes与其在初始阶段用户的fans的vote数成反比，可能说明真正有价值的新闻不是靠炒作而出来的。

最后文章简单的介绍了与另外两种方法的对比：与线性预测的相比，该方法更好的解释了新闻累积votes的过程，以及提高了相关性（correlation），减小了RMS。与只基于用户的社交关系（用户的粉丝数，前10次vote中fans的数量）为feature提出的决策树来对新闻进行是否会流行的分类，准确率有所提高。

参考文献

---

[1] Yang, J. and Leskovec, J., Patterns of temporal variation in online media, in Proceedings of the fourth ACM international conference on Web search and data mining - WSDM ’11 (ACM Press, New York, New York, USA, 2011), p. 177, doi:10.1145/1935826.1935863.

[2] Lerman, K. and Hogg, T., Using a model of social dynamics to predict popularity of news, in Proceedings of the 19th international conference on World wide web - WWW ’10 (ACM Press, New York, New York, USA, 2010), p. 621, doi:10.1145/1772690.1772754.

[3] Markdown 原文