聚类分析算法概览：从统计到生物信息学的广泛应用

需积分: 9 106 浏览量更新于2024-07-23 收藏 1.49MB PDF 举报

"这篇文章是关于聚类分析的综合概述，主要涵盖了聚类算法的各种类型、应用领域以及相关的重要概念，如亲和力度量和聚类验证。它出自IEEE Transactions on Neural Networks，由Rui Xu和Donald Wunsch II撰写，讨论了在统计学、计算机科学和机器学习等领域中的聚类技术，并通过基准数据集、旅行商问题和生物信息学等实例展示了聚类的应用。文章还涉及了自适应共振理论(ART)、神经网络和自组织特征映射(SOFM)等相关主题。" 聚类分析是一种无监督学习方法，用于在没有先验知识的情况下对数据进行分组，以便发现数据的内在结构和模式。文章介绍了多种聚类算法，这些算法在不同的社区中被广泛研究和发展，包括但不限于K-means、层次聚类、DBSCAN（基于密度的聚类）、谱聚类和BIRCH（大规模数据的边界包容树聚类）。每种算法都有其独特的优点和适用场景，例如K-means适合处理凸形状的簇，而DBSCAN则能够识别任意形状的簇。文章中，作者讨论了聚类算法在实际问题中的应用，如旅行商问题，这是一个经典的优化问题，聚类可以帮助减少路径规划的复杂性。生物信息学是另一个重要的应用领域，聚类分析被用来揭示基因表达数据的模式，帮助科学家理解生物系统的复杂性。亲和力度量是聚类算法中的关键组成部分，用于量化数据点之间的相似性或距离。选择合适的亲和力度量对于聚类结果的质量至关重要，常见的有欧氏距离、曼哈顿距离和余弦相似度等。文章也提到了聚类验证的重要性，这是评估聚类结果是否有效的一种方法，包括内部验证（如Calinski-Harabasz指数和Davies-Bouldin指数）和外部验证（如基于已知类别标签的评价）。此外，文章还探讨了神经网络在聚类分析中的作用，如自适应共振理论(ART)和自组织特征映射(SOFM)，这两者都是神经网络模型，能够自适应地学习和组织输入数据的结构。这篇综述提供了聚类分析的全面视角，对于理解和选择适合特定任务的聚类算法具有很高的参考价值，同时对聚类相关领域的最新进展进行了总结，对研究者和实践者都极具指导意义。

XU AND WUNSCH II: SURVEY OF CLUSTERING ALGORITHMS 651

distance measures, especially the mean-based ones, were intro-

duced by Yager, with further discussion on their possible effect

to control the hierarchical clustering process [289].

The common criticism for classical HC algorithms is that they

lack robustness and are, hence, sensitive to noise and outliers.

Once an object is assigned to a cluster, it will not be considered

again, which means that HC algorithms are not capable of cor-

recting possible previous misclassiﬁcation. The computational

complexity for most of HC algorithms is at least

and

this high cost limits their application in large-scale data sets.

Other disadvantages of HC include the tendency to form spher-

ical shapes and reversal phenomenon, in which the normal hier-

archical structure is distorted.

In recent years, with the requirement for handling large-scale

data sets in data mining and other ﬁelds, many new HC tech-

niques have appeared and greatly improved the clustering per-

formance. Typical examples include CURE [116], ROCK [117],

Chameleon [159], and BIRCH [295].

The main motivations of BIRCH lie in two aspects, the ability

to deal with large data sets and the robustness to outliers [295].

In order to achieve these goals, a new data structure, clustering

feature (CF) tree, is designed to store the summaries of the

original data. The CF tree is a height-balanced tree, with each

internal vertex composed of entries deﬁned as

child

, where is a representation of the cluster and

is deﬁned as

, where is the number of

data objects in the cluster,

is the linear sum of the objects,

and SS is the squared sum of the objects, child

is a pointer to the

th child node, and is a threshold parameter that determines

the maximum number of entries in the vertex, and each leaf

composed of entries in the form of

, where

is the threshold parameter that controls the maximum number of

entriesin theleaf. Moreover,the leavesmustfollowtherestriction

that the diameter

of each entry in the leaf is less than a threshold . The CF

tree structure captures the important clustering information of

the original data while reducing the required storage. Outliers

are eliminated from the summaries by identifying the objects

sparsely distributed in the feature space. After the CF tree is

built, an agglomerative HC is applied to the set of summaries to

perform global clustering. An additional step may be performed

to reﬁne the clusters. BIRCH can achieve a computational

complexity of

Noticing the restriction of centroid-based HC, which is

unable to identify arbitrary cluster shapes, Guha, Rastogi, and

Shim developed a HC algorithm, called CURE, to explore more

sophisticated cluster shapes [116]. The crucial feature of CURE

lies in the usage of a set of well-scattered points to represent

each cluster, which makes it possible to ﬁnd rich cluster shapes

other than hyperspheres and avoids both the chaining effect

[88] of the minimum linkage method and the tendency to favor

clusters with similar sizes of centroid. These representative

points are further shrunk toward the cluster centroid according

to an adjustable parameter in order to weaken the effects of

outliers. CURE utilizes random sample (and partition) strategy

to reduce computational complexity. Guha et al. also proposed

another agglomerative HC algorithm, ROCK, to group data

with qualitative attributes [117]. They used a novel measure

“link” to describe the relation between a pair of objects and their

common neighbors. Like CURE, a random sample strategy is

used to handle large data sets. Chameleon is constructed from

graph theory and will be discussed in Section II-E.

Relative hierarchical clustering (RHC) is another exploration

that considers both the internal distance (distance between a

pair of clusters which may be merged to yield a new cluster)

and the external distance (distance from the two clusters to the

rest), and uses the ratio of them to decide the proximities [203].

Leung et al. showed an interesting hierarchical clustering based

on scale-space theory [180]. They interpreted clustering using

a blurring process, in which each datum is regarded as a light

point in an image, and a cluster is represented as a blob. Li

and Biswas extended agglomerative HC to deal with both nu-

meric and nominal data. The proposed algorithm, called simi-

larity-based agglomerative clustering (SBAC), employs a mixed

data measure scheme that pays extra attention to less common

matches of feature values [183]. Parallel techniques for HC are

discussed in [69] and [217], respectively.

C. Squared Error—Based Clustering (Vector Quantization)

In contrast to hierarchical clustering, which yields a succes-

sive level of clusters by iterative fusions or divisions, partitional

clustering assigns a set of objects into

clusters with no hier-

archical structure. In principle, the optimal partition, based on

some speciﬁc criterion, can be found by enumerating all pos-

sibilities. But this brute force method is infeasible in practice,

due to the expensive computation [189]. Even for a small-scale

clustering problem (organizing 30 objects into 3 groups), the

number of possible partitions is

. Therefore, heuristic

algorithms have been developed in order to seek approximate

solutions.

One of the important factors in partitional clustering is the

criterion function [124]. The sum of squared error function is

one of the most widely used criteria. Suppose we have a set of

objects

, and we want to organize them

into

subsets . The squared error criterion

then is deﬁned as

where

a partition matrix;

if cluster

otherwise

with

cluster prototype or centroid (means) matrix;

sample mean for the th cluster;

number of objects in the th cluster.

Note the relation between the sum of squared error criterion

and the scatter matrices deﬁned in multiclass discriminant anal-

ysis [75],

剩余33页未读，继续阅读

xiaoweng79

粉丝: 0
资源: 3

聚类分析算法概览：从统计到生物信息学的广泛应用

聚类分析关键问题综述与解决方案

文本聚类技术综述及其应用探讨

2002-2009年聚类分析进展：系统聚类与快速聚类方法详解

聚类分析综述.docx

数据挖掘中聚类分析综述.pdf

数据挖掘中聚类分析综述.docx

聚类分析聚类算法综述ppt

聚类分析文献综述

地铁站聚类分析研究综述

时间序列聚类分析文献综述

最新资源