主题相似度与链接权重相结合的垃圾网页排序检测

针对因Web中存在由正常网页指向垃圾网页的链接,导致排序算法(Anti-TrustRank等)检测性能降低的问题,提出了一种主题相似度和链接权重相结合,共同调节网页非信任值传播的排序算法,即主题链接非信任排序(TLDR)。首先,运用隐含狄利克雷分配(LDA)模型得到所有网页的主题分布,并计算相互链接网页间的主题相似度;其次,根据Web图计算链接权重,并与主题相似度结合,得到主题链接权重矩阵;然后,利用主题链接权重调节非信任值传播,改进Anti-TrustRank和加权非信任值排序(WATR)算法,使网页得到更合理的非信任值;最后,将所有网页的非信任值进行排序,通过划分阈值检测出垃圾网页。在数据集WEBSPAM-UK2007上进行的实验结果表明,与Anti-TrustRank和WATR相比,TLDR的SpamFactor分别提高了45%和23.7%,F1-measure(阈值取600)分别提高了3.4个百分点和0.5个百分点, spam比例(前三个桶)分别提高了15个百分点和10个百分点。因此,主题与链接权重相结合的TLDR算法能有效提高垃圾网页检测性能。     

基于相似度传播的二分网络链接预测

链接预测是复杂网络分析中的重要研究问题。提出了一个基于链接相似度传播的二部图链路预测算法。该算法将链接相似度得分通过随机游走在网络中进行传播和更新。在该算法中,网络里的每一条边都被分配一个基于相似度的传播概率。不同部分的节点之间的链接相似性得分根据它们的边的传播概率来传播。在不同大小的真实社交网络上的实验结果证明,该算法可以取得比其他算法更精确的预测结果。     

基于PageRank的页面排序算法研究

提出一种基于PageRank的页面排序算法.采用网页类别相关度计算,对来自不同类别网页所传递的权威值赋予相应的权重;根据链接所属信息块重要性的不同,赋予相应权值.实验表明,该算法对提高页面排序质量是有效的.     

一种新的属性图重叠聚类挖掘算法

属性图各节点附有的节点属性标签,为节点提供了更加丰富的信息,在数据挖掘应用,特别是数据聚类问题中如何有效利用这些丰富的信息,已经成为开展此类研究的研究目的.不同于传统图聚类,属性图上的聚类要同时考虑图的结构信息和节点的属性信息,因此如何平衡两者之间的关系,这是属性图聚类主要关注所在.目前已提出的属性图聚类算法,部分算法的效率很高,然而聚类质量较差,同时一些算法可以得到较好的聚类结构,然而算法消耗大量的系统资源,效率也较低.这些算法均没有考虑簇之间存在重叠的情况,这导致无法得到更高精度的聚类结构.因而提出一种属性图上的重叠聚类挖掘算法,实验表明,提出的算法可以得到更高的聚类精度,特别是可以提升聚类内部节点的属性相似度.     

基于K-means聚类算法和信息熵的页面排序算法研究

针对经典的PageRank算法存在的偏重历史网页、主题漂移、平分网页链接权重等缺陷,引入了向量空间模型和信息论中的信息熵,提出一种改进的PRKE算法.该算法用表征网页特征的关键词构成的向量来表示网页,用关键词在网页中所占的权重作为向量中各个分量的权值;对已存在的网页采用K-means聚类算法进行聚类,以信息熵的形式表征各个簇的权值,完成对网页的宏观排序;融入了时间因子和主题相关度等参数,完成对网页的微观排序.实验结果表明,改进的PRKE算法相对于经典的PageRank算法在首页命中率、检索准确性等方面获得了较大的提高.     

基于高效置信传播的改进马尔可夫随机场高光谱数据分类算法

针对马尔可夫随机场分类算法中类条件概率估计不准及全局能量最小化计算负担重的问题,提出一种基于高效置信传播的改进马尔可夫随机场高光谱数据分类算法.采用基于光谱信息的统计支持向量机方法提高类条件概率估计精度;通过马尔可夫随机场分类算法引入空间相关信息,实现光谱与空间信息的有效结合;设计一种高效置信传播优化算法,降低计算负担、提高算法精度.实验结果表明该算法平均分类精度达到95.78%,Kappa系数为93.34%,且计算时间约为标准置信传播算法的25%,因此是一种计算负担小、分类精度高且具有实用价值的高光谱数据地物分类方法.     

时序图节点嵌入策略的研究

相较于传统的图数据分析方法,图嵌入算法是一种面向图节点的新型图数据分析策略.其旨在通过将图节点向量化表达,进而在节点向量基础上利用神经网络相关技术更有效的进行图数据分析或挖掘工作,如在节点分类、链接预测及交通流预测等经典问题上取得效果显著.虽然研究者们在图嵌入方面已取得了诸多成果,但是面向时序图的节点嵌入问题却未被充分重视,本文便是在先前研究工作的基础上,结合信息在时序图中的传播特性,提出了一种对时序图节点进行自适应嵌入表达的方法ATGEB （Adaptive Temporal Graph Embedding）.首先,为了解决不同类型时序图节点活跃程度不同的问题,通过设计一种自适应方式对其活跃时刻进行聚类.而后,在此基础上设计一种游走模型用以保存节点对之间的时间关系,并将节点游走序列保存在一种双向多叉树上进而可以更快速的得到节点时间相关的游走序列.最后,在基于节点游走特性和图拓扑结构的基础上,对节点向量进行重要节点采样,以便在尽可能短的时间内训练出满足需求的网络模型.通过充分的实验证明,本文面向时序图的嵌入策略相较于现流行的嵌入方法,在时序图时序中节点间时序可达性检测以及节点分类等问题上得出了更好的实验效果.     

一种基于结构分析的网页主题区域发现方法

随着互联网的发展,We b数据挖掘在帮助人们获取主题信息方面越来越具有重要意义。本研究基于树结构,将We b网页解析为标签树;在树匹配算法的基础上,提出了数据区域挖掘和语义链接块识别算法,实现了去链接的预处理;提出了文本结构权重的概念,并采用文本结构权重的计算结果发现主题区域,去噪后获得主题信息。实验表明该研究结果对新闻、博客类网页具有很好的识别效果。     

基于局部图结构的链接预测模型

链接预测是基于已知的部分图数据来预测节点之间未被观测到的边或者未来可能产生的边的任务。链接预测领域目前最表现最佳的方法是,对所有目标节点对提取周围的低阶邻居小图,使用小图做图分类预测链接的方法。然而,这种方法的稳定性和性能受限于图的局部结构特异性。提出的方法在上述算法的基础上进行了改进。该算法根据目标节点周围节点的结构特征计算周围节点优先值,根据优先值筛选出高优先值的节点集合,并同时选出一定数量的随机节点,共同组成封闭子图,提取子图特征进行链接预测。实验表明,该算法有效提高了在不同结构的图数据上选出的小图的精准性和稳定性,显著提升了链接预测的效果。     

融合结构与属性相似性的加权图聚集算法

图聚集技术是将一个大规模图用简洁的小规模图来表示,同时保留原始图的结构和属性信息的技术。现有算法未同时考虑节点的属性信息与边的权重信息,导致图聚集后与原始图存在较大差异。因此,提出一种同时考虑节点属性信息与边权重信息的图聚集算法,使得聚集图既保留了节点属性相似度又保留了边权重信息。该算法首先定义了闭邻域结构相似度,通过一种剪枝策略来计算节点之间的结构相似度;其次使用最小哈希(MinHash)技术计算节点之间的属性相似度,并调节结构相似与属性相似所占的比例;最后,根据2方面相似度的大小对加权图进行聚集。实验表明了该算法可行且有效。     

结合ECOC与DS证据理论的多目标识别研究

情感分类任务旨在自动识别文本所表达的情感色彩信息(例如,褒或者贬、支持或者反对)。提出一种基于情 绪词与情感词协作学习的情感分类方法:在基于传统情感词资源的基础上,引入少量情绪词辅助学习,只利用大规模 未标注数据实现情感分类。具体来讲,基于文档一单词二部图的标签传播算法框架,利用情绪词与情感词构建两个视 图,通过协作学习的方法从大规模未标注语料中抽取高正确率的自动标注样本作为训练数据,然后训练分类器进行情 感分类。实验表明,该方法在多个领域的情感分类任务中都取得了较好的分类效果。     

Weighted samples based semi-supervised classification

Graph-based semi-supervised classification (GSSC) takes labeled and unlabeled samples as vertices in a graph, and edge weights as the similarity between samples. Most GSSC methods handle each labeled sample as equally important in the graph, and they mainly focus on optimizing the graph to improve the performance. In fact, samples are not always evenly distributed. Labeled samples close to the decision boundary of different classes are generally more important than labeled samples far away from the boundary. To account for the different importances, we propose an approach called Weighted Samples based Semi-Supervised Classification (WS3C for short). WS3C firstly executes multiple clusterings on the dataset to explore the structure of samples and summarizes these clustering results. Second, it quantifies the hard-to-cluster index of each labeled sample with respect to other samples based on the summarized results and employs the index to weight that sample. Next, it constructs a graph whose edge weights are equal to the frequency of two samples grouped into the same clusters in multiple clusterings. After that, it performs semi-supervised classification based on the constructed graph and weighted samples. Empirical study on synthesized and real datasets demonstrates that assigning labeled samples with different weights significantly improves the accuracy than equally treating labeled samples. WS3C not only has better performance than other related comparing methods, but also is robust to the input parameters.     

基于图的半监督关系抽取

提出利用基于图的半监督学习算法,即标注传递算法,指导计算机从非结构化的文本中自动识别出实体之间的关系.该方法首先利用图策略来建立关系抽取的模型.在这个图模型中,各个有标签和未标签的样本被表示成图上的各个节点,而样本间的距离则作为图上各边的权重.然后,关系抽取的任务就转化成在这个图上估计出一个满足全局一致性假设的标注函数通过对ACE(automatic content extraction)语料库的评测,结果显示,当只有少量的标签样本时,采用该标注传递的方法可以获得比基于SVM(support vector machine)的有监督关系抽取更好的性能,同时也明显优于基于Bootstrapping的半监督关系抽取的方法.     

结合半监督与主动学习的时间序列PU问题分类

目前基于PU问题的时间序列分类常采用半监督学习对未标注数据集[U]中数据进行自动标注并构建分类器,但在这种方法中,边界数据样本类别的自动标注难以保证正确性,从而导致构建分类器的效果不佳。针对以上问题,提出一种采用主动学习对未标注数据集[U]中数据进行人工标注从而构建分类器的方法OAL（Only Active Learning）,基于投票委员会（QBC）对标注数据集构建多个分类器进行投票,以计算未标注数据样本的类别不一致性,并综合考虑数据样本的分布密度,计算数据样本的信息量,作为主动学习的数据选择策略。鉴于人工标注数据量有限,在上述OAL方法的基础上,将主动学习与半监督学习相结合,即在主动学习迭代过程中,将类别一致性高的部分数据样本自动标注,以增加训练数据中标注数据量,保证构建分类器的训练数据量。实验表明了该方法通过部分人工标注,相比半监督学习,能够为PU数据集构建更高准确率的分类器。     

Semi-supervised learning based on nearest neighbor rule and cut edges

In this paper, we propose a novel semi-supervised learning approach based on nearest neighbor rule and cut edges. In the first step of our approach, a relative neighborhood graph based on all training samples is constructed for each unlabeled sample, and the unlabeled samples whose edges are all connected to training samples from the same class are labeled. These newly labeled samples are then added into the training samples. In the second step, standard self-training algorithm using nearest neighbor rule is applied for classification until a predetermined stopping criterion is met. In the third step, a statistical test is applied for label modification, and in the last step, the remaining unlabeled samples are classified using standard nearest neighbor rule. The main advantages of the proposed method are: (1) it reduces the error reinforcement by using relative neighborhood graph for classification in the initial stages of semi-supervised learning; (2) it introduces a label modification mechanism for better classification performance. Experimental results show the effectiveness of the proposed approach.     

Label Propagation through Linear Neighborhoods

In many practical data mining applications such as text classification, unlabeled training examples are readily available, but labeled ones are fairly expensive to obtain. Therefore, semi supervised learning algorithms have aroused considerable interests from the data mining and machine learning fields. In recent years, graph-based semi supervised learning has been becoming one of the most active research areas in the semi supervised learning community. In this paper, a novel graph-based semi supervised learning approach is proposed based on a linear neighborhood model, which assumes that each data point can be linearly reconstructed from its neighborhood. Our algorithm, named linear neighborhood propagation (LNP), can propagate the labels from the labeled points to the whole data set using these linear neighborhoods with sufficient smoothness. A theoretical analysis of the properties of LNP is presented in this paper. Furthermore, we also derive an easy way to extend LNP to out-of-sample data. Promising experimental results are presented for synthetic data, digit, and text classification tasks.     

半监督模式下社团结构划分方法

为了对有标签和无标签节点混合的网络进行分类,给出了一种基于半监督学习的信息传递分类算法,算法首先确定网络中无标签节点的分类参数,然后通过对网络中所有无标签节点进行有限次的迭代计算,可以对所有节点进行分类。实验数据分析证明了该算法在进行半监督分类时具有比较好的效果。     

Adaptive edge weighting for graph-based learning algorithms

Graph-based learning algorithms including label propagation and spectral clustering are known as the effective state-of-the-art algorithms for a variety of tasks in machine learning applications. Given input data, i.e. feature vectors, graph-based methods typically proceed with the following three steps: (1) generating graph edges, (2) estimating edge weights and (3) running a graph based algorithm. The first and second steps are difficult, especially when there are only a few (or no) labeled instances, while they are important because the performance of graph-based methods heavily depends on the quality of the input graph. For the second step of the three-step procedure, we propose a new method, which optimizes edge weights through a local linear reconstruction error minimization under a constraint that edges are parameterized by a similarity function of node pairs. As a result our generated graph can capture the manifold structure of the input data, where each edge represents similarity of each node pair. To further justify this approach, we also provide analytical considerations for our formulation such as an interpretation as a cross-validation of a propagation model in the feature space, and an error analysis based on a low dimensional manifold model. Experimental results demonstrated the effectiveness of our adaptive edge weighting strategy both in synthetic and real datasets.     

基于两阶段学习的半监督支持向量机分类算法

提出了一种基于两阶段学习的半监督支持向量机(semi-supervised SVM)分类算法.首先使用基于图的标签传递算法给未标识样本赋予初始伪标识,并利用k近邻图将可能的噪声样本点识别出来并剔除;然后将去噪处理后的样本集视为已标识样本集输入到支持向量机(SVM)中,使得SVM在训练时能兼顾整个样本集的信息,从而提高SVM的分类准确率.实验结果证明,同其它半监督学习算法相比较,本文算法在标识的训练样本较少的情况下,分类性能有所提高且具有较高的可靠性.     

基于集成学习的半监督情感分类方法研究

情感分类旨在对文本所表达的情感色彩类别进行分类的任务。该文研究基于半监督学习的情感分类方法,即在很少规模的标注样本的基础上,借助非标注样本提高情感分类性能。为了提高半监督学习能力,该文提出了一种基于一致性标签的集成方法,用于融合两种主流的半监督情感分类方法:基于随机特征子空间的协同训练方法和标签传播方法。首先,使用这两种半监督学习方法训练出的分类器对未标注样本进行标注;其次,选取出标注一致的未标注样本;最后,使用这些挑选出的样本更新训练模型。实验结果表明,该方法能够有效降低对未标注样本的误标注率,从而获得比任一种半监督学习方法更好的分类效果。