你好,游客 登录 注册 搜索
背景:
阅读新闻

挖掘数据流 Mining Data Stream

[日期:2015-02-27] 来源: Ryan的博客  作者: Ryan [字体: ]

数据流挖掘:

  1. 输入元组通过一个或多个端口快速地进入
  2. 系统无法存储整个数据流
  3. 在有限内存的条件下对数据流做出一些计算

对数据流的两类Query:

  1. Ad-hoc queries,例如当前数据流中的最大值是多少
  2. standing queries, 例如每当数据流中出现了新的最大值就汇报一次

滑动窗口:

  • Query时总是针对数据流中固定长度N的一个窗口(最新进入系统的N个数据)
  • 或者:最近T时间内进入系统的数据

当窗口的长度大到无法存储于主存内时,或者有太多不同数据流,内存不够存储多个窗口,则需要更有趣的方法。

例子:平均数

  • 数据流为一个个整数
  • 窗口尺寸N
  • standing query: 当前窗口中数字的平均值为多少?

方法:

  1. 对于前N个数据,计算其平均值A
  2. 对于每一个新来的数据i,找到当前窗口中最旧的数据j,更新平均值为AA+(ij)/

 

Counting Bits 问题:

 

  • 给定一个数据为01的数据流,希望回答的问题是:最近k个数据中有多少个1kN
  • 如果存储最近的N个数据,很容易回答。
  • 假设N,k均很大,并且有非常多数据流同时流入并且需要计算,无法这样做。

DGIM算法:

  • 对每一个数据进行timestamp
  • 对窗口内的数据进行summary为一个个bucket
  • 每个bucket代表窗口内报括了2i1的一段数据流,记录为(该段的末尾位置,2i2i为该bucket的大小
  • 如果同样大小的bucket出现了3次,就进行合并,丢掉时间戳较老的,更新较新的那个味(该段的末尾位置,2i+1)

QQ截图20150226231451

 

Query,最近k个数据中有多少个1

 

  • 只看结尾时间在最近k时间以内的bucket
  • 将所有bucket的大小加起来,最旧的一个bucket的值只算一半
  • 这样的误差,最大可能会有50

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
defdgimTimeStamp(stream,windowSize,t=0,buckets=dict()):
    # input n to add a new bit
    # input e to exit program
    # input a number ot query
    sizes=[2**iforiinrange(int(round(math.log(windowSize,2))))]
    whileTrue:
        option=raw_input('e to exit; n to add 1 bit; any number to query  ')
        ifoption=='n':
            # remove too old buckets
            timestamp=t%windowSize
            forkey inbuckets.keys():
                ifkey==timestamp:
                    buckets.pop(key)
            # adding a new bit in
            ifstream[t]==1:
                buckets[timestamp]=1
            t+=1
            # buckets cascading updating
            forsize insizes:
                ifsum(np.array(buckets.values())==size)==3:
                    keys=[bforbinbuckets.keys()ifbuckets[b]==size]
                    foriinrange(len(keys)):
                        ifkeys[i]<=timestamp:
                            keys[i]+=windowSize
                    keys.sort()
                    tbr=keys[0]
                    iftbr<windowSize:
                        buckets.pop(tbr)
                    else:
                        buckets.pop(tbr-windowSize)
                    tbm=keys[1]
                    iftbm<windowSize:
                        buckets[tbm]*=2
                    else:
                        buckets[tbm-windowSize]*=2
            ift>=len(stream):
                break
        elifoption=='e':
            break
        else:
            k=int(option)
            keys=[i%windowSize foriinrange(t-k,t)]
            initial=True
            s=0
            forkey inkeys:
                ifkey inbuckets andinitial==False:
                    s+=buckets[key]
                ifkey inbuckets andinitial==True:
                    s+=buckets[key]*0.5
                    initial=False
            prints,t
        printbuckets
 
 
    returnbuckets,t
 
stream=[1foriinrange(99)]
 
b,t=dgimTimeStamp(stream,5)
 
 
eto exit;nto add1bit;anynumbertoquery  n
{0:1}
 
eto exit;nto add1bit;anynumbertoquery  n
{0:1,1:1}
 
eto exit;nto add1bit;anynumber to query  1
0.52
{0:1,1:1}
 
eto exit;nto add1bit;anynumber to query  2
1.52
{0:1,1:1}
 
eto exit;nto add1bit;anynumbertoquery  n
{1:2,2:1}
 
eto exit;nto add1bit;anynumbertoquery  n
{1:2,2:1,3:1}
 
eto exit;nto add1bit;anynumbertoquery  n
{1:2,3:2,4:1}
 
eto exit;nto add1bit;anynumbertoquery  n
{0:1,1:2,3:2,4:1}
 
eto exit;nto add1bit;anynumbertoquery  n
{0:2,1:1,3:2}
 
eto exit;nto add1bit;anynumber to query  2
2.07
{0:2,1:1,3:2}
 
eto exit;nto add1bit;anynumber to query  4
4.07
{0:2,1:1,3:2}
 
eto exit;nto add1bit;anynumber to query  e

原文链接:http://www.ryanzhang.info/archives/2569?utm_source=tuicool





收藏 推荐 打印 | 录入:Cstor | 阅读:
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数
点评:
       
评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款