传递闭包与谱聚类结合的多中心模糊C均值算法探索
58 浏览量
更新于2024-08-26
收藏 3.36MB PDF 举报
"该研究论文探讨了一种基于传递闭包和谱聚类的多中心模糊C均值（Fuzzy C-means, FCM）算法。文章由武汉理工大学、武汉纺织大学和华中科技大学的研究人员共同完成，发表在《应用软计算》期刊上。该算法旨在改进传统的模糊C均值聚类方法，解决其在处理复杂数据集时存在的问题，如单中心限制和对噪声数据的敏感性。"
正文:
模糊C均值（Fuzzy C-means）算法是数据挖掘和机器学习领域中广泛应用的一种聚类方法，因其能够处理具有模糊边界的样本而备受青睐。然而，传统的FCM算法存在一些局限性，比如它通常假设数据集只有一个中心，这可能无法准确反映实际中复杂的数据结构。此外，FCM对于异常值或噪声也比较敏感，这些因素都可能导致聚类结果的不理想。
本研究论文提出了一种新的多中心模糊C均值算法，该算法结合了传递闭包和谱聚类的概念。传递闭包是一种在图论中用于分析节点间关系的方法，它可以捕捉数据之间的非对称性和传递性。在聚类场景中，传递闭包可以帮助识别样本之间的隐含关联，增强聚类的连通性和稳定性。
另一方面，谱聚类是一种利用数据的相似性矩阵的谱特性进行聚类的技术，它能有效处理非凸形状的簇。通过将这两种方法整合到FCM算法中，研究者旨在克服传统FCM的单中心限制，同时利用谱聚类来改善对噪声和复杂结构的处理能力。
论文详细介绍了算法的设计过程，包括如何构建传递闭包矩阵以及如何结合谱聚类来确定多中心。实验部分对比了新算法与传统FCM和其他聚类方法在多种数据集上的性能，验证了新算法在处理复杂数据结构时的优越性。关键词包括模糊C均值、多中心、格子相似性以及谱聚类，表明了该研究的主要关注点和理论基础。
这篇研究论文为复杂数据集的聚类提供了一个新颖且强大的工具，通过结合不同的理论概念，提高了聚类的准确性和鲁棒性。这一方法不仅对数据挖掘领域有贡献，也为解决现实世界中的复杂问题提供了新的思路。
S.
Zeng
et
al.
/
Applied
Soft
Computing
16
(2014)
89–101
91
Fig.
1.
Schematic
diagram
of
the
non-convex
shaped
datasets
classification.
(a)
Partitioning
the
dataset
by
FCM
algorithm
with
multi-centers;
(b)
the
relationship
graph
of
the
similarity
among
subclusters;
(c)
the
results
of
merging
the
subclusters.
(For
interpretation
of
the
references
to
color
in
this
text,
the
reader
is
referred
to
the
web
version
of
this
article.)
efficient
clustering
criterion
is
the
normalized
cut
(Ncut)
[7]
which
is
defined
as
Ncut(A,
B)
=
assoc(A,
B)
assoc(A,
V)
+
assoc(A,
B)
assoc(B,
V)
(7)
where
assoc(A,
B)
=
i∈A,j∈B
S
ij
.
In
other
words,
Ncut
criterion
com-
putes
the
cut
cost
as
a
fraction
of
the
total
edge
connections
to
all
the
nodes
and
achieves
a
better
balance
in
the
cardinality
A
and
B.
Thus
the
aim
is
to
minimize
Ncut.
Following
some
algebraic
for-
mulations,
it
turns
out
[8]
that
minimizing
normalized
cut
can
be
equivalently
recast
as
min
Tr(H
T
(D
−
S)H)
A
1
,
.
.
.,
A
c
s.t.
H
T
DH
=
I
(8)
where
A
1
,
.
.
.,
A
c
is
a
partition
of
X
(A
1
∪
·
·
·
∪
A
c
=
X,
A
i
∩
A
j
=
,
i
/=
j
and
A
i
/=
,
i
=
1,
.
.
.,
c),
c
is
the
number
of
classes,
D
is
an
N
×
N
diagonal
matrix
with
D
ii
=
j
s
ij
,
I
is
the
identity
matrix,
H
∈
N×c
is
a
specific
discrete
matrix,
and
Tr
denotes
the
trace
of
a
matrix.
Unfortunately,
solving
the
above
discrete
optimization
problem
is
NP-hard.
To
make
it
tractable,
an
efficient
relaxation
is
adopted
so
as
to
solve
a
real-valued
problem
instead
of
a
discrete-valued
one.
This
is
done
by
computing
the
first
k
generalized
eigenvec-
tors
z
1
,
.
.
.,
z
k
,
corresponding
to
the
k
smallest
eigenvalues,
of
the
generalized
eigenvalue
problem
(D
−
S)z
=
Dz
(9)
where
is
the
eigenvalue
and
z
is
the
corresponding
eigenvec-
tor.
Furthermore,
D
−
S
is
called
as
the
normalized
Laplacian
matrix
which
is
symmetric
positive
semi-definite.
Finally,
fuzzy
C-means
method
is
performed
on
the
row
vectors
of
Z
=
[z
1
,
.
.
.,
z
k
]
∈
N×k
to
obtain
the
clusters.
3.
The
new
multi-center
FCM
algorithm
Many
datasets
are
non-convex
shaped
in
practical
clustering
problems.
As
is
showed
in
Fig.
1(a),
red
stars
and
green
stars
repre-
sent
samples
belonging
to
different
classes.
The
direct
application
of
the
FCM
algorithm
cannot
achieve
good
results,
because
the
FCM
algorithm
is
only
suitable
in
spherical
clusters,
it
cannot
recognize
irregular
or
elongated
shaped
clusters,
and
it
is
sensitive
to
the
ini-
tial
centers
of
clusters.
For
the
purpose
of
solving
these
problems,
we
propose
the
multi-center
FCM
algorithm
based
on
transitive
closure
and
spectral
clustering
(MFCM-TCSC).
This
method
divides
irregular
classes
into
lots
of
subclusters
(multi-cluster),
transforms
the
classification
problem
into
a
problem
of
merging
subclusters.
There
is
no
need
to
consider
the
initial
number
of
clusters,
whether
the
distribution
of
datasets
is
spherical,
nor
the
local
optimum
problem
in
clustering.
3.1.
The
merge
criteria
of
subclusters
in
the
multi-center
fuzzy
C-means
clustering
In
order
to
recognize
the
irregular
classes,
one
class
is
repre-
sented
by
multiple
subclusters.
That
is,
partitioning
the
irregular
class
into
some
subclusters
(multi-clusters)
at
first,
hence
the
classification
problem
can
be
converted
into
a
subcluster
merg-
ing
problem.
As
is
showed
in
Fig.
1(a),
the
dataset
is
made
up
of
two
classes.
When
the
multi-center
FCM
algorithm
is
adopted,
the
dataset
is
clustered
into
6
subclusters.
The
first
class
is
partitioned
into
4
subclusters,
and
the
second
is
partitioned
into
2
subclusters.
Merge
those
subclusters
and
get
the
results
showed
in
Fig.
1(c).
In
the
merging
the
subclusters
process,
two
criteria
are
acquired
from
analyzing
the
results
in
Fig.
1:
(1)
the
subclusters
of
the
same
class
should
satisfy
the
similarity
and
nearness
relations
(such
as
the
subclusters
1
and
2
in
Fig.
1(a));
(2)
the
similarity
can
be
tran-
sitive
between
the
subclusters
of
the
same
class
(in
Fig.
1(a),
the
similarity
between
subcluster
1
and
subcluster
4
can
be
obtained
by
taking
the
maximal
similarity
value
through
the
path:
subcluster
1
→
subcluster
2
→
subcluster
3
→
subcluster
4).
In
this
paper,
the
number
of
subclusters
is
√
N,
which
is
the
upper
limit
of
the
number
of
cluster
based
on
the
Literature
[5,14,15].
After
the
large
classes
or
non-spherical
datasets
are
divided
into
lots
of
subclusters
by
using
the
FCM
algorithm,
then
merge
the
subclusters
under
those
two
criteria.
3.2.
The
representation
of
the
subclusters’
features
After
the
multi-center
FCM
algorithm
clustering,
the
centers
and
the
fuzzy
membership
values
of
subclusters
will
be
derived.
The
representation
of
the
features
of
subclusters
can
be
studied
in
two
aspects:
the
centers
of
subclusters
and
the
information
of
fuzzy
membership
matrix.
(1)
Replace
subclusters
with
features
of
cen-
ters.
That
is,
the
features
of
the
center
p
i
(i
=
1,
2,
.
.
.,
c)
∈
R
q
as
the
features
of
the
ith
subcluster.
It
is
the
sparsification
of
samples,
which
can
reduce
the
computational
load
of
the
similarity
measure
and
the
spectral
clustering.
But
the
position
of
a
center
is
related
closely
to
the
quantity
of
samples
in
this
cluster
which
the
center
represents.
If
one
class
is
partitioned
sparsely
and
another
densely,
剩余12页未读，继续阅读
2022-07-14 上传
230 浏览量
2020-05-23 上传
2023-07-02 上传
2011-05-07 上传
2022-11-12 上传
2021-07-10 上传
点击了解资源详情
点击了解资源详情
weixin_38654855
- 粉丝: 6
- 资源: 888
我的内容管理
展开
最新资源
- 全国江河水系图层shp文件包下载
- 点云二值化测试数据集的详细解读
- JDiskCat：跨平台开源磁盘目录工具
- 加密FS模块：实现动态文件加密的Node.js包
- 宠物小精灵记忆配对游戏：强化你的命名记忆
- React入门教程：创建React应用与脚本使用指南
- Linux和Unix文件标记解决方案：贝岭的matlab代码
- Unity射击游戏UI套件：支持C#与多种屏幕布局
- MapboxGL Draw自定义模式：高效切割多边形方法
- C语言课程设计：计算机程序编辑语言的应用与优势
- 吴恩达课程手写实现Python优化器和网络模型
- PFT_2019项目：ft_printf测试器的新版测试规范
- MySQL数据库备份Shell脚本使用指南
- Ohbug扩展实现屏幕录像功能
- Ember CLI 插件：ember-cli-i18n-lazy-lookup 实现高效国际化
- Wireshark网络调试工具：中文支持的网口发包与分析
