在线社交网络用户的分类及采样研究

摘要

近年来，随着越来越多的网络在线服务的出现，大量以网络形式相互关联的数据在互联网中涌现。这些数据包括：在线社交网络的用户交互信息、论文检索库中的引用信息、电子商务网站上的消费评论信息等。此外，还存在一些非互联网络中产生的，但是同样具有相互关联特性的数据，比如：生物医学界中的蛋白质和基因组合数据、电信行业的用户通信数据等等。所有这些网络数据都具有如下显著特征：数据样本间不独立；数据样本的属性之间存在概率相关性；数据量十分巨大。
　　针对网络数据的上述特性，以网络数据的分类问题为核心，对网络数据的在线采集、模型建立、特征提取和分类应用等方面展开了一系列研究。主要研究内容和创新点如下：
　　1.研究如何对网络数据建立普适的模型，并基于该模型总结了一套通用的网络数据分类策略框架。该框架由本地分类器（Local Classifier）、关系分类器（Relational Classifier）和联合推理（Collective Inference）三部分组成。详细对比了各部分对应的算法，以及各种算法组合后的分类性能。
　　针对网络数据中小占比类别样本的数据缺失问题，提出了在样本权重中引入误分代价的方式，对网络数据的初始化操作进行了优化，使得小占比样本的数据缺失在本地分类（Local Classifier）阶段得以补足，为后续的关系分类和联合推理提供了更多分类依据。
　　2.针对在线社交网络用户分类问题中训练集和测试集的类别占比不一致的问题，以Na?ve Bayes算法为例，运用迁移学习的方法，将测试集中的信息迁移到训练集中，获得了更好的预测效果。
　　3.讨论了影响关系分类器（Relational Classifier）的预测精度的主要因素。大多数关系分类器都基于网络数据的一个普遍特征：同质性（Homophily）对数据进行分类。大多数同质性指标都仅仅对整个网络数据集进行同质性度量。然而，就分类问题而言，需要对数据集中的各个类别分别进行同质性度量。
　　因此，尝试性地定义了多个同质性指标（Edge-centered indexes和Node-centered indexes以及E-Index）专门对网络数据集中的任一给定类别的同质性进行量化。实验表明，E-Index指标的度量效果最好。研究同时发现，对关系数据分类问题而言，给定类别的分类预测精度仅和该类别自身的同质性有关，和其余类别的同质性无关。
　　4.以推特（Twitter）在线社交网络为研究实例，设计了一个基于用户交互行为的分级采样爬虫系统，详细介绍了该系统的模块架构和资源优化策略。
　　为实时锁定当前最有影响力的用户，重点优化了系统的用户采样模块：在用户分级算法—TunkRank算法中，引入了基于用户交互信息的，可调制的转发率因子p。使得系统能够实时的基于用户当前的信息交互状态对用户进行分级。实验表明，引入转发率因子p的TunkRank算法相较于传统的分级算法：PageRank算法和HITS算法，在采样时，更有助于对重要用户的信息更新进行实时跟进。
　　5.基于上述研究结果，对比了推特(Twitter)在线社交网络中的两个重要用户关系：关注（Follow）关系和转发（Retweet）关系，并分析了两者在传播用户影响力和提升用户分类精度这两个方面的作用。
　　定义了两个变量Vf和Vr，分别度量关注关系和转发关系对传播用户影响力的作用。实验对比发现：转发关系在传播用户影响力方面所起的作用更大。
　　分别依据关注关系和转发关系对Twitter用户进行分类后发现：基于关注关系的分类效果更好，但是转发关系也有助于理解用户的信息交互行为；此外，隶属于不同类别的用户，其信息交互行为习惯间存在着差异。

目录

封面

声明

中文摘要

英文摘要

目录

主要符号表

第一章 绪 论

1.1 相关背景和研究动态

1.2 课题来源及主要研究内容

1.3 论文章节安排

第二章 关系数据分类框架及算法

2.1 关系数据简介

2.2 关系数据分类框架

2.3 各种关系分类算法和联合推理算法的组合及对比

2.4 本章小结

第三章 对Local Classifier 模块进行算法改进

3.1 对Local Classifier模块进行误分代价敏感化处理

3.2 将迁移学习引入Local Classifier模块

3.3 本章小结

第四章 网络数据的同质性度量

4.1 相关工作、背景和研究意义

4.2 问题描述和建模

4.3 两组类别同质性指标的定义和对比

4.4 E-Index的定义

4.5 实验对比

4.6 本章小结

第五章 基于分级采样的Twitter爬虫系统

5.1 相关工作

5.2 Twitter建模及特征分析

5.3 Twitter用户的信息交互行为分析

5.4 爬虫的系统架构

5.5 用户采样及更新

5.6 实验对比及分析

5.7 本章小结

第六章 Twitter的Follow关系和Retweet关系对比

6.1 相关工作

6.2 Follow和Retweet在传播用户影响力上的差异

6.3 基于Follow 和Retweet的Twitter用户分类

6.4 实验与结果分析

6.5 本章小结

第七章 全文总结与展望

7.1 全文工作总结

7.2 未来工作展望

致谢

参考文献

攻博期间取得的研究成果