最长01子串

最长01子串

原题

给定一个数组,数组中只包含0和1。请找到一个最长的子序列,其中0和1的数量是相同的。

例1:10101010 结果就是其本身。

例2:1101000 结果是110100

请大家展开自己的思路。

分析

这个题目,看起来比较简单,一些同学可能认为题目的描述符合动态规划的特征,然后就开始用动态规划解,努力找状态转移方程。这些同学的感觉,是很正确的。但,找状态转移方程,我们要对原来的数组进行变换一下。

原来是0和1的串,我们将0都换为-1。这样题目目标就变成,找到一个最长的子串,子串数字和是0。设原数组为A, DP[i]表示从0开始到i的子数组和。DP遍历一遍数组即可。例1中的数组产生的DP为:

0 1 2 3 4 5 6 7
1 0 1 0 1 0 1 0

这个例子,最后一个值是0,并且长度是偶数位。直接满足了结果。

再看例子2:

0 1 2 3 4 5 6
1 2 1 2 1 0 -1

5的位置为0,最长子串从0开始到5,长度为6。

上面这两个例子,所求的子串都是从头开始,如果不是从头开始,会是什么样的呢?看这个例子:1101100

0 1 2 3 4 5 6
1 2 1 2 3 2 1

通过观察上面的表格,我们可以得到,DP[0]==DP[6]==DP[2],DP[1]==DP[3]. 根据DP的定义,如果DP[i]==DP[j],i
一种方法,我们用map保存DP的值到位置的映射,如下表:

DP值 位置 最大位置 最小位置 最大长度
1 0,2,6 6 0 6
2 1,3 3 1 2
3 4 4 4 0
最长子串长度 6

我们最终的算法,要综合考虑最常穿是否从头开始的。
上面的这个思路,时间复杂度是O(n),空间复杂度也是O(n).

还有其他的思路,例如DP保存的是[0,i]的1的个数,那么DP[j] - DP[i] * 2 == j - i则表明A[i+1]…A[j]是一个满足条件的串,找到j-i最大的,就是最终的结果,这个思路的时间复杂度为O(n^2),空间复杂度为O(n).

社交圈子挖掘的问题

这是博客搬家到博客园之后的第一篇文章,也是我最近对微博社交圈子挖掘的一些思考和总结,最近主要的思考和研究,主要针对一下几个问题:

  • 层次性
  • 重叠性
  • ego network
  • 有向社交网络
  • 带权社交网络
  • 统一解决上面的问题(!)

这几个,都是社交圈子挖掘时候我们所面临的问题,在挖掘逐渐深入的过程中,问题会一个一个显现出来。我们就要一个一个解决掉,最后要能够统一在一个方法,一个框架中。我在思考的过程中,也阅读了之前的研究,绝大部分都是针对其中的一个问题,或者两个问题。很少能够解决全部的问题。那我下面尝试分析一下这些问题的产生原因,以及一些可尝试的方法。

层次性

层次性是一个社会属性,在我们的社交圈子中非常的明显。比如,我的一个大一点的圈子是计算所,小一点的圈子是实验室。这种层次结构非常多,很多这个包含关系的层次结构。而且,层次结构也是很重要的,在网络中学习、了解网络的结构性质很有帮助。有一个应用,比如说,猎头在找人的时候,想知道哪些人都是百度的,可是并不是每个人都在自己的profile中写了公司是百度的资料,这个时候,就可以通过圈子挖掘的算法,将潜藏的信息挖掘出来。不同的层次,可能代表着公司中的不同的组。这个需要在实验过程中,自己体会,很有乐趣。针对层次性的问题,一个很直接的揭发就是层次聚类。可以根据不同的阈值获得不同层次的结果。不过,这个方法,要针对不同的层次,设定不同的阈值,并不是那么直接。

重叠性

这个是有社会中人的属性决定的:人会有小学同学、中学同学、大学同学、以前的同事、现在的同事、家人,兴趣小组等等关系圈子。首先,以个人为中心,个人出现在所有的这些圈子中(这也是下面要谈的ego network的问题),具有重叠性。另外,现实中,我的小学同学可能是在中学、大学都是同学,甚至非常有缘分的,工作了还是同事。所以重叠性是客观存在的,我们要正视这个问题。目前,在我的实验中,k-clique算法,针对重叠性,要过比较好。我之前的博客,也有介绍,大家可以看看效果。不过,一般的聚类和基于图划分的方法,都不具备这个特点。但这是很重要的一个性质。

Ego network

以前,在做社交网络的时候,并没有明确提出要针对个人、以个人为中心进行检测。基本都是对整个网络进行划分,对划分的评价也是针对整个网络进行的,比如Q函数。那为什么要构建ego network,以个人为中心进行检测呢?直观上说,没有问题。那么深层的原因呢?这个仍旧要从社会因素、社会的个体因素的角度理解。以微博为例(微博可以认为是一个社会的缩影),微博上的用户活跃度不同,最直观的表现有:1)更新微博比较频繁;2)关注、粉丝比较多;3)关注、粉丝变化也比较多。有的用户喜欢和朋友们交流,有的用户不喜欢。有的用户觉得微博是媒体,有的用户觉得微博是SNS。这些特点,都会让不同用户的关注、粉丝结构变化比较大。间接的结果就是用户的圈子大小、多少不同。所以,圈子挖掘要针对个人构建ego network,然后对该网络进行分析等。既然是针对不同的用户,构建不同的个人网络。我们是否还能够采用统一的阈值呢?当然不能。所以,针对不同的用户,学出相应的阈值,是非常重要的。这也是我最近研究的重点之一。

有向和带权的社交网络

我在做社交圈子挖掘的时候,主要针对的是微博。由于微博自身的媒体、SNS的性质,微博的关系是有方向的。所以,我们在挖掘过程中,是否能够充分利用这一点呢。另外,产生关注关系的原因有很多,比如有的人会碍于面子的原因关注的。还有,用户之间的交互有的多有的少。这些因素就直接导致了,社交网络是一个带权的网络,社交网络中的边的权重,可以理解为用户之间的紧密度。我们可以考虑不同的紧密度计算方法。比如互相转发,评论,@的次数之类的。总而言之,充分考虑方向和权重的因素。能够很大程度上提升效果。在我的尝试方法中,这两个也是重要的因素。

总结

上面干巴巴的说了很多问题。可能不是很有趣,但确实是我们在做社交挖掘过程中需要注意的问题。上面是一些点,如何将这些点,有机的结合在一起,将是一件更有挑战的事情。到目前为止的研究,已经有一些尝试,我会逐渐在后续的博客中,和大家分享。

后记

博客写多了,就会发现,大家更喜欢有例子,有数据,有结果的博文。所以,我想类似这种概述性质的,还是少写为妙。多将一些论文中的观点总结,写出来,实现并且给出结果。这样会更有帮助,让大家直观的知道这些方法的优缺点。我想我更多的路子,会是这样。并且,我真心希望更多的关注社交网络的同学一起讨论。我们国内也可像国外的大学一样,做出一些社交网络挖掘的工具,让老外用我们的。

计算微博垂直领域的传播力排名

这几天,我计算了几个领域的PageRank,包括投资人,程序员这种大的垂直领域,也包括“机器学习”“数据挖掘”等这样的小的领域。在挖掘的过程中,也遇到很多有意思的事情。不过,做这个,并不是要给谁排座次,只是想尝试挖掘出来一些有意思的东西。

下面是我通过“机器学习”“数据挖掘”“信息检索”等关键字找出来的一批人,然后再计算排名得到的结果。后面一列是粉丝数。不过一些新开通微博的牛人:@余凯 @老师木 尚不在其中。我的数据是之前的一个快照。

这样的一个排序,和粉丝的数量关系就不太一致了。所以,垂直领域,还是能够做出很有意思的东西的。可以进一步挖掘,到底哪些因素影响了某一排名。

  • 张栋_机器学习 48966
  • 李航博士 20336
  • 刘挺 44324
  • 孙茂松 6147
  • 沈浩老师 30236
  • 马少平THU 6964
  • 小蚊子乐园 37021
  • 王斌_ICTIR 7032
  • 刘铁岩 11266
  • 王海峰_百度 10679
  • 白硕 SH9930
  • ICTCLAS张华平博士 4714
  • 刘群MT-to-Death 3261
  • 郑来轶 10421
  • 张磊IDMer 6571
  • 谢幸Xing 14620o

综合一下这些事情,可以得出,对微博博主进行PageRank计算,得到的结果的含义:每一个博主的PageRank值,直接代表了博主的传播力。具体点说,就是博主发布一条微博消息,能够传播覆盖多少人,越多传播力越到,PageRank越大。很多同学会讲,这个不就是粉丝的数量么?不是的,粉丝本身有的质量高,有的质量低,实际上能够影响多少人,这个是需要衡量的。举一个例子,某一个博主300w粉丝,大部分买来的僵尸粉,而另外一个博主,只有3w,都是一个一个积累起来的。对于做营销而言,哪个更好呢?显然是后者。PageRank在一定程度上,就是起到了着作用。

PageRank是一种计算的框架,一种计算的方法。在这个框架下,我们可以有很多的改进,比如就拿上面的这些人来看,我们如果想要计算专家能力排序,应该怎么做呢?仅仅是有关注,就确切表示一条边么?其实在网络建模的过程中,我们有很多的基础可以用来加强模型,或者利用不同的信息,为不同目的建立模型。比如,这条关注的边强度有多大呢?如何来衡量,一个很有用的点就是微博上两个人之间的交互信息。这个很重要,新浪可以做很多事情。

社交网络时代,数据为王。我们有很多工具,很多算法可以来做挖掘,但是,没有数据,都是白费心思的。尤其是涉及到网络的一些挖掘,网络规模达到一定程度,好多性质是不会涌现出来的。

希望和更多的同学一起交流。

计算的工具依然是graphchi,非常好用。限定领域这块儿,我做的比较粗糙,目前就是通过关键字去检索。只要匹配上了,我就认为这个博主是该领域相关的。这部分,也是需要一些工作量的。也是很有意思,很有价值的一块儿工作。