数据挖掘基础及其应用 课件 第11、12章 社交网络图聚类、 生物网络挖掘.pptxVIP

第11章社交网络图聚类;第11章社交网络图聚类;第11章社交网络图聚类 尽管复杂网络备受关注,但对复杂网络尚无严格的定义。钱学森院士认为具有自组织、自相似、吸引子、小世界、无标度中部分或全部性质的网络可称为复杂网络,主要表现在 以下方面: 结构复杂性:网络规模巨大,同时网络连接结构随时间而改变。 元素复杂性:网络节点可能具有混沌等非线性行为。 (3)相互作用复杂性:多重因素相互影响引发非线性集体 行为并导致了网络的复杂性。;第11章社交网络图聚类 11.2 社团结构 从图的观点看来,社团是网络的子图,其内部节点之间的连接相对紧密,但与社团外节点的连接相对稀疏。图11-1包含三个社团,分别对应图中三个大圈内的部分。这些社团内的 连接相对紧密,而社团间的连接相对稀疏得多。;第11章社交网络图聚类;第11章社交网络图聚类;第11章社交网络图聚类;第11章社交网络图聚类;第11章社交网络图聚类 11.2.2 社团检测算法 该算法的关键步骤是定义节点间的相似性,然后利用已有算法进行社团提取。其基本框架可定义为算法11.1。;第11章社交网络图聚类;第11章社交网络图聚类;第11章社交网络图聚类;第11章社交网络图聚类;第11章社交网络图聚类;第11章社交网络图聚类 11.3 半监督学习 半监督聚类方法可分为以下几种: 基于模型的方法:假定每个类都隐含一个模型,根据模型发现相应的数据对象。其优点是可通过构建数据点空间分布的密度函数来确定分类,同时可利用标准统计工具来处理 噪声与异常数据,自动确定聚类数。 基于约束的方法:结合了用户指定或面向应用的约束进行聚类。;第11章社交网络图聚类 (3)基于数据集空间结构的方法:与核优化算法有一个共同点,即借助于辅助空间,但不同的是,该方法并不抛弃原空间信息,而是通过投影技术将主空间信息映射到辅助空间,在新空间中完成迭代过程。;第11章社交网络图聚类;第11章社交网络图聚类;第11章社交网络图聚类;第11章社交网络图聚类 在通非负矩阵分解的基础上,基于公式(11-1)的非负矩阵分解算法被称为SS-NMF,与社团结构之间的关系为: 定理11-1 半监督非负矩阵分解算法与模块密度是等价的。;第11章社交网络图聚类;第11???社交网络图聚类 11.4.2 参数优化 本小节主要解决社团分类数的确定与半监督矩阵构建。确定数据集的聚类数问题目前仍是聚类分析研究中的基础性难题之一。目前有两种确定聚类数的方法:枚举法与拓扑结构性质方法。 枚举法的原理是通过使用不同的输入参数(如聚类数m)运行特定的聚类算法,对数据集进行不同的划分,并计算每种划分的聚类有效性指标,最后比较各个指标值的大小或变化情况,符合预定条件的指标值所对应的算法参数m 被认为是最佳的聚类数。该策略的最大优势在于其将一个参数估计问题成功转化为了一个无参数优化问题。;第11章社交网络图聚类;第11章社交网络图聚类;第11章社交网络图聚类;第11章社交网络图聚类;第11章社交网络图聚类 GN 网络的高度对称性不能全面衡量算法的性能,因此对 GN 测试网络进行相应的扰动:对称地合并社团,即将原来4个社团合并成2个等同规模的社团;非对称地合并社团,即合并3个社团为一个大社团。为了进一步检验SS-NMF算法的性能,将该算法应用于改进的GN 网络。表11-1包含了SS-NMF算 法、压缩算法、Q-优化算法、D-优化算法在非对称GN 网 络中的性能对照结果。从表中可以看出,D-优化算法的性能最好,Q-优化算法的效果最差,SS-NMF算法拥有与D-优化算法相近的性能。;第11章社交网络图聚类;第11章社交网络图聚类 2.跆拳道俱乐部网络 Zachary俱乐部网络是经典的社会网络,来源于Zachary的分析研究,包含34个成员(节点)和78 对关系(边)。由于管理者和指导教师对费用问题发生了分歧,俱乐部分成分别以管 理者和指导教师为中心的两个子俱乐部,如图11-3(a)所示。;第11章社交网络图聚类;第11章社交网络图聚类 11.5.2 分辨极限容忍性分析 1.LFR标准测试集 由于GN 测试网络的社团规模与节点度保持严格的一致性,无法评价算法对分辨极限的容忍性。为解决这一缺陷, Lancichinetti、Fortunato与Radicchi(LFR)提出新的LFR标准测试集。与GN 网络不同,LFR可构建规模大小可变的社 团结构,社团结构规模与节点的度都服从于某个参数的指数分布。;第11章社交网络图聚类;第11章社交网络图聚类;第11章社交网络图聚类;第11章社交网络图聚类;第11章社交网络图聚类;第11章社交网络图聚类 除了分类的准确性,算法所检测的社团规模分布也是研究分辨极限的重要指标。图11-6是社团规模累计分布率与社团规模之间的关系图,其横坐标表示社团规模