双分图模型、相互强化分析与遗传算法在聚类层次结构中的应用

### 双分图模型、相互强化分析与遗传算法在聚类层次结构中的应用 在数据处理与分析领域，检测异常评论者、总结评论以及进行聚类层次结构的发现是重要的研究方向。本文将介绍一种用于评论分析的双分图模型和相互强化分析方法，以及一种基于遗传算法的聚类层次结构发现算法。 #### 双分图模型与相互强化分析在评论分析中的应用 ##### 方法概述 当目标对象的评论较少时，该方法可以结合目标对象和其他对象的评论来检测异常评论者。通过对三种形式的评论以及部分对象评论者较少的情况进行验证，该方法能够检测出异常评论者，并生成比评论平均值更可信的总结。 ##### 相关工作 - **异常检测**：该方法属于异常检测的范畴，利用上下文异常来检测异常评论者。与一些现有研究不同，现有研究在图建模目标数据上进行上下文异常检测时，多使用节点相似度，而本方法使用与边相关的量化评估。 - **垃圾评论检测**：部分现有研究定义并检测垃圾评论或垃圾评论者，而本方法检测的异常评论者不仅包括垃圾评论者，还包括与普通人评价不同的评论者，如被评价对象的专家。 ##### 提出的方法 - **双分图模型**：评论分析的图模型有两种实例：主体和对象。主体是进行评价的实例组，如评论者；对象是被评价的实例组，如产品和服务。评论数据可以建模为双分图 $G(V_S, V_O, E)$，其中： - $V_S = \{p\}$：表示主体的节点集合。 - $V_O = \{q\}$：表示对象的节点集合。 - $E = \{(p, q)\}$：表示评价的边集合。 - 若 $p$ 评价 $q$，则生成 $(p, q)$ 并关联量化评估 $D_{pq}$，$D_{pq}$ 可以是实数、向量或分布等形式。 - **相互强化分析**：在双分图模型上，统一总结评价并检测异常主体。基于主体和对象之间的相互强化关系，为主体 $p$ 赋予表示异常程度的实数特征量 $x_p$，为对象 $q$ 赋予与量化评估 $D_{pq}$ 形式相同的表示评价总结的特征量 $Y_q$。 - $x_p$ 的定义： \[x_p = \frac{\sum_{q:(p,q)\in E} x_{pq}}{N_p}, x_{pq} = distance(D_{pq}, Y_q)\] 其中，$N_p$ 是与 $p$ 相邻的节点数，$x_{pq}$ 是 $D_{pq}$ 和 $Y_q$ 的差异度。 - $Y_q$ 的定义： \[Y_q = \sum_{p:(p,q)\in E} w_{pq}D_{pq}, w_{pq} = \frac{\frac{1}{x_p}}{\sum_{p:(p,q)\in E} \frac{1}{x_p}}\] 其中，$w_{pq}$ 用于 $q$ 的评价加权平均。 - **特征量计算**：使用迭代算法计算特征量 $x_p$ 和 $Y_q$。首先初始化所有 $x_p$ 为相同值，然后迭代更新特征量，直到 $x_p$ 的差异足够小。 ##### 实验 - **数据集**：使用雅虎电影网站的用户评论，创建了包含 17 个原始评论者和 3 个异常评论者的数据集。使用三种形式的量化评估： - **评价分数（E）**：用户评论中的评分，取值为 1 - 5 的实数。 - **基于特征的评价向量（FE）**：使用用户评论中的其他评分创建五维向量，每个元素取值为 1 - 5 的实数。 - **基于情感模型的评价向量（S）**：使用情感词典从用户评论的文本中提取并量化情感，创建八维向量。 - **结果**： - **异常主体检测**：实验结果表明，该方法能够使用任