彩色关联聚类算法研究

发布时间：2024-10-03 07:10

　　聚类原本是统计学上的概念,随着人工智能的发展,现在属于机器学习中无监督学习的范畴,其被广泛应用在数据挖掘、数据分析等领域。聚类算法通常是按照一定的规则将具有共同特性的对象归为一类,不同特性的对象划分为不同类。关联聚类是聚类问题中最为重要的方法之一,它是图上的一种聚类。在图中,相似的对象之间有一条正边相连,不相似的对象之间则用负边相连。关联聚类就是要根据这种图结构将具有正边的对象尽量放入一个类中而负边的两个对象放入不同的类。然而现实关系纷繁复杂,由此构建的关系网络十分复杂,简单的二元关系往往无法应用于这样的场景。自然而然产生了对彩色关联聚类问题的研究。彩色关联聚类问题是关联聚类问题的一种高度概括,它将关联聚类中的二元关系进行扩展,在图上的边中引入颜色的概念,从而能够应对现实中更多的场景。目前彩色关联聚类有着十分广泛的应用,如社交网络、生物信息学等。但彩色关联聚类问题的研究还很不完善,这些算法的近似比和关联聚类算法相差甚远。目前近似比最好的算法是Pivot算法,但其在聚类过程中忽视了颜色属性。本文基于松弛线性规划解针对彩色关联聚类问题提出了一个确定性的近似算法,从而将该问题的近似比提升到了 ...

【文章页数】：70 页

【学位级别】：硕士

【文章目录】：
摘要
ABSTRACT
第1章 绪论
    1.1 研究背景及意义
        1.1.1 关联聚类
        1.1.2 彩色关联聚类
    1.2 主要研究内容和贡献
        1.2.1 主要研究内容
        1.2.2 本文贡献
    1.3 论文组织结构
第2章 基础知识
    2.1 关联聚类简介
    2.2 标准彩色关联聚类
        2.2.1 定义
        2.2.2 整数线性规划及其松弛形式
        2.2.3 整数界
    2.3 非对称权重的彩色关联聚类问题
        2.3.1 定义
        2.3.2 松弛线性规划形式
        2.3.3 整数界
    2.4 本章小结
第3章 标准彩色关联聚类问题的近似算法设计与分析
    3.1 算法
        3.1.1 算法描述
        3.1.2 背后的思想
        3.1.3 算法性能
    3.2 近似比分析
        3.2.1 证明脉络
        3.2.2 更多细节
    3.3 去随机化
    3.4 本章小结
第4章 标准彩色关联聚类问题的启发式算法设计与评估
    4.1 算法介绍
        4.1.1 算法描述
        4.1.2 背后的思想
        4.1.3 时空复杂度
    4.2 实验评估
        4.2.1 真实数据介绍
        4.2.2 参数实验
        4.2.3 对比实验
    4.3 本章小结
第5章 非对称权重的彩色关联聚类问题的近似算法设计与分析
    5.1 算法
        5.1.1 算法描述
        5.1.2 背后的思想
        5.1.3 算法性能
    5.2 近似比分析
        5.2.1 在θ≤0.169时的近似比分析
0.169时的近似比分析">        5.2.2 在θ>0.169时的近似比分析
    5.3 本章小结
第6章 总结与展望
    6.1 工作总结
    6.2 工作展望
参考文献



本文编号：4006898