拟阵约束下最大化子模函数的模型及其算法的一种熵聚类方法

摘要

本文提出了一个新的带有信息熵的聚类目标函数,它是由基于图论的随机路径的熵率和平衡项两部分组成。熵率有利于形成紧凑和均匀的聚类,平衡函数鼓励相似度比较高的对象才能聚类,并惩罚那些相似度比较低的对象。首先构造了与数据关联的赋权无向图,并发现这种构造诱导出一个拟阵,它是一个组合在向量空间中推广线性独立概念的结构。接着得到了拟阵约束下最大化子模函数的模型。最后根据目标函数的单调性、递增性和下模性,开发了一个高效的贪婪算法并讨论了它的性能保证。最后根据数值实验,与已有的算法做了比较,说明了该算法的有效性。