report - 数据挖掘报告


NAME

report - 数据挖掘报告


AUTHOR

章亦春 <agentzh@gmail.com>

3030602110 计算机0304班

计算机科学与通信工程学院 江苏大学


VERSION

   Maintainer: Agent Zhang <agentzh@gmail.com>
   Date: 6 Jan 2007
   Last Modified: 7 Jan 2007
   Version: 0.02


DESCRIPTION

这篇报告描述了我为数据挖掘课程进行的 OLAP 应用研究。研究对象是 Pugs 团队两年以来在 IRC 聊天通道 #perl6 中的日志以及 Subversion 版 本控制仓库中的提交日志。

Perl 6 是下一代的 Perl 语言,而 Pugs 是当今世界最完整的 Perl 6 编译器项目。 其团队成员遍布全球各地。我也于 2006 年夏天加入了该团队。

本文档详细地描述了从原始数据的获取,到数据入库,再到查询操作,以及查询结果 可视化,知识化的全过程。


数据来源

获取 #perl6 原始日志

#perl6 原始日志的自动下载

#perl6 通道的聊天记录来自 http://colabti.de/irclogger/irclogger_logs/perl6. 它是以 HTML 页面的形式发布,且日志每分钟都在积累。

我在 2006 年夏天开发了 get-irc-logs.pl 脚本,自动从该位置取得每一天的聊天日志。 该脚本位于 Pugs 项目仓库内:

http://svn.openfoundry.org/pugs/util/get-irc-logs.pl

为了方便定期同步,该脚本在默认情况下只下载需要更新的日志(除非指定 -f 选项)。

#perl6 原始日志的格式解析

每一天的日志都使用的是类似 mIRC 日志格式的形式进行记录的:

    [10:32] <nothingmuch> actually it can be prettier
    [10:32] <gabor529> ?eval my @a=("x", "y", "z"); say "{@a}";
    [10:32] * jisom loves syntax highlighting
    [10:33] <nothingmuch> ?eval "my @bar = <a b c>; say "foo{@bar}.com"
    [10:33] <evalbot_9350> OUTPUT[x y z ] bool::true 
    [10:33] <nothingmuch> and you can also use q:a{ }
    [10:39] *** Barry left perl6
    [10:39] *** Gothmog_ joined perl6
    

其中开头方括号里的为消息发送时间,后面尖括号里的是消息发送者,最后才是消息内容。 以单个 * 开头的消息为“IRC 动作”,是用户消息的一种特殊形式。当用户 foo 发送 IRC 命令 /me does something, 则在日志中便会显示 * foo does something. 三个 * 起始的消息为 IRC 系统消息。在我这儿的研究中,忽略系统消息。

基于此格式,我用 perl 实现了该日志格式的解析器 parse-irc.pl,自动生成 YAML 格式的数据文件供后面 的数据库导入程序读取。parse-irc.pl 的源代码位置如下:

http://svn.berlios.de/svnroot/repos/unisimu/Jifty/PugsPP/bin/parse-irc.pl

典型的 YAML 输出片段如下:

  - 
    content: ingy screams
    msg_type: A
    sender: ingy
    sent: 2005-03-02 01:28
  - 
    content: and that will never change, because the one thing that is constant is change
    msg_type: N
    sender: mugwump
    sent: 2005-03-02 01:29
  - 
    content: MakeMaker is a whore
    msg_type: N
    sender: ingy
    sent: 2005-03-02 01:31
  -

其含义基本上都是自解释的 (self-explanatory). 唯一需要说明一下的是 msg_type. 它指示了消息 的类型 (message type). 其取值目前只有两种:N (普通消息)和 A (动作)。

编码转换

事实上在解析过程中有不少需要特别考虑的细节。比如,#perl6 通道中的聊天者来自世界各地,因此 虽然大部分时间,大家用的都是英语,但经常也会夹杂进非英语国家的文字,比如汉语、拉丁语、甚 至希伯来语。如果所有 #perl6 用户的 IRC 客户端发送的消息都采用 UTF-8 编码,那么不同民族的文字 就不会对我的解析器造成影响,毕竟 UTF-8 者,压缩后的 Unicode 也。不幸的是,许多 IRC 客户端都 默认使用用户的本机多字节编码。例如许多台湾的繁体中文的消息使用的是 big5-eten 字符集,许多 大陆这边的简体中文消息又使用的是 gb2312 字符集,而许多含有特殊拉丁字母的欧州文字的消息又是 用 latin-1 进行编码的。这些字符集彼此不兼容,因此需要特别的识别算法,并将之统一地转换为 UTF-8.

利用 perl 的 Encode::Guess 模块可以很好地区分出 UTF-8, gb2312, 和 big5-eten 这些编码。 同时也可以很好地区分出 UTF-8, latin-1 这些编码。但是 latin-1 与中文字符集却是存在着很大的 交集的,而 IRC 的消息体一般极短,Encode::Guess 较难正确区分二者。因此我在 Encode::Guess 基础之上根据汉语和拉丁语与 ASCII 字符之间的位置关系,又引入了一些简单的启发式规则,从而提高了 编码的正确识别率。如果一条消息的编码没有正确识别,那么它们在数据库中以 UTF-8 格式存储时就是 乱码。

创建数据库

为便于后续进行大规模的统计分析,我们需要将 #perl6 日志导入到真正的关系型数据库中。

这里我们使用 Jifty 的数据库抽象层来创建数据库模型,这样我们的数据库模式可以透明地运行在 SQLite, PostgreSQL, MySQL, 和 Oracle 等多种主流的 DBMS 之上。

数据库的模式定义直接使用 Jifty::DBI 声明式的 perl 代码。首先是 IRCMessage 模型的定义, Jifty 自动将之映射到底层 DBMS 中的 ircmessages 数据库表格,并生成相应的 OO 包裹类。

    package PugsPP::Model::IRCMessage;
    use Jifty::DBI::Schema;
    use PugsPP::Model::IRCSession;
    use PugsPP::Record schema {
        column sent =>
            type is 'timestamp',
            label is 'Sent time',
            is mandatory;
        column sender =>
            type is 'varchar(32)',
            length is 32,
            label is 'Sender',
            is mandatory;
        column content =>
            type is 'text',
            label is 'Content',
            render_as 'Textarea',
            is mandatory;
        column msg_type =>
            type is 'char',
            label is 'Type (Action/Normal)',
            valid_values are qw/A N/,
            is mandatory;
        column irc_session =>
            refers_to PugsPP::Model::IRCSession by 'id',
            #render_as 'Text',
            label is 'IRC Session',
            is mandatory;
        column session_offset =>
            type is 'integer',
            label is 'Offset in its session',
            validator is sub { $_[0] >= 0; },
            is mandatory;
            };

这些代码的含义基本上都是不言自明的。唯一需要解释一下的是 irc_session 和 session_offset 这两个属性。为了方便对聊天的“段落”进行分析,我将原始的 IRC 消息按照时间人为地分割为许 多个“组”,或者说是“会话”(session). messages 表中的 irc_session 是一个外键,指向 sessions 表的 id 字段,而 session_offset 则是当前消息记录在所属 session 中的偏移量(或序号),从 0 开始。

Session 模型的定义如下:

    package PugsPP::Model::IRCSession;
    use Jifty::DBI::Schema;
    use PugsPP::Record schema {
        column begin_time =>
            type is 'timestamp',
            label is 'Begin time',
            is mandatory;
        column end_time =>
            type is 'timestamp',
            label is 'End time',
            is mandatory;
        column msg_count =>
            type is 'integer',
            label is 'Message count',
            is mandatory;
        column speakers =>
            type is 'text',
            label is 'Selected Speakers';
            };

其中的 speakers 只存放当前 session 中最活跃的说话人的名字列表,以空格分隔。

定义好上面的两个 .pm 文件之后,建立数据库及相应包装类就只需要一个命令:

    $ jifty schema --setup

在本次分析中,我在项目配置文件 Config.yml 中指定使用的数据库为 Pg, 即 PostgreSQL.

将数据导入库

使用 Jifty 的好处在于一行 SQL 代码都不用写。导入库时,我同样不会编写任何 SQL 代码, Jifty::DBI 会根据需要,在底层自动为我生成 select 语句,insert 语句,和 update 语句。 一切数据库方面的细节对我来说,都是透明的。

前面我已经编写了 parse-irc.pl 脚本,将原始的 .log 日志文件“编译”为 .yml 数据文件。 这里我又编写了 import-irc.pl 脚本,负责将 .yml 中的数据导入到上一步建立的数据库中。

import-irc.pl 使用了 Jifty 自动为数据库表格生成的面向对象包装类,来完成数据的导入 工作,并能够自动避免相同的 IRC 消息的重复导入。其源代码位置如下:

http://svn.berlios.de/svnroot/repos/unisimu/Jifty/PugsPP/bin/import-irc.pl

获取 Pugs SVN 仓库的提交日志

两年以来,Pugs 的 SVN 仓库中已经积累了数量惊人的 commits (提交)。在编写本文档时, Pugs 的 head 已经达到 revision 15006 了。

为了获取这 15000 次提交的日志记录,我借用了唐凤 (Audrey Tang) 在 feather 服务器上 的 svk 历史记录。从而只用一个命令就从她的 svk 仓库中导出了所有 Pugs 提交的日志列表:

    $ svk log -q > pugs.log

该日志文件可以从我在 feather 上的个人网站获得:

http://perlcabal.org/agent/pugs.log

其中的典型片段如下所示:

    ----------------------------------------------------------------------
    r42425 (orig r14931):  Ovid | 2006-12-20 22:10:40 +0100
    ----------------------------------------------------------------------
    r42424 (orig r14930):  andara | 2006-12-20 16:57:09 +0100
    ----------------------------------------------------------------------
    r42423 (orig r14929):  wolverian | 2006-12-19 18:24:10 +0100
    ----------------------------------------------------------------------
    r42422 (orig r14928):  lwall | 2006-12-19 09:31:47 +0100
    ----------------------------------------------------------------------
    r42421 (orig r14927):  luqui | 2006-12-19 01:47:53 +0100
    ----------------------------------------------------------------------
    r42420 (orig r14926):  luqui | 2006-12-19 00:15:47 +0100
    ----------------------------------------------------------------------

第一个 revision 数为 svk 自己的版本号,(orig rXXXX) 中的才是 SVN 仓库中真正的 版本。 Ovid, andara, wolverian 都是提交人的用户名。最后则是提交时间。像 +0100 这 样的数字表示时区。

我又编写了一个小脚本用来将这些 SVK 提交日志导入到数据库中:

http://svn.berlios.de/svnroot/repos/unisimu/Jifty/PugsPP/bin/import-svn.pl

数据库中只有一张数据表与之对应。其 Jifty::DBI 模式描述如下:

    package PugsPP::Model::SvnLog;
    use Jifty::DBI::Schema;
    use PugsPP::Record schema {
        column committed =>
            type is 'timestamp',
            label is 'Committed',
            is mandatory;
        column committer =>
            type is 'varchar(31)',
            label is 'Committer',
            length is 31,
            is mandatory;
        column revision =>
            type is 'integer',
            label is 'Revision',
            is distinct,
            is mandatory;
            };

这里并没有像导入 #perl6 日志那样通过 .yml 过渡。这主要是因为 SVK 提交日志的格式已 经足够简单了。


对 #perl6 聊天记录的分析

以月份作为归约粒度

首先我通过 irc-year.pl 脚本自动绘制出 #perl6 通道在指定年份和发信人的情况下,消息数目 随时间的变化曲线。

irc-year.pl 的源代码位于下面的位置:

http://svn.berlios.de/svnroot/repos/unisimu/Jifty/PugsPP/bin/irc-year.pl

通过命令

  $ irc-year.pl 2005

  $ irc-year.pl 2006

可以分别得到下面这 2 张 #perl6 通道所有用户按月统计的消息数目的时间序列图:

#perl6 logs for all

      

从这两张曲线图,我们不难看到以下事实:

而通过命令

  $ irc-year.pl -u 2005 autrijus% audreyt%

  $ irc-year.pl -u 2006 audreyt%

则可以分别得到唐凤在 2005 和 2006 年的消息数随时间变化的曲线:

#perl6 logs for Audrey (Autrijus) Tang

      

之所以使用 % 后缀是因为 IRC 用户名 foo 时常会有 foo_ 和 foo1 这样的变体。

从唐凤的聊天消息的变化曲线,我们不难看到,她的活动与整个 #perl6 通道的活动 是密切关联的。两条曲线在形状上非常接近。

#perl6 logs for Larry Wall

类似地,我们可以得到 Larry Wall 的聊天趋势:

  $ irc-year.pl -b 6000 -u 2005 TimToady%
  $ irc-year.pl -b 6000 -u 2006 TimToady%
      

我们看到,Perl 的创造者 Larry Wall 在整个 2005 年只是阅读 #perl6 日志,而并没有真正加入。 而到了 2006 年初,Larry 终于现身了。Audrey 他们把几乎不可能的事情变成了现实!随后,Larry 以 TimToady 的名字在 #perl6 通道里的活动便变得一发不可收拾。事实上,从下面这张饼图,我 们可以看到 Larry Wall 早已摘得了 2006 年 #perl6 消息数量的亚军!

    

#perl6 logs for Yuval ``nothingmuch'' Kogman

      

#perl6 logs for Gaal Yahas

或许 Gaal 的活动规律是最让人捉摸不透的了,呵呵。

      

看起来 Gaal 似乎是每两个月休息一次。

#perl6 logs for Mitchell N ``putter'' Charity

putter 的活动曲线也非常有“个性”:

      

#perl6 logs for myself (Agent Zhang)

我自己的活动曲线就比较无味了:

      

虽然大部分时候我都是“无线电静默”,但我从 Pugs Day 1 就开始密切关注她了。呵呵。我 是去年(2006年)夏天才在 #perl6 现身的。说实话,是受到唐凤在她的 Pugs 博客留言的“鼓励”。 之所以从 9 月份我在 #perl6 的活动开始下滑,是因为大学里的学业实在是太重了……唔唔…… school-- school-- school--

以日作为归约粒度

以日作为粒度对每月的消息数进行统计似乎并不是特别有趣:

    

很像是白噪声信号,对吧?呵呵。

上面的图片由我的 irc-month.pl 脚本自动绘制。对应的命令如下:

  $ irc-month.pl 2005 03

其源代码位于

http://svn.berlios.de/svnroot/repos/unisimu/Jifty/PugsPP/bin/irc-month.pl

类似地,唐凤(唐宗汉)在 2005 年 3 月,即 #perl6 通道最活跃的时候的活动如下图如示:

    

生成上图的命令为

    $ irc-month.pl -u 2005 03 autrijus%

对单个月进行统计不会得到特别有意义的规律。日后应对各个月份的活动进行叠加后求平均, 或许就可以看到一些有趣的现象了。


对 SVN 提交日志的分析

如果 #perl6 是“说”的地方,那么 Pugs SVN repos 则是“做”的地方。说得再多,做得少,显然也 没什么意义,呵呵。分析表明,Pugs 团队是说得多,做得多的地方。;-)

我编写了 svn-year.pl 脚本来帮助进行数据分析。其源代码位于

http://svn.berlios.de/svnroot/repos/unisimu/Jifty/PugsPP/bin/svn-year.pl

整体上的 SVN 提交数目变化

    $ svn-year.pl -u 2005
    $ svn-year.pl -u 2006
      

我们看到,新的 SVN 提交的数量随时间的变化曲线与 #perl6 的活跃度基本吻合。

Pugs 团队的领袖唐凤的提交数目变化

    $ svn-year.pl -u 2005 autrijus audreyt
    $ svn-year.pl -u 2006 audreyt
      

我们再一次看到了她在 Pugs 团队中的主导作用。

Larry Wall 的提交数目的变化

      

Larry Wall 对 Pugs 的贡献始于 2005 年 11 月。我还记得当时我第一次看到 lwall 的提交信息时 有多么的激动和振奋,呵呵。

虽然 Larry 的上传数量不是很大,但我们看到一直都在稳步增加。至于 2006 年 12 月份的急剧下滑 多半是因为圣诞家庭聚会和新年聚会什么的。哈哈。

fglock 的提交数目变化

      

fglock 是 perl 版本的 perl 6 regex 实现 Pugs::Compiler::Rule 的作者,同时也是 MiniPerl6 和 KindaPerl6 编译器重要的设计和开发者之一。他对 Pugs 的贡献感觉上每天都在持续。fglock++

SVK 的作者 clkao 的提交数目变化

      

看上去 clkao 主要是夏天的空闲时间多一些。他在 2006 年的曲线让我联想到了“正态分布”函数。呵呵。

我自己的提交数目变化

      

感觉很惭愧啊,呵呵。只是在去年夏天“疯狂”了一把。哈哈。真想天天都“疯狂”耶。可以咱们大学不给我 这样的机会呀。


Pugs 贡献者的统计与分析

贡献者总数随时间的变化

为得到 Pugs 团队成员在各个时刻的个数,我利用下面的 SQL 查询来得到每一个贡献者首次 SVN 提交 的时间戳:

   select min(committed) as first_time
   from svn_logs
   group by committer
   order by first_time

然后再对每一个人首次提交的时间按照时间进行累积,并可以得到成员总数随时间的变化:

      

看!到 2006 年底,有接近 200 个 committers 耶!他们来自世界各地!

新增贡献者数量随时间的变化

新增成员的数据获取与上一步相同,只不过这一次不再对成员数目进行累积了。

      

活跃的贡献者数量随时间的变化

这里我们使用类似下面的 SQL 语句来完成查询:

    select count(committer)
    from svn_logs
    where committed >= '2005-03-01 00:00' and
        committed < '2005-04-01 00:00'
    group by committer
      

有趣的是,新增贡献者数目的变化, 活跃贡献者的变化,#perl6 消息数和 SVN 提交数的变化 在曲线的形状上都很接近。


图片的自动化生成

上面的折线图和饼图都是利用 CPAN 模块 GD::Graph 自动生成的。详情请见:

http://search.cpan.org/dist/GDGraph


性能问题

如果要把 OLAP 真正搬到 Jifty 应用中,成为真正的“在线分析”的话,需要对 data cube 进 行预计算,否则数据库查询所花的时间无法满足浏览器用户的交互需求。


更多有趣的挖掘

 report - 数据挖掘报告