21-网络信息体系结构课程项目报告

'网络信息体系结构课程项目报告——BBS信息挖掘系统第21组朱嘉奇刘丹星李希婷田枫第一部分项目计划如今，BBS已经成为了我们学习生活中不可缺少的一部分，它不仅是我们获取信息的重要途径，更是我们结识朋友、相互交流的重要场所。BBS上的用户数量非常大（北大未名BBS有ID八万六千多个），而用户并不是孤立存在的，他们之间可能存在认识的关系，以这种“认识”关系为基础，可以构造出一个关系图，通过分析与挖掘这个关系图，我们可以获得很多有用的信息。例如，关系图的一个连通分支中的人很可能彼此认识（直接或间接），那么他们就构成了一个团体，该团体可能对应现实中的一个班或一个协会。BBS管理员利用此信息可以从另一个角度分析各个版的热门程度。如果在一个版发文的id基本属于同一个小团体，说明该版的人气不是很高。而如果这些id分布在许多团体中，则说明该版能吸引多类用户。我们甚至可以猜想，如果这些id同属于一个或几个很大的团体，是否可以说这个版是许多用户互相认识的桥梁呢？而对于普通用户，系统可以帮助他找到结识某个人的途径，从而简化认识过程。基于上述想法，我们决定设计一个BBS信息挖掘系统，以北大未名BBS为对象，建立用户关系网，并以此为基础进行各种分析挖掘，为BBS管理员和用户提供更多的信息和方便。我们的系统只是一个初步的尝试，今后，随着技术上的不断成熟，还可扩展到其它校园BBS甚至更复杂的论坛中，并使系统的功能越来越强大。第二部分系统功能及完成情况1.功能我们的系统主要提供以下功能：1、建立关系图：抓取BBS上的网页，通过文集发文情况与回文情况建立关系图。该图为有向带权图，图中结点为BBS上的用户ID，结点之间有边相连，边的权值则为两个ID之间的认识程度。程序第一次抓取时抓取BBS上的几乎所有网页并建关系图，以后则只需更新关系图，即，只处理上次抓取后更新的网页。 1、将ID分类：根据关系图，对BBS上的ID分类。分类针对不同的认识程度分别进行，即每次分类时，用于判断两个ID是否认识的标准不同，分高、中、低三等。分类结果保存于数据库中。注：每次更新关系图后，需要重新分类以保证结果的准确。2、Top10：显示在三种认识程度下（即分别以三种权值为判断是否认识的依据）认识人最多的ID和被认识最多的ID。3、查看某ID的认识情况：输入ID，系统计算出他所认识的所有ID或认识他的所有ID（认识或被认识由用户选择）。在使用时，用户可以设定一些参数，包括认识程度（高、中、低），以及显示在图中的点数。由于图中点太多会影响图的清晰程度，因此图中只显示认识程度较高的点，其他的点将在左侧列出（效果见下图）。4、查看两个ID之间的最短路径：输入两个ID，A与B，系统计算出两个ID之间的距离和最短路径，即A通过哪些人可以认识到B或A通过哪些人可以被B认识。在输入ID时，用户也可以改变参数，可以选择认识程度，以及关系图是有向还是无向。如果A不想通过路径中的某些人来认识B，可以点击该ID，系统会给出一条不含该ID的新路径。通过这项功能，用户可以查看他与Top10中的id之间的距离以及一条路径。5、查看某ID的间接认识输入ID，系统计算出他可以间接认识哪些人，或被哪些人间接认识。同样，这里也可以选择认识程度。用户还可以选择距离上限，即最多通过几个人间接的认识某ID。2．实现情况系统使用MFC开发，构造出的关系图以邻接表的方式存储于sqlserver数据库中。具体实现策略将在第三部分进行讨论。系统界面如下：（以查看好友功能的界面为例） 图中蓝色的点为用户输入的中心点，图中各点与蓝色点之间距离越短说明认识程度越高，红色点为与蓝色点认识程度最高的ID。，第三部分实现文档1.对网页的抓取虽然未名BBS提供好友功能，但是我们无法获得好友记录、信件、消息等等对判断两个ID是否认识非常有帮助的信息，只能通过分析文集的发文情况和各个版面的回文情况来进行判断。这就需要我们抓取文集的访客留言，连目以及所有版面的文章。l抓取文集的问题由于未名文集的命名格式不够规范，抓取文集遇到不少问题。1。文集中最有用的信息是留言本，这基本上反映了用户之间的主要互动之一。然而留言本的命名多种多样，并不是每个文集都会显式指出哪个目录就是留言本。分析网页的时候遇到指明“留言”的url当然好，更多的时候需要以广度优先的顺序层层深入每个目录，分析每篇文章的署名（id），不与文集主人重名以及不是“guest”登录的才有保存的价值2。文集中另一个麻烦的地方是目录创建者的名字可以不是用户的id，可以是任意的值。幸好文集的目录创建者一般都是文集拥有者，而留言文件的创建者只能是用户的id，因此我们只关心文件的创建者 3。连目也是一个很重要的信息来源，然而连目的整理者和目录一样，也是可以随意改动，因此没有参考的价值。只有超链接的url的最后部分能够如实的反映连向文集的拥有者的真实id。可是连目不一定连向文集，可能连向讨论区的精华区，也可能连向文集，但只连到文集中某一个目录，这些都是要特别处理的情况。当然有的用户可能没有文集，有的可能有隐藏目录甚至有的用户文集是隐藏的，这些情况只能忽略了。同时考虑到效率，也不可能爬遍整个文集，在程序中只爬了前三层。l抓取版面文章的问题1.对版面的分析给定两个IDA和B,weight_re[A,B]记录IDB对IDA的文章进行回复的总数.weight_re[A,B]=1，当且仅当IDB对IDA的某篇文章进行了回复。并且只要IDB对IDA的某篇文章中进行了回复,weight_re加1.北大未名BBS共有讨论区546个,除去系统类32个和校务类13个(因为这两类对分析ID间的关系帮助很小),共有讨论区501个.对每个讨论区的所有文章依次分析.对于每篇文章,若文章数是1,说明无人回复,不用进行分析.若文章数大于1,对文章内容进行分析,用HostID记录发文的ID,用IDList记录对该文进行回复的ID,重复的不放入IDList.分析完后,将HostID与IDList中的ID的weight_re值分别加1.所有版面分析完后,字段weight_re[A,B]的值就是IDB对IDA的文章进行回复的总数.BBS系统中,系统版务通常会把与当前时间间隔较长的文章的回复删掉,只留文章原文.所以,较早的文章的文章数通常都是1.利用这个特点,对每个讨论区进行分析时,不需要一直找到第一篇文章.程序处理时,若发现当前页的所有文章的文章数都是1,就不再对上一页进行分析,直接分析下一个版.2.进一步的改进1.分析文章时,对于文章数是1的,认为是无人回复,没有进行分析.这里忽略了文章是合集的情况.下一步的工作中,可以增加对合集的分析.2.分析每个讨论区时,若发现当前页的所有文章的文章数都是1,就不再对上一页进行分析,直接分析下一个版.这里只是一种近似处理.忽略了某些版最新页文章数都是1但上一页的文章的文章数会多起来的情况.下一步的工作中,还应针对这种情况进行具体分析.3.表中的weight_re[A,B]每加1,说明IDB对IDA的某篇文章进行了回复.然而,同一篇文章中,IDB可能只回复一次,也可能是多次,甚至是多次往复的回复,而如果都只记做1,似乎会丢失一些信息.下一步的工作中,可以回复的情况进行更细致的分析.如记录回复的次数,以及是否是双向的回复等.2.权值的选取、计算以及阈值的选取如何分析id之间的联系，并用数值表示出来，是本系统将要面临的主要技术问题。bbs中用户（id）之间的关系是通过对两类关系设定权值进行综合计算的，一是用户之间存在相互回复文章的关系，一是用户在个人文集里留言的关系。显然，用户之间相互回复文章的次数越频繁，他们就越有可能认识；一个用户在另一个用户的文集中留言越多，同样他们也越有可能互相认识。当然，这里的“认识”并不完全等同于生活中的认识，而是侧重在bbs环境下用户之间的互动。只要是用户之间的互动频繁，我们就认为他们“认识” 的可能性大。实际上也是如此，就算两个用户在生活中联系不很紧密，只要他们在bbs上互动频繁，则他们至少很熟悉在bbs环境下的对方；反之即使两个用户在生活中很熟悉，但在bbs上没有什么来往，那么他们也未必熟悉在bbs环境下的对方。总而言之，所有对关系的分析都是基于bbs环境的。然而文集和回复文章两种关系的重要程度是不一样的。根据用户在bbs中的行为判断，用户A在用户B的文集中留言与用户C回复了用户B的文章相比，A与B关系的密切程度比C与B关系的密切程度要高。在可获得的bbs信息中，最能准确反映id之间联系的是个人文集中的信息。不过用户之间回复文章的关系也不能忽略，如果两个用户相互回复文章的次数积累到一定数量，他们的关系也很可能非常密切。l简单加权一开始我们考虑的是由于文集中的留言比回复文章能更准确的反映用户之间的关系，因此对A在B的文集中有留言，我们将给这种关系赋予一个较大的权重。而A有回复B的文章，这种关系我们赋予一个较小的权重。用抓取网页分析得到的直接结果，我们累加A在B的文集中留言的次数Corpus_num，累加A回复B的文章的篇数Re_num，然后进行加权求和，公式如下：Corpus_num*Corpus_Weight(文集权重)+Re_num*Re_Weight(回文权重)然而这样得到的结果是有问题的，我们发现实际数据中，文集的留言次数的分布区间比回复文章篇数的分布区间大很多，并且回复文章篇数主要集中在分布区间的低端，再加上文集的权重比回复文章的权重高，因此回复文章这一关系变的无足轻重了。例如用户A回复用户B的文章多达20篇，而在B的文集中没有留言，由公式计算的结果可能他们的关系密切程度算是低的，而在bbs环境下这样的两个用户肯定是关系比较密切的。由此，简单加权的方法会丢失一些重要信息（尤其对回复文章的关系而言）。l分布区间规格化考虑到上述问题的产生是分布区间的不一致造成的，我们考虑分别把文集留言数与回复文章数映射到同样一段区间，然后再相加。例如，文集留言数的分布区间是1-1000，回复文章数的分布区间是1-200，则把回复文章数的分布区间映射到1-1000的区间里。然而这就相当于回复文章数的权重是5，文集留言数的权重是1，反而比回复文章数低了（由于文集留言数的分布区间比回复文章数的分布区间广，这种现象不可避免），这和我们文集留言的关系比回复文章的关系重要这一前提不符，因此也否决。l区间分段映射重新反思一下我们的权值计算方案的目标：1。文集留言的权重比回复文章大2。回复文章数较大的（然而相比文集留言的权值还是小）不能使其被忽略3。文集留言数目很少的（然而计算权值后可能与回复文章相仿）不能使其权值过大我们提出这样的方案：首先把分别文集留言数和回复文章数的分布区间各自划分为4段，每一段对应关系的从小到大4种密切程度——即（很可能）不认识，认识但不一定熟悉，熟悉但不一定是好友，一定是好友。把这4段区间分别映射到[1，20]（很可能不认识），[21，40]（认识但不一定熟悉），[41，80]（熟悉但不一定是好友），[80，100]（一定是好友）4个区间，如下图： 把分别映射后的值相加得到的数落入哪个区间内，就代表这两个用户的关系属于哪一级别。这样做保证了：1。只要单靠文集留言数或回复文章数就可以判断用户关系至少属于某个级别，把两个权值合并后至少不低于原来各自判断出的最高级别。例如：看文集留言数可判断A和B至少熟悉但不一定是好友（落入区间[40，80]），看回复文章数判断A和B很有可能不认识（落入区间[0，20]）他们相加的和落入区间[40，100]，则他们仍然至少是熟悉。2。保证单靠文集留言数或回复文章数就可以判断用户关系至少属于某个级别，把两个权值合并后他们的关系至多上涨一级。这也是比较合理的考虑，因为每一级蕴含的是有可能也属于更高一级，但是距离高两级仍然是比较远的。这正是区间这样设计的原因：如[1，20]和[1，20]区间的数相加不会超过40，[21，40]和[21，40]区间的数相加不会超过80。3。只要大于80就是好友，上界可以不管，保证大于80（好友级别）的无论怎么加都大于80我们不取平均值而求和的原因就是避免低级别的值把高级别的值拉低，从而使已经能够判断出用户关系属于某一高级别在合并权值以后反而变成低级别了。id之间联系的判断方法和相应的权值计算公式将直接决定系统的性能，系统也需要在复杂性和准确性之间进行权衡。本系统从简单情况入手，逐步增加和细化计算公式，使计算结果尽量准确地反映现实中用户之间的认识程度。l文集留言阈值选取考虑在文集中留言不超过2篇的，很有可能与文集拥有者不认识（存在随便去别人文集里逛逛的用户），而与用户认识的一般在文集中发言都大于2篇；留言9篇以上的，可以认为对文集拥有者比较熟悉；而留言20篇以上肯定是好友了。这里考虑的认识是双向的，即A在B文集中留言，则A认识B与B认识A两种关系都应该加一个权值。然而根据实际情况考虑A认识B的权值增加应该比B认识A的大。综上所述，下图可反映这样的映射： l版面文章阈值选取通常认为，如果IDA对IDB的某篇文章进行了回复，有两种可能.一是A和B并不认识,只是对B的文章内容感兴趣,所以进行了回复.或者是A和B已经很熟悉,两个人是在灌水或者聊天.如果weight_re[A,B]=1,或者很小,那么这种回复的偶然性较大,很可能是第一种情况,可以认为A,B并不认识.如果weight_re[A,B]的值很大,那么很可能是第二种情况,即A与B是好友关系.对抓取结果中weight_re的分布情况进行统计,得到下图.按照上述原则,将计算出来的weight_re值分别映射到4个等级,分别表示A和B不认识、认识、熟悉与好友关系.3.对关系图的分析在获得邻接矩阵之后，首先要做的就是对ID进行分类，分类根据三个标准（认识、熟悉、好友）分别进行。以认识为例，只要某个id与某类A中的任一个id之间在某一方向上的权值不小于认识级别的阈值，则把此id归到类A中，即分类时可把关系图看成无向图。如果把图中权值小于阈值的边去掉，则问题转化为求图中的连通分支的问题。具体计算过程采取不严格的广度优先搜索的算法，其中“不严格”指的是层数小的节点不一定在层数大的节点之前遍历。在内存中建立2个map结果存储id和它们的分类结果。其中map2包括所有已分好类的id，map1则只包括已分好类且以它为根节点的树尚未遍历的id。 每次新确定一个id属于当前类后，先检查它是否已经在map2中，如果是，说明已经分好类，如果不是，则插入map1中，等待遍历。数据库表中检查过的记录用weight_other值置1表示，以后不再查找。当某个类不能找出其它新的id时，则开始找下一个类。最后，所有与其它id存在关系的id和它们所在类的信息都保存在map2中。由于此分类过程需要时间很长，故把结果都输入到class数据库表中，其它功能要调用分类信息时只需从数据库中读取，只有在更新关系矩阵后才重新分类，修改数据库表。Top10包括认识别人最多的Top10和被别人认识最多的Top10两种情况，其中认识程度又有3种，所以总共计算出6组Top10。由于此处只涉及直接认识或直接被认识，所以具体算法很简单，只需对每个id查询数据库表，计算与它之间的权值不小于相应阈值的id个数，选出排在前10位的id。用一个长度为10的CString数组和一个相同长度的int数组存储当前前10位的id（排好序的）以及它们认识或被认识id的个数。每得到一个新id的信息后都从该数组的开始进行检查，找到插入点或不能插入。求两个id之间的最短路径采取严格的广度优先搜索算法。先判断两个id是不是属于同一个类，如果是，则从源id开始一层一层扩散，直到找到目的节点。如果数据库表查找完毕，但仍未找到目的节点，则不存在路径。需要用两个CString数组存储上一层的id和当前层的id，以及一个map结构用于记录已经扩散到的所有id和它的前驱id，也可避免重复查找。求某id的间接认识（或间接被认识）的所有id与求两id之间的最短路径的算法类似，只是少了找到目的id就退出的终止条件。第四部分拓展与展望我们的系统只是一个初步的尝试，主要目的在于建立一个代表ID之间关系的有向无环图。在这个图的基础上，我们实现了一些分析功能。这些功能同时也证明了关系图的正确性及其应用价值。在下一步的工作中，我们还要在以下方面继续努力：1．权值的定义。本系统对权值的定义比较简单，考虑还不够全面，权值计算中的一些参数的设定也有待我们在测试中完善。如发文的次数与增加的权值之间的关系需要考虑，完全的正比关系固然简单，但并不准确。如果A在同一天就同一个问题发了多篇文章，是否应看成是一篇呢？还是取一个折中值？这些都是定义计算公式时要研究的问题。另一种情况，如果idA回复了idB的某篇文章，说明两人有可能认识，可以对相应的权值增加一个较小的数。考虑得再复杂一点，是否可以通过分析回复内容，估算两人认识的概率，从而得到一个相对准确的权值增加值？以上是两个体现id之间认识程度的最典型的例子，是否还有别的途径？2．分析算法的改进。本系统采取的都是比较简单的算法，数据量很大时运行起来会比较慢。下一步可以设计一些有针对性的比较快的算法，以满足大数据量的要求。3．对图中隐藏信息的挖掘。本系统实现的功能只是对id之间的关系进行简单的分析，关系图中是否包含一些其它隐藏的信息呢？尽管bbs上某些信息并不完全可信，但通过分析关系图还是应该可以获得一些有用的信息的。这也是今后改进系统需要思考的主要问题。4．版面分析的功能尚未完成。由于此系统只是测试阶段，某些结果并不很准确，我们打算先把id之间的关系做好，再分析版面的性质，而这也是下一步工作中的一个重要的内容。 5．扩展系统是适用范围。目前此系统只适用于分析北京大学的未名bbs(bdwm)，在从网页中获取信息时也是按照未名bbs的固定结构抓取的，并不适用于其它的bbs。今后可扩展到其它一些校园bbs，比如两全其美(lqqm)，水木清华(smth)等，寻找它们网页之间的共同结果，让用户选择分析哪个bbs或把几个关系紧密的bbs放在一起分析。当然，这样分析的难度会更大，得到的结果也会更不准确，这就需要进一步的测试。在做好各校园bbs的分析有了一定的经验之后，还可以考虑扩展到其它一些面向整个网络的论坛中，可那些论坛中干扰信息会比较多，分析结果的准确性和实用性也值得商榷，但也是将来工作的一个方向。'