编者按:  

    “2010年7月，北京连续10天温度超过35摄氏度。这是10年来的第一次。”      

    “勒布朗-詹姆斯从3月22号到4月8号间的连续9场比赛中，詹姆斯每场都至少得到了35分。自1970年以来，仅有迈克尔-乔丹、科比布-莱恩特和他做到这一点。”     

    以上是两个新闻亮点的例子。本文将介绍中国惠普研究院的最新研究成果：如何从序列数据中高效的挖掘出这些“亮点”。

           
     作者：姜啸，2010年7月至2011年1月在惠普中国研究院实习，现于上海交通大学计算机系在读研究生。

                

原文请参见：Xiao Jiang, Chengkai Li, Ping Luo, Min Wang, Yong Yu: Prominent streak discovery in sequence data. KDD 2011: 1280-1288

    序列数据
    日常生活中，我们随时随地都会遇到序列数据，尤其是时间序列数据。例如每天猪肉的价格，每分每秒股票的价格、成交量，每小时的地方温度的高低，每时每刻网站的访问人数，等等……
    几十年来，许许多多的研究人员都对序列数据进行了研究。有些研究是关于如何根据历史序列对未来序列进行预测的，研究成果可以应用在股价预测上。有些研究是关于对多个序列进行聚类的，通过聚类的结果可以发现数据集中序列的几种基本模式。我们这次的研究目标主要是发掘序列数据中的“亮点”－序列中一些有趣的子序列。

    引子

                          
    勒布朗-詹姆斯是在NBA打球的著名篮球明星。下图是在雅虎体育上记录的他在2006年3月和4月NBA常规赛季中每场比赛的数据。第一列是比赛的日期，最后一列是该场比赛中他的得分。可以看出来从3月22号到4月8号间的9场比赛中，詹姆斯每场都至少得到了35分。很显然这是他这段时期比赛的一个亮点。事实上，NBA自1970年来仅有两名运动员拿到过这样的数据，分别是迈克尔乔丹和科比布莱恩特，勒布朗詹姆斯是第三位。

    亮点
    从上面的例子可以看出来，我们所关注的亮点就是序列中一段很牛的子序列。这里的牛可以是高也可以是低，需要看具体的应用背景来决定。在篮球比赛中，我们显然认为得分高的更牛一些。
    上面给出的只是“牛”的一个直观的定义，为了进一步研究方便，我们需要从数学上精确的表述它：给两段子序列，究竟哪个更牛一些呢？这里我们把关注点集中在两个点上，一个是子序列的长度，还有一个是谷点（最低点）。譬如勒布朗詹姆斯从3月22号到4月8号这段子序列的长度就是9（场比赛），谷点就是35（分）。显而易见，一个子序列越长或是它的谷点越高，则它越牛。对于两个子序列来说，若一个子序列的长度超过了另外一个并且它的谷点也更高，则该子序列更牛一些。

          

    所以我们最终的目标就是：给定一个序列，找出所有的子序列（亮点），对于这些子序列来说，不存在比他们更牛的子序列。
    对于詹姆斯06年3月和4月的比赛数据来说，9场35分+显然是一个亮点。9场中其中有连续两场都拿到了至少46分，这也是一个亮点。此外，他还有过两个单场47分，根据我们的定义，这些都是亮点。
下图给了一个简单的序列中所有亮点的例子。横坐标表示是序列中的位置，而纵坐标表示的是值的大小。图中的一个线段表示的就是一个亮点，对应的3个数字分别是子序列的起点、终点和谷点的值。

    解决问题
    最简单也是最容易想到的做法就是把所有的子序列都枚举出来，然后两两进行比较，看一个是否比另一个更牛。这个方法一看就很暴力。当序列较长的时候，计算机需要很长的时间才能得出结果。
    我们最终采用的方法分成了两步：第一步找到那些有可能成为亮点的子序列，我们称之为候选序列；第二步从候选序列中选出最终的我们真正寻找的亮点。
    在第一步中，算法从左往右扫描序列，在扫描的时候，利用一些局部性质，可以很快的判断出哪些有可能成为亮点哪些毫无可能。令人惊讶的是，这些简单的判断可以使得候选数量大大的减少。而第二步中，我们直接采用了文献中现成的Skyline算法。

    有趣的实验结果
    我们在一些真实的数据上做了实验。实验不仅证实了我们的算法要比最朴素的算法快很多很多倍以外，还确实找到了一些有趣的子序列。在对著名歌手Lady Gaga在维基百科的页面流量的实验中，我们发现超过一半的亮点都在2010年9月12号附近。事实上，那天正好是2010年MTV音乐录影带大奖的颁奖典礼，Lady Gaga成为了当晚的大赢家，得到多个奖项。其中一个子序列显示，她的维基百科页面几乎连续4天每小时都有超过2000的访问流量。