1引言
基于信息处理技术的推荐模型目前得到了广泛应用，其应用模型包括：分类决策树模型、支持向量机模型、K最近邻模型等；其处理的对象主要是相对孤立的用户及其相关数据【1】；这些数据通常以用户实体标识作为“主键”，以多个向量来描述用户实体；为保证挖掘工作的开展，这些向量之间被假设为彼此独立。而在实际的社会网络中，用户之间必然存在着种种联系，因此难以形成彼此独立的数据点；忽视了上述联系的算法，往往会阻碍社会网络推荐模型的性能发挥【2-4】。为了解决上述问题，必须将网络中各个用户之间的关系同时引入；因此，社会网络的概念随之诞生【3-4】。针对社会网络的数据挖掘，又被称为社会网络分析，它不但关注实体节点，而且注意对链接信息的挖掘，因此又称为链接挖掘（linkmining）。通过对社会网络的深度挖掘，可以获取更丰富、更准确的信息【4-5】。目前，研究人员已经提出了一批诸如：SocioMetrica、Stocnet、Inflow、MultiNet等社会网络分析模型和应用工具【6-8】。基于上述研究背景和成果，本文提出了基于用户活动事件识别的社会网络推荐模型AER（ActionEventRecommender）。
2问题分析与解决方案
在实际研究和开发中，现有的社会网络应用模型暴露出较多问题；本文基于社会网络推荐模型，给出了相应的分析及解决方案。首先，在大规模社会网络中，进行实体节点之间的链接挖掘（相当于子网划分）需要一个新型的切入点。传统的挖掘，通常从实体节点自身属性入手，根据相似度进行好友推荐，这种方法具有一定的实用性，但随着网络规模的扩大，进行节点的平方级遍历（每个节点均与其他节点进行一次匹配），将会消耗大量的系统资源【8】。其次，从目前社会网络推荐实施的依据来看，主要是对实体节点的属性（性别、年龄、学历等）进行链接挖掘，这种挖掘依据静态的、主观化的、初期的节点数据，难以应对社会网络节点动态的、客观的荐友需求【9】。针对上述问题，AER模型提出了以用户活动为依据，对社会网络进行动态划分，将子网的划分切入点从实体节点转移到用户活动的关键点上来，并将节点匹配的范围缩小至活动所划分的子网内，从而降低节点遍历所需的系统开销，提高链接挖掘的动态性和适应性。
3模型结构与工作流程
3.1模型结构
AER模型的结构与功能模块、处理流程如图1所示。节点（实例）管理模块：该模块负责收集节点的相关属性信息与其相关的用户活动信息。为扩展节点信息的收集范围，本模型采用了微格式信息收集机制；其中，“微格式”是一种对象描述规范，用以表述特定的网络信息类型；以本模型中的节点为例，其微格式包括：姓名、所在地、所属组织、电子邮件地址、操作行为序列等明细属性。活动事件管理模块：该模块负责AER模型中的用户个体或集体活动事件的跟踪、识别、记录等工作，相关信息在采集后，注入活动事件数据库备用，并定时扫描，以进行事件跟踪。本模型中的活动信息采用事件六元组表示法，即：E（Event）=<O,A,T,E,P,L>。其中，O,A,T,E,P,L分别为其构成要素，即：实体节点（O:Object）、动作（A:Action）、时间（T:Time）、环境（E：Environment）、预言（P:Predict）、表现词（L:language即：关键词）。节点和活动（事件）数据库模块：用于存储和管理本模型中的节点属性序列以及事件六元组，并提供事件查询服务，包括：事件与事件、事件与节点等匹配操作。推荐生成模块：由节点管理模块和活动管理模块激发，在事件关键点或事件完成后，根据相关信息生成节点的好友推荐列表，并向社会网络节点实施推荐。
3.2工作流程
由于客户活动总是在不断的变化，为从时间序列角度描述活动，AER模型中定义活动要素变迁描述系统S=(Es,Ts,As)。其中Es为活动（事件）要素集合；Ts为时间段集合；As为动作集合。依据上述模型，在本模型工作流程中，对于活动进行两方面的处理，如图1所示。（1）本模型对节点进行“微格式”跟踪，并以时间为序，构建节点的状态信息序列，从中判断节点与活动的关系；最终注入数据至节点数据库。（2）本模型跟踪系统中活动（事件）的发展过程：本模型将定时对各个事件进行采样（2.1），即对活动中的各个要素进行取值，并保存在数据库中，以从数值上描述活动的发生发展过程。此外，活动管理模块将对活动的要素状态进行监测（2.2），通过阈值判断等方式，进行活动的关键点识别，并保存在活动数据库中，或激活推荐模块。（3）本模型根据活动中实体节点的微格式数据（3.1），采集活动（事件）要素集合中实体节点的详细信息，并定时更新；随着活动（事件）从发生到发展，及至消亡，活动中实体节点的动态离散变化过程均被记录在数据库中；节点管理模块或活动管理模块将在各活动/节点的关键点处激发匹配操作（3.2），由推荐生成模块，生成TopN的相关活动或好友（目前该模型仅用于好友推荐系统）推荐列表。（4）推荐生成列表将相关信息回馈给节点管理模块，或通过社会网络系统中的其他模块提交节点好友推荐列表。
4关键算法
4.1基于子网的匹配推荐算法
由于社会网络中活动涉及的节点（用户）数量较多，如采用传统的节点枚举匹配算法，系统将不堪重负，因此本模型中采用了改进的、基于子网的匹配推荐算法。详细步骤描述如下：（1）将根据用户在历次活动事件中筛选预处理后的活动数据，抽取其中的用户的关系形成关系矩阵X；因为用户的关系数据量较大，本模型中采用了二维表处理稀疏矩阵的方法进行存储；计算中，将矩阵扩展为X=[XA]，其中的A是一个零矩阵，其规模为H×(w-mod(W,w))，其中H和W为关系数据规模的纵向高度和横宽，而w为设定的矩阵宽度；经过该步骤，可以将关系矩阵X均分为宽度为w的多个关系子矩阵（社会网络中的节点/关系子网）。（2）将分解开的二维窗口中的极值计算进行水平和垂直分解，进行两次一维窗口的极值运算，具体算法为：此时，需要对序列进行2(w-1)次数据对比，计算量较大。
4.2推荐列表过滤算法
通过上述算法得到的推荐好友列表往往较长，因此需要进行过滤，以提高推荐精度。本算法以负熵最大作为最终好友列表的搜寻方向；本算法首先需要建立负熵的判决准则。由概率统计学的基础理论可知：在目前已知的所有等方差的随机性变量中，高斯变量的熵是大的；因此，本算法利用熵来度量非高斯性的常用熵的修正状态，即负熵。以中心极限理论为基础，如果一随机变量X（用户的好友需求）由若干彼此独立的随机变量Si(i=1,2,3……N)组成，只要Si均值和方差都有限，则不论它呈现哪种分布，随机变量X都将比Si更类似于高斯分布。据此现象，在推荐列表过滤过程中，可通过过滤结果的非高斯性的度量来描述过滤结果之间的彼此独立性，当它们的非高斯性的度量达到最大值时，则表明已完成了过滤。据此，负熵可定义为：实际运算中，该算法中用的期望必须用它们的估计值代替；而最好的估计是对应的样本平均。但引入所有的有效数据参与计算，将会消耗过多的系统资源。因此本算法采用了随机抽样求平均的方法进行估值。因为，样本数目对最终的估值精度影响较大。因此，如果假如收敛不理想的话（最终好友数量太少），将调节样本的数量。
5性能仿真与分析
本模型的测试采用了VLSNS(VirtualLocalSNS：开源的虚拟社会网络数据库，具有兆级的关系数据，适用于海量关系模拟与仿真)测试数据集进行性能测试，并与基于用户属性与话题的社会网络推荐模型SRR(SmartRelationRecommender：该模型主要采用静态用户属性与动态话题跟踪的方法进行推荐)进行了仿真结果对比。其中VLSNS数据库中，选用了275名用户（节点）作为测试基本数据，其相关活动条目共计21935条（含好友列表操作活动），用户实际存在好友关系共2381对（双向关系记为一对）。仿真性能测试分别对两种模型的好友覆盖度、推荐精确度和召回率进行了验证。其中，普通的好友覆盖度定义为：推荐模型向用户推荐的好友集对用户最终好友集合的覆盖程度；实际的应用中，好友关系是流动性关系，存在数量上的增减（例如：用户和好友的添加、删除、关系变更等）和时序上的变化，为更精确的测试模型性能，本次测试对运行中两种模型中的好友覆盖率进行了活动顺序的跟踪，其定义修正为：Coverage(t)=∑(RS(t)∩RR(t))/RS(t)t≥0；其中，RS(t)为用户在时刻t的实际好友数量，RR(t)为用户在时刻t获得的推荐好友数量。如图2可知，本模型能在较短的时间内，实现较高的好友覆盖率，具有较好的推荐性能。
6结语
AER模型能够较好的避免传统社会网络推荐模型中高系统负载和低精度的缺陷，仿真实验也证明了其优良性能，因此具有一定的应用推广价值。未来的研究方向包括：扩展事件识别方法、研发用户活动事件与节点匹配方法等。
作者：谭龙江 单位：华侨大学 西南财经大学
相关专题：医学论文 中国如何应对金融危机
