Document Clustering Using Semantic Cliques Aggregation

The search engines are indispensable tools to find information amidst massive web pages and documents. A good search engine needs to retrieve information not only in a shorter time, but also relevant to the users’ queries. Most search engines provide short time retrieval to user queries;however, they provide a little guarantee of precision even to the highly detailed users’ queries. In such cases, documents clustering centered on the subject and contents might improve search results. This paper presents a novel method of document clustering, which uses semantic clique. First, we extracted the Features from the documents. Later, the associations between frequently co-occurring terms were defined, which were called as semantic cliques. Each connected component in the semantic clique represented a theme. The documents clustered based on the theme, for which we designed an aggregation algorithm. We evaluated the aggregation algorithm effectiveness using four kinds of datasets. The result showed that the semantic clique based document clustering algorithm performed significantly better than traditional clustering algorithms such as Principal Direction Divisive Partitioning (PDDP), k-means, Auto-Class, and Hierarchical Clustering (HAC). We found that the Semantic Clique Aggregation is a potential model to represent association rules in text and could be immensely useful for automatic document clustering.

Maximum Cliques of Hypergraphs and Polynomial Optimization

A remarkable connection between the clique number and the Lagrangian of a graph was established by Motzkin and Straus. Later, Rota Bul′o and Pelillo extended the theorem of Motzkin-Straus to r-uniform hypergraphs by studying the relation of local（global） minimizers of a homogeneous polynomial function of degree r and the maximal（maximum） cliques of an r-uniform hypergraph. In this paper, we study polynomial optimization problems for non-uniform hypergraphs with four different types of edges and apply it to get an upper bound of Tur′an densities of complete non-uniform hypergraphs.

Efficient keyword search over graph-structured data based on minimal covered r-cliques

Keyword search is an alternative for structured languages in querying graph-structured data.A result to a keyword query is a connected structure covering all or part of the queried keywords.The textual coverage and structural compactness have been known as the two main properties of a relevant result to a keyword query.Many previous works examined these properties after retrieving all of the candidate results using a ranking function in a comparative manner.However,this needs a time-consuming search process,which is not appropriate for an interactive system in which the user expects results in the least possible time.This problem has been addressed in recent works by confining the shape of results to examine their coverage and compactness during the search.However,these methods still suffer from the existence of redundant nodes in the retrieved results.In this paper,we introduce the semantic of minimal covered r-clique(MCCr)for the results of a keyword query as an extended model of existing definitions.We propose some efficient algorithms to detect the MCCrs of a given query.These algorithms can retrieve a comprehensive set of non-duplicate MCCrs in response to a keyword query.In addition,these algorithms can be executed in a distributive manner,which makes them outstanding in the field of keyword search.We also propose the approximate versions of these algorithms to retrieve the top-k approximate MCCrs in a polynomial delay.It is proved that the approximate algorithms can retrieve results in two-approximation.Extensive experiments on two real-world datasets confirm the efficiency and effectiveness of the proposed algorithms.

Social cliques in male northern muriquis Brachyteles hypoxanthus

Analyses of spatial relationships and social interactions provide insights into the social structure of animal societies and the ways in which social preferences among and between dyads affect higher order social relationships. In this paper we de- scribe the patterns of spatial associations and social interactions among adult male northern muriquis in order to evaluate the dy- namics of their social networks above the dyadic levels. Systematic observations were made on the 17 adult males present in a multi-male/multi-female group from April 2004 through February 2005, and in July 2005. Analyses of their spatial relationships identified two distinct male cliques; some adult males （called ＂N＂ males） were more connected to the females and immatures than other adult males （＂MU＂ males）, which were more connected to one another. Affiliative interactions were significantly higher among dyads belonging to the same clique than to different cliques. Although frequencies of dyadic agonistic interactions were similarly low among individuals within and between cliques, MU males appeared to be subordinate to N males. Nonetheless, there were no significant differences in the copulation rates estimated for MU males and N males. Mutual benefits of cooperation between MU and N cliques in intergroup encounters might explain their ongoing associations in the same mixed-sex group

Disjoint Cliques in Claw-free Graphs

A graph is said to be claw-free if it does not contain an induced subgraph isomorphic to K_（1,3）. Let s and k be two integers with 0≤s≤k and let G be a claw-free graph of order n. In this paper, we investigate clique partition problems in claw-free graphs. It is proved that if n≥3 s ＋4（k-s） and d（x）＋ d（y）≥n-2 s ＋2 k ＋1 for any pair of non-adjacent vertices x, y of G, then G contains s disjoint K3 s and k-s disjoint K4 s such that all of them are disjoint. Moreover, the degree condition is sharp in some cases.

Proof of Ding’s Conjecture on Maximal Stable Sets and Maximal Cliques in Planar Graphs

X. Deng et al. proved Chvātal＇s conjecture on maximal stable sets and maximal cliques in graphs. G. Ding made a conjecture to generalize Chvátal＇s conjecture. The purpose of this paper is to prove this conjecture in planar graphs and the complement of planar graphs.

Identification of key genes underlying clinical features of hepatocellular carcinoma based on weighted gene co‑expression network analysis and bioinformatics analysis

Objective: To identify module genes that are closely related to clinical features of hepatocellular carcinoma (HCC) by weighted gene co‑expression network analysis, and to provide a reference for early clinical diagnosis and treatment. Methods: GSE84598 chip data were downloaded from the GEO database, and module genes closely related to the clinical features of HCC were extracted by comprehensive weighted gene co‑expression network analysis. Hub genes were identified through protein interaction network analysis by the maximum clique centrality (MCC) algorithm;Finally, the expression of hub genes was validated by TCGA database and the Kaplan Meier plotter online database was used to evaluate the prognostic relationship between hub genes and HCC patients. Results: By comparing the gene expression data between HCC tissue samples and normal liver tissue samples, a total of 6 262 differentially expressed genes were obtained, of which 2 207 were upregulated and 4 055 were downregulated. Weighted gene co‑expression network analysis was applied to identify 120 genes of key modules. By intersecting with the differentially expressed genes, 115 candidate hub genes were obtained. The results of enrichment analysis showed that the candidate hub genes were closely related to cell mitosis, p53 signaling pathway and so on. Further application of the MCC algorithm to the protein interaction network of 115 candidate hub genes identified five hub genes, namely NUF2, RRM2, UBE2C, CDC20 and MAD2L1. Validation of hub genes by TCGA database revealed that all five hub genes were significantly upregulated in HCC tissues compared to normal liver tissues;Moreover, survival analysis revealed that high expression of hub genes was closely associated with poor prognosis in HCC patients. Conclusions: This study identifies five hub genes by combining multiple databases, which may provide directions for the clinical diagnosis and treatment of HCC.

A Remark on the Characterization of Triangulated Graphs

In this study, we consider the problem of triangulated graphs. Precisely we give a necessary and sufficient condition for a graph to be triangulated. This gives an alternative characterization of triangulated graphs. Our method is based on the so-called perfectly nested sequences.

一种有效的并行高维聚类算法

针对CLQUE算法聚类结果精确性不高的缺点,提出利用小波变换来生成自适应网格的方法对CLIQUE算法进行改进,将改进算法并行化以增强聚类维数升高时算法的可伸缩性,并将其应用于药品的销售预测。实验表明本算法聚类结果的精确性高,可伸缩性好,并且有效地降低了计算复杂度。

高维数据的高密度子空间聚类算法

高维数据具有稀疏性与易受维度灾难影响的特点,这使高维数据聚类的精度与的效率一直难以得到保证,因此采用子空间聚类的方式减小稀疏性与维度灾难对聚类结果的影响。首先采用随机抽样的方式从高维数据中挑选出适合聚类的维度生成子空间,并结合hoeffding界保证抽样结果的有效性。其次利用网格的邻接性,在子空间内生成混合网格,即可以保证数据的完整性也可以提高子空间密度。最后根据子空间的相似度与相异度,对维度剪枝,再次提高子空间密度。算法在加州大学欧文分校数据集(University of California-Irvine,UCI)上能够取得较好的结果,而且算法在的伸缩性以及抗噪声能力上有较好的表现。

基于图挖掘的文本主题识别方法研究综述

本文通过文献调研分析,将基于图挖掘的文本主题识别方法总结为中心度方法、紧密关联子图查找和图聚类三种,后两者又细分为基于clique子团或类clique子团、基于图拓扑结构或结点属性聚类的方法。中心度方法通过对比文本网络中术语结点的重要度来实现文本主题的识别,紧密关联子图查找和图聚类方法则是根据文本图中术语结点和边的属性相似度来识别文本核心主题。基于语言文本网络自身特性,如何构建复杂文本关系图来同时揭示术语间的句法、共现和语义关系,如何基于术语关联和图拓扑结构识别其中的紧密关联子团,基于何种标准将紧密关联子团聚类以揭示文本核心主题,都是未来需要进一步深入研究的问题。

高维不确定数据的子空间聚类算法

如何降低不确定数据对高维数据聚类的影响是当前的研究难点。针对由不确定数据与维度灾难导致的聚类精度低的问题,采用先将不确定数据确定化,后对确定数据聚类的方法。在将不确定数据确定化的过程中,将不确定数据分为值不确定数据与维度不确定数据,并分别处理以提高算法效率。采用结合期望距离的K近邻(K NN)查询得到对聚类结果影响最小的不确定数据近似值以提高聚类精度。在得到确定数据之后,采用子空间聚类的方式避免维度灾难的影响。实验结果证明,基于Clique的高维不确定数据聚类算法(UClique)在UCI数据集上有较好的表现,有良好的抗噪声能力和伸缩性,在高维数据上能得到较好的聚类结果,在不同的不确定数据集实验中能够得到较高精度的实验结果,体现出算法具有一定的健壮性,能够有效地对高维不确定数据集聚类。

基于多重文本关系图中clique子团聚类的主题识别方法研究

在网络成为最主要科学交流和信息传播渠道的今天,越来越多的机构将其研究成果以电子化形式呈现,这些电子化的文本资源中蕴涵着丰富的语义信息。面对这些海量的资源,科研人员很难在短时间内快速捕获文本中的主旨内容。如何高效准确地呈现文本资源中的核心主题,辅助科研人员对文本集中的重要关联信息进行聚焦,提高科研效率,一直是文本挖掘研究中的一个重要问题。在对现有有益研究成果借鉴的基础上,结合文本中术语和术语关系的特点,论文提出将文本中的术语和术语间的共现、句法和语义关系利用图结构进行表示,识别文本关系图中的紧密关联子团,基于所得到的紧密关联子团聚类来揭示文本子主题的整体研究思路。开展了两个方面的研究:①将文本集中的术语和术语间各种关系属性进行叠加归并,构建多重文本关系叠加模型;②基于clique子团间相似性距离和语义标识,进行聚类识别文本集中所包含的重要子主题。论文采用"migraine disorders"主题中近五年的文献构建文本集,对提出的方法开展了2个有效性实验。实验1与文本中领域专家所给出的标引词按语义类型分组结果对比,结果表明论文提出的方法与领域专家给出的标引词语义类型分组结果具有一致性;实验2与目前广泛使用的LDA方法结果进行对比,在准确率和召回率上都较LDA方法有所提高。2个实验均证明了文中方法的有效性。

基于子空间聚类算法的时空轨迹聚类

已有的时空轨迹聚类方法一般以整条轨迹作为聚类单元,聚类效果较低且不能识别轨迹局部特征;另一种轨迹聚类方法是以划分后轨迹段为聚类单元,算法效率较低且不能很好地支持多属性聚类。该文提出基于子空间聚类算法的时空轨迹聚类。首先引入数据归约的思想,将轨迹进行离散化处理,再运用CLIQUE算法对离散化后的轨迹段进行聚类。实验结果表明,此轨迹聚类方法具有较高的伸缩性,能有效地处理多维轨迹数据并识别轨迹的局部聚类特征,能揭示时空轨迹在不同子空间的运动规律。

基于多重文本术语关系叠加识别文本核心主题的有效性探索

目前基于图或网络进行文本主题挖掘的研究大多是基于单一文本术语关系,而文本是由一系列具有语义信息的术语,按照一定的逻辑结构构成的,这些术语除了物理位置上共现关系外,还存在句法上的支配从属关系和隐含的语义关联,仅利用单一术语关系对文本内容进行分析难免会造成信息的丢失,因此本文尝试将术语间的共现、句法和语义三种关系进行叠加,探索基于多重文本术语关系识别核心主题的有效性。文中选取PubMed数据库2012-2014年"migraine disorders"主题相关的249篇论文进行实验,结果表明术语和关系的叠加使文本主题信息更为凸显,同时存在三种关系的术语和边可表征文本的重要内容。对同时存在三种关系的术语和边组成多重文本术语关系图深度分析显示,叠加术语关系图中所包含的clique子团的边数和结点数少于术语共现关系图,但多于术语语义和句法关系图;在凝聚度最大的前20个clique中,叠加术语关系图中所含clique的凝聚度要高于共现、句法和语义三者中的任何一个,且这种差异具有统计学意义。多重术语关系的叠加平衡共现、句法和语义三种关系,在减少术语共现关系影响的同时增加术语语义和句法关系的优势,将三者含有的信息量进行叠加,克服了单独考虑一种术语关系时造成的信息丢失。

基于CLIQUE的聚类算法研究

聚类分析是数据挖掘研究领域中一个非常活跃的研究课题.本文重点分析了高维度数据的自动子空间聚类算法(CLIQUE)及其各类改进算法,并对其未来发展方向进行了简要展望.

一种用于居住热区聚类的改进CLIQUE算法

在居住热区分析应用中,已有的CLIQUE算法密度阈值初始化多采用主观性较强的经验值,容易对聚类结果造成不良影响.针对该问题提出了一种自适应密度阈值选取的CLIQUE算法(APS-CLIQUE,Adaptive Parameter Selection-CLIQUE),并对聚类边界进行了优化处理.该算法首先使用四分位数箱型模型排除数据形态两端对结果的干扰,解决密度阈值自适应问题;其次通过边界网格的判定,提高了聚类边界精度.使用UCI标准数据集、成都市出租车GPS轨迹浮动数据集进行了对比实验,实验结果表明本文算法的Dunn指数较CLIQUE算法分别提高了26.53%、28.66%.

基于聚类高维空间算法的离群数据挖掘技术研究

离群数据挖掘是数据挖掘领域的一个研究分支,而聚类算法分析则是进行离群数据挖掘的重要研究方法之一。文中首先分析研究离群数据挖掘方法,对多个离群数据挖掘算法进行分析比较,讨论各自的优点和不足,同时针对高维空间数据的特点,分析挖掘高维空间数据中的离群点方法。其次对聚类分析算法进行讨论,分析一种基于网格和基于密度的聚类方法——聚类高维空间算法(CLIQUE算法),运用它可以更好地挖掘高维空间中的离群数据。提出了CLIQUE算法的有待改进的思想,为以后的研究指明方向。

基于Clique聚类的精神分裂症多文档自动摘要研究

利用SemRep将精神分裂文献集处理为语义述谓项集,建立语义述谓网络,从节点、边及网络凝聚性三个层次提取文献集的核心内容,生成的图形摘要由具有高凝聚性的clique组成,探索利用网络属性结合语义信息的生物医学多文档自动摘要方法。通过clique共节点矩阵对其聚类获取摘要的子主题,采用人工标准对摘要内容的覆盖面进行评价,结果显示摘要的准确率为0.93,召回率为0.68,F值为0.79。该方法能有效识别文献集中的核心内容,网络图中所富含的语义信息能较完整地表达摘要内容。

基于相对熵和子空间二次过滤的CLIQUE改进算法

提出了一种基于相对熵和子空间二次过滤的CLIQUE改进算法。该算法根据数据的分布情况对每一维采用自适应的网格划分方法,减少了全空间中网格单元的数量,降低了算法的时间复杂度。算法采用了基于维关联度的子空间二次过滤策略,提高了聚类结果的准确性。实验使用仿真数据表明,该算法在精度,时间复杂性等方面的表现优越。