图是表示一些事物或者状态关系的表达方法。由于许多问题都可以归并为图的问题,因此出现了很多与图相关的算法。图论算法为很多问题都提供了有效,简单,且系统的建模方式。图论模型可以利用矩阵描述并通过线性代数及矩阵理论知识来分析和求解,其表达形式简洁但富有概括力,同时便于进行深入理论分析。很多问题都可以转化为图论问题,然后用图论的基本算法加以解决。其在机器学习的无监督聚类及有监督的类分布学习等方面中得到了广泛应用。本文的具体工作内容如下:基于图松弛优化为非近似迭代方法提供了有效的分析解决方案,且实现简单。然而,由于矩阵的逆在计算时需要多项式时间,则在运行速度方面不是很理想,当面对较大规模数据时此方法将变得不可行。在本文中,我们提出了对基于图松弛优化聚类进行快速近似提升的两种方法:一个基于k均值聚类,另一个是基于随机投影树。广泛实验表明,这些算法在运算速度方面表现较优,且聚类精度变化非常小。具体来讲,我们的算法在运算大规模数据时精度优于k均值算法,并且在保证精度的情况下运行速度远快于基于图松弛优化聚类算法。值得注意的是,文中的算法可以使得单个机器在数分钟内对具有数百万样本量的数据集进行聚类。现有的大多数面部表情识别方法都是假定样本中每个人脸表情对应单一的情绪,而后作为分类问题进行解决。但是在实际情况中,一个人脸表情往往是多种不同基础情绪的混合体。因此,具有相似表情的样本在基础情绪层面存在一定的相关性,这种相关性也通常会导致样本的表情标签呈现多样性。也就是说,每个表情样本的表情状况与潜在的情绪标签分布相关联。为此,我们提出了一种通过数据进行自适应学习潜在标签分布的方法,不需要任何预先假设的标签分布形式,便可得到每个表情与其相应的多个情绪的关联情况。此方法可得到每个表情所包含情绪的特定描述度以及表情图像到情绪分布的映射。实验结果表明,文章算法在表情识别上具有较高准确率,并且能够有效地分析出人脸表情中所包含的基础情绪的强度。