Exact and Approximation Algorithms for Clustering

In this paper we present an n^ O(k ^1-1/d ) -time algorithm for solving the k -center problem in \reals ^d , under L _∈ fty - and L ₂ -metrics. The algorithm extends to other metrics, and to the discrete k -center problem. We also describe a simple (1+ɛ) -approximation algorithm for the k -center problem, with running time O(nlog k) + (k/ɛ)^ O(k ^1-1/d ) . Finally, we present an n^ O(k ^1-1/d ) -time algorithm for solving the L -capacitated k -center problem, provided that L=Ω(n/k ^1-1/d ) or L=O(1) . Received July 25, 2000; revised April 6, 2001.     

大数据聚类算法综述

随着数据量的迅速增加,如何对大规模数据进行有效的聚类成为挑战性的研究课题。面向大数据的聚类算法对传统金融行业的股票投资分析、互联网金融行业中的客户细分等金融应用领域具有重要价值。对已有的大数据聚类算法进行了详细划分,并比较了每种聚类算法的优缺点,进一步总结了已有研究存在的问题,最后对未来的研究方向进行了展望。     

混合类型数据的聚类算法综述

在所有数据挖掘的算法中,聚类算法尤为重要。在实际应用中,数据大多是混合型的数据,既包含数值型,又包含分类型数据。因此,对混合数据进行聚类分析越来越重要。笔者首先介绍了聚类的定义,然后详细阐述了K-prototype聚类算法的基本原理,最后详细介绍了近年来各学者对混合类型数据的聚类算法的研究现状和其具体应用。     

数据流聚类算法研究

许多应用程序会产生大量的流数据,如网络流、web点击流、视频流、事件流和语义概念流。数据流挖掘已成为热点问题,其目标是从连续不断的流数据中提取隐藏的知识/模式。聚类作为数据流挖掘领域的一个重要问题,在近期被广泛研究。不同于传统的静态数据聚类问题,数据流聚类面临有限内存、一遍扫描、实时响应和概念漂移等许多约束。本文对数据流挖掘中的各种聚类算法进行了总结。首先介绍了数据流挖掘的约束;随后给出了数据流聚类的一般模型,并描述了其与传统数据聚类之间的关联;最后提出数据流聚类领域中进一步的研究热点和研究方向。     

On Density-Based Data Streams Clustering Algorithms: A Survey简

Clustering data streams has drawn lots of attention in the last few years due to their ever-growing presence. Data streams put additional challenges on clustering such as limited time and memory and one pass clustering. Furthermore, discovering clusters with arbitrary shapes is very important in data stream applications. Data streams are infinite and evolving over time, and we do not have any knowledge about the number of clusters. In a data stream environment due to various factors, some noise appears occasionally. Density-based method is a remarkable class in clustering data streams, which has the ability to discover arbitrary shape clusters and to detect noise. Furthermore, it does not need the nmnber of clusters in advance. Due to data stream characteristics, the traditional density-based clustering is not applicable. Recently, a lot of density-based clustering algorithms are extended for data streams. The main idea in these algorithms is using density- based methods in the clustering process and at the same time overcoming the constraints, which are put out by data streanFs nature. The purpose of this paper is to shed light on some algorithms in the literature on density-based clustering over data streams. We not only summarize the main density-based clustering algorithms on data streams, discuss their uniqueness and limitations, but also explain how they address the challenges in clustering data streams. Moreover, we investigate the evaluation metrics used in validating cluster quality and measuring algorithms＇ performance. It is hoped that this survey will serve as a steppingstone for researchers studying data streams clustering, particularly density-based algorithms.     

基于聚类分析技术的数据清洗研究

数据清洗是建立数据仓库及进行数据挖掘的一个重要步骤。数据清洗的核心是检测近似重复记录,而聚类是将相似度高的数据对象聚集到一个类中的分析方法。本文描述的数 据清洗过程就基于聚类分析,它将基于密度的改进聚类算法ICAD应用到数据清洗过程中,该算法通过不断调节密度发现近似重复记录,快速完成大容量数据清洗任务。     

数据挖掘中聚类算法比较研究

聚类分析技术是数据挖据中的一种重要技术。本文介绍了数据挖掘对聚类的典型要求和聚类方法的分类，研究分析了聚类的主要算法．并从多个方面对这些算法的性能进行比较。     

数据挖掘中的聚类算法综述

聚类是数据挖掘中用来发现数据分布和隐含模式的一项重要技术。全面总结了数据挖掘中聚类算法的研究现状,分析比较了它们的性能差异和各自存在的优点及问题,并结合多媒体领域的应用需求指出了其今后的发展趋势。     

数据流聚类算法研究

随着传感器数据、互联网数据、金融数据(股票价格等)、在线拍卖以及事务日志(网站访问日志、电话记录日志)等的不断产生,数据流成为了主要的数据形式.流挖掘是数据库领域的研究热点,有很大的应用前景.本文首先简单介绍了数据流与聚类分析的概念,阐述了数据流中的聚类分析及其要求,详细说明了主要传统聚类方法的演变及各自代表性流数据聚类算法,并对其进行总结.在本文的最后,对流数据挖掘的前景做出展望.     

数据挖掘中的聚类算法分析

随着计算机网络的飞速发展,各行各业每天都产生大量数据。为了大量数据中提取有效信息,衍生了数据挖掘技术。聚类分析是数据挖掘领域的一项重要工具,广泛应用于不同领域,比如模式识别、医药、统计学等。现实生活中的数据有数值型数据、分类型数据和混合型数据。基于此,针对这三种数据分别介绍k-means、k-modes和k-prototype算法,以提高聚类分析效率。     

数据挖掘中聚类算法比较研究

聚类分析技术是数据挖据中的一种重要技术.本文介绍了数据挖掘对聚类的典型要求和聚类方法的分类,研究分析了聚类的主要算法,并从多个方面对这些算法的性能进行比较.     

基于数据概要描述的分布式数据流聚类模型与算法

数据流挖掘可有效解决大容量流式数据的知识发现问题,并已得到广泛研究.数据流的一个典型的例子是传感器采集的流式数据.然而,随着传感器网络的应用普及,这些流式数据在很多情况下是分布式采集和管理的,这就必然导致分布式地挖掘数据流的需求.分布式数据流挖掘的最大障碍是由分布式而导致的挖掘质量或者效率问题.为适应分布式数据流的聚类挖掘,探讨了分布式数据流的挖掘模型,并且基于该模型设计了对应的概要数据结构和关键的挖掘算法,给出了算法的理论评估或者实验验证.实验说明,提出的模型和算法可以有效地减少数据通信代价,并且能保证较高的全局模式的聚类质量.     

Exact Algorithms for MAX-SAT

The maximum satisfiability problem (MAX-SAT) is stated as follows: Given a boolean formula in CNF, find a truth assignment that satisfies the maximum possible number of its clauses. MAX-SAT is MAX-SNP-complete and received much attention recently. One of the challenges posed by Alber, Gramm and Niedermeier in a recent survey paper asks: Can MAX-SAT be solved in less than 2ⁿ “steps”? Here, n is the number of distinct variables in the formula and a step may take polynomial time of the input. We answered this challenge positively by showing that a popular algorithm based on branch-and-bound is bounded by O(2ⁿ) in time, where n is the maximum number of occurrences of any variable in the input.When the input formula is in 2-CNF, that is, each clause has at most two literals, MAX-SAT becomes MAX-2-SAT and the decision version of MAX-2-SAT is still NP-complete. The best bound of the known algorithms for MAX-2-SAT is O(m2^m/5), where m is the number of clauses. We propose an efficient decision algorithm for MAX-2-SAT whose time complexity is bound by O(n2ⁿ). This result is substantially better than the previously known results. Experimental results also show that our algorithm outperforms any algorithm we know on MAX-2-SAT.     

不一致数据上精确决策树生成算法

近年来,随着现实生活中数据量的不断增大,不一致数据的出现也越发频繁,这使得人工修正不一致数据变得更加耗时.而且,人工修正数据方法本身也存在着不可避免的人为操作错误,因此,这种修正方法不再可行.如何不提前修复不一致数据,直接在不一致数据上进行分类,是该文的核心研究内容.对决策树生成算法的目标函数进行改进,使其能够直接对不一致数据进行分类,并得到较好的分类结果.对约束条件中的特征对分类结果的影响进行了多方面衡量,从而调整该特征的影响因子,使得决策树的节点分割更加精确,分类效果更优.     

基于数据挖掘的聚类算法研究

随着数据信息的积累,如何从这些海量信息中有效地提取所需要的知识成为当前数据挖掘的重要内容。聚类作为数据挖掘的重要工具,通过将数据划分成多个类,使得类内数据尽可能相似,而类间数据的相似度尽可能小,已成为研究热点。本文总结在数据挖掘中的聚类算法,针对聚类中所存在的问题进行归纳,并对未来的研究进行了展望。     

Exact Algorithms for Graph Homomorphisms

Graph homomorphism, also called H-coloring, is a natural generalization of graph coloring: There is a homomorphism from a graph G to a complete graph on k vertices if and only if G is k-colorable. During recent years the topic of exact (exponential-time) algorithms for NP-hard problems in general, and for graph coloring in particular, has led to extensive research. Consequently, it is natural to ask how the techniques developed for exact graph coloring algorithms can be extended to graph homomorphisms. By the celebrated result of Hell and Nesetril, for each fixed simple graph H, deciding whether a given simple graph G has a homomorphism to H is polynomial-time solvable if H is a bipartite graph, and NP-complete otherwise. The case where H is the cycle of length 5, is the first NP-hard case different from graph coloring. We show that for an odd integer , whether an input graph G with n vertices is homomorphic to the cycle of length k, can be decided in time . We extend the results obtained for cycles, which are graphs of treewidth two, to graphs of bounded treewidth as follows: if H is of treewidth at most t, then whether input graph G with n vertices is homomorphic to H can be decided in time .     

聚类算法在基因表达数据分析中的应用研究

针对传统聚类算法在基因表达数据处理中的不足之处,讨论了与计算智能技术相关的两种算法:模糊C均值算法(FCM)和遗传K均值算法(GKA),对FCM算法中类别数c和模糊指数m的选取进行了比较深入的研究,最后用实验数据对各算法性能进行了分析和比较。     

使用计量数据和聚类算法检测非技术损失

减少非技术损失(NTL)是实施智能电网所带来的潜在利益的重要组成部分。提出了一种基于智能电表数据的聚类算法来检测窃电和其他原因所导致的非技术性损失。通过对智能电表采集的数据进行聚类,提取正常用电行为的数据原型。然后对待检测数据样本和正常数据的聚类中心之间的距离进行计算,如果距离明显,则将其分类为NTL数据样本。最后对四种不同的异常用电指标进行空间分析,使分类结果更易于可视化。实验表明,基于GA聚类算法的NTL检测方法具有优于同类检测方法的性能。     

基于聚类算法的零售业CRM数据挖掘的应用

把数据挖掘中K-中心点聚类算法应用于基于客户价值矩阵的客户价值细分中,建立一种零售业客户细分方法,为零售超市客户保持和营销提供决策依据,并用样本进行实验,得出结论.     

基于聚类和关联规则的挖掘算法

数据挖掘技术中关联规则可以很好地发现数据项之间存在的相互关系,同时有大量的挖掘算法可供选择。聚类分析就是通过分析数据库中的记录数据,根据一定的分类规则合理地划分记录集合,确定每个记录所在类别。它所采用的分类规则是由聚类分析工具决定的。本文研究 聚类和关联规则的挖掘算法。