分类是机器学习中一个重要的研究领域,在各领域有广泛的应用,例如,垃圾邮件检测,银行贷款信用评估,新闻文本自动分类,蛋白质功能预测,图像或视频标签预测,社交网络用户分组,电商网站物品分类等。因此,一直以来研究学者和行业从业者一直以来对数据分类都有关注。随着互联网技术的快速发展,各领域产生了大量多义异构的数据,数据的组织形式多样化,数据的分类也面临着新的挑战。例如,传统的分类任务中假设样本是单示例的,随着数据的复杂化,组织形式的多结构化,这样的假设不再适用于所有的分类问题。在大多数分类问题中,假设样本彼此之间是相互独立的,但在很多实际场景中,数据之间存在复杂的关联关系。在很多实际应用中,一个样本通常关联多个语义信息,传统的单标签学习方法不再适用。本文针对上述这些问题,以马尔可夫链和随机森林为基础,提出了多个分类算法,分别是:基于Hausdorff距离的多示例分类算法,基于马尔可夫链的异构信息网络分类算法,以及基于层次聚类树的多标签分类算法。本文的主要研究内容如下:(1)针对多示例数据分类问题,本文提出一种基于Hausdorff距离的多示例分类算法,H-Mark算法。该算法基于标签传播的思想,根据样本的特征信息,使用Hausdorff距离度量样本与样本之间的关联关系,构建样本之间的相似度矩阵。以马尔可夫链模型为基础,根据样本之间的相似度,构建样本之间的转移概率矩阵,得到样本的稳态概率分布。由于相似度矩阵的非0属性,本文使用一个近邻参数控制样本近邻个数,使用相似度矩阵计算一个稀疏的转移概率矩阵,用于标签传播。通过H-Mark算法得到样本稳态概率分布,设置合理的阈值,预测样本的标签。在生物分子功能注释问题中,由于每个蛋白质是由多个域构成的,每个蛋白质又被标注有多个功能,因此,使用多示例分类模型解决多域蛋白质的功能预测问题。本文在7个实际的蛋白质数据集上表明H-Mark算法的性能优于对比的多示例分类算法。(2)针对异构信息网络数据分类问题,本文提出一种基于马尔可夫链的异构信息网络分类算法,HIN-Mark算法。首先,将异构信息网络转化为多关系网络,只保留作为分类对象的网络实体,并将异构信息网络中各类型实体之间的关联关系转化为分类对象实体之间的关联关系。然后,使用张量表示多关系网络,并提出了基于特征的转移概率矩阵和基于网络关联关系的转移概率张量的异构信息网络分类模型。最后,提出HIN-Mark算法,使用迭代算法求解提出的基于马尔可夫链的异构信息网络分类模型。HIN-Mark算法能够同时计算出实体的概率分布和关系的概率分布。根据这两个概率分布,预测分类对象实体的标签,以及各关联关系与标签的相关性。本文对HIN-Mark算法进行了理论分析,证明了实体概率分布ˉx和关系概率分ˉz的存在性和唯一性,以及HIN-Mark算法的收敛性。本文在多个数据集上的使用结果,说明了网络关系与标签的相关性对实体分类的重要作用,以及HIN-Mark算法优于其它对比算法的分类性能。(3)针对多标签数据分类问题,本文提出一种基于层次聚类树多标签分类算法,ERF-H算法。该算法计算标签之间的相似性,构建一棵层次聚类树,该树的构建过程是,首先将数据集中的标签进行分层聚类,并以此构建层次化的树模型;然后将原数据根据建好的聚类树分层划分,并为聚类树中的每一个节点构建一个分类器。基于层次聚类树的分类模型中树节点是根据标签的聚类结果分裂的,当节点中只包含一个标签或一个数据时,节点停止分裂。使用组合分类器的方法,随机森林模型,构建多棵层次聚类树,提高数据的分类准确率。构建随机森林时,随机抽样每棵聚类树的训练数据和每棵聚类树节点的子节点的个数。预测未标记数据的节点时,每个节点的标签概率分布结果要继承父节点的概率分布结果,以此类推,根据随机森林中每棵聚类树中叶节点的标签概率分布预测标签。在多个公开、标准的多标签数据集上测试算法的性能,实验结果上说明了ERF-H算法优于其它算法。