多密度信息驱动的自适应半监督聚类算法

165 浏览量更新于2024-08-26 收藏 2.53MB PDF 举报

本文主要探讨了一种名为"基于多个基于密度的信息的自适应半监督聚类方法"的研究论文，发表在2017年的《神经计算》(Neurocomputing)期刊第257期，193-205页。随着多媒体信息的爆炸式增长，对多媒体数据挖掘的需求和兴趣也随之大幅提升，而数据聚类作为重要的挖掘任务之一，对于理解大量多媒体数据的内在结构和信息浓缩具有关键作用。半监督学习作为一种机器学习范式，结合了有监督学习的指导信息和无监督学习的自我发现能力，是解决大规模数据集上标注困难问题的有效手段。该研究旨在通过引入多种密度基信息，提升聚类算法的性能和鲁棒性。密度基聚类方法如DBSCAN（Density-Based Spatial Clustering of Applications with Noise）利用邻域内的点密度来定义簇，而约束基聚类则考虑了额外的先验知识或规则来指导聚类过程。在论文中，作者们提出了一种自适应策略，这种策略能够动态地调整参数以适应不同的数据分布和复杂度。这种方法允许算法在处理高维和非均匀分布的数据时更有效，同时还能有效地利用少量的标注样本作为指导，减少人工标记的工作量。通过对比实验，论文展示了这种新的自适应半监督聚类方法在处理多媒体数据集上的优越性能，尤其是在精度、召回率和计算效率方面。研究者们强调了他们的方法在处理实际应用中的潜在价值，例如图像分类、视频分割、文本挖掘等领域，尤其是在缺乏大量标注数据的情况下，能显著提高数据挖掘的效率和准确性。然而，文章也指出这种方法可能存在的局限性，如对噪声和异常值的敏感性，以及对初始参数选择的依赖性，这些是未来进一步研究和改进的方向。这篇论文提供了一种创新的半监督聚类技术，它融合了密度信息和约束条件，能够在处理大规模多媒体数据时展现出良好的适应性和效率。它为解决实际问题提供了新的思路，并为进一步优化和扩展此类方法奠定了基础。

Y. Yang et al. / Neurocomputing 257 (2017) 193–205 195

concepts: evidential clustering and constraint-based clustering. EV-

CLUS uses the Dempster–Shafer theory to assign a mass function to

each instance. It provides a credal partition, which subsumes the

notions of crisp, fuzzy and possibilistic partitions. CEVCLUS con-

sists of taking advantage of prior information. Such background

knowledge is integrated as an additional term in the cost function.

Given dataset X = [ x

]

i =1

and number of clusters K , CEVCLUS aims

to obtain a clustering partition by minimizing a loss function con-

sisted of two terms:

C EVC LU S

(M, a, b) = L

EV CLUS

(M, a, b) + α

2(| ML | + | CL | )

CONST

(M)

(2)

where L

EVCLUS

( M, a, b ) represents the loss of conventional evidential

clustering (EVCLUS), and is expressed as:

EV CLUS

(M, a, b) =



i< j



i< j



aC F

+ b + d



(3)

In Eq. (3) the matrix of mass functions M = ( m

) corresponds

to a credal partition. The mass m

represents the degree of belief

that the instance x

is assigned to the cluster C

, which is regarded

by the distance between x

and representative point mean ( C

) of

cluster C

. C F

= 1 − p l

i × j

(θ ) represents the degree of conﬂict be-

tween two instances. pl

i × j

( θ) is the plausibility that the instance

and x

are in the same cluster and p l

i × j

(

θ ) is the plausibility

that the two instances are in a different cluster. a and b are two

coeﬃcients.

In the second term of Eq. (2) α

2( | ML | + | CL | )

CONST

(M) repre-

sents the loss of violating pairwise constraints, α ≥ 0 is a hyper-

parameter that controls the importance of constraints including

Must-Link(ML) and Cannot-Link(CL). Therefore, L

CONST

( M ) can be

formulated as follows:

CONST

(M) =



, x

∈ ML

p l

i × j





+ 1 − p l

i × j

(

)



, x

∈ CL

p l

i × j

(

)

+ 1 − p l

i × j

(

θ ) (4)

2.4. Constrained clustering via spectral regularization (CCSR)

In this approach [25] , a regularization framework has been de-

veloped for spectral clustering [26] in use of constraint informa-

tion. It aims to adapt the spectral embedding to accord with pair-

wise constraints by optimization, which constructs a smooth data

representation space parameterized by a spectral embedding, and

is most consistent with the pairwise constraints.

Given dataset X = [ x

]

i =1

and number of clusters K , it initially

forms a sparse symmetric similarity matrix W = [ w

]. where w

de-

notes the similarity between x

and x

. W is assumed to be non-

negative and symmetric. Then the normalized graph Laplacian is

obtained by

= I − D

−1 / 2

W D

−1 / 2

, where I is the identity matrix of

size n × n and D = diag( d

, ..., d

) with d



j=1

. Next, the

m eigenvectors v

, …, v

is computed corresponding to the

ﬁrst m smallest eigenvalues. Given F

= ( v

, …, v

), the new data

representation is written by F = F

A , it indicates that obtaining a

representation in consistent with the prior information of pairwise

constraints is equivalent to determining a suitable coeﬃcient ma-

trix A . In fact, coeﬃcient matrix A can be obtained by minimizing

the following loss function:

L (A ) =



(i, j, t

) ∈ S



A A

− t



(5)

where u

denotes the i th row of F

, F

= ( u

, …, u

)

, S =

{ (i, j, t

) } is a set of pairwise constraints, where t

is a binary in-

dicator that takes 1 or 0 to indicate x

and x

belong to the same

cluster or not. Let M = A A

, it is positive semi-deﬁnite. Then the

objective function in Eq. (5) can be re-written as:

L (M) =



(i, j, t

) ∈ S



M u

− t



(6)

M can be obtained by solving the semi-deﬁnite problem derived

from Eq. (6) such detail is shown in [25] . Once M is obtained, the

clustering partition can be ﬁnally produced by applying any con-

ventional clustering algorithm such as K-means on the new data

representation that is constructed by rows of F

1/2

2.5. Semi-supervised Naïve Bayesian classiﬁer using EM

In this approach, semi-supervised learning task is performed by

applying naive Bayes to the case of labeled and unlabeled data

with Expectation-Maximization (EM) technique [27] . Firstly a naive

Bayes classiﬁer with parameters of generative model θ is built in

the standard supervised fashion with the limited amount of la-

beled data x

∈ X

θ = arg max

(

)



∈ X



(

)



; θ



(7)

Then, we perform E-step of Expectation-Maximization (EM)

technique by classifying the unlabeled data x

∈ X

with the naive

Bayes model

θ. The class of unlabeled data is determined by

estimating the highest probability of that the generative model

component generates the corresponding unlabeled data, which is

shown in Eq. (8) :

= arg max

P ( c

| x

;

θ ) =

P ( c

θ ) P ( x

| c

;

θ )

P ( x

θ )

(8)

As M-step of Expectation-Maximization (EM) technique, a new

naive Bayes classiﬁer is built by re-estimating the parameters

with the updated labeled dataset in Eq. (7) .

The parameters of classiﬁer

θ is iteratively improved by repeat-

ing above process of classifying the unlabeled data and rebuilding

the naive Bayes model based on the labeled data until it converges

to a stable classiﬁer and set of labels for the data. In fact, the con-

vergence condition is indicated by no change in the log probability

of full dataset X with label Y in Eq. (9) :

l( θ | X, Y ) = log ( P ( θ ) ) +



∈ X

log



P ( c

| θ ) P ( x | c

; θ )



∈ X

log P ( y

= c

| θ ) P ( x | y

= c

; θ ) (9)

Description of our approach

In this section, we describe our approach shown in Algorithm 1

as two steps: Firstly, the density-based parameters including least

data points MinPts and a radius Eps are determined by use of both

labeled and unlabeled data for each of classes. Next, the local clus-

ters are constructed by applying DBSCAN on the target dataset

with different parameter sets, and then the ﬁnal clustering result

is obtained by integrating these local clusters.

3.1. Determination of density-based parameter sets

For density-based clustering approaches, different set of param-

eters (least data points MinPts and a radius Eps ) can result in var-

ious clustering results. We assume that the each class of instances

are constructed in different size, shape and density, thus it is nec-

essary to deﬁne individual set of parameters for each cluster.

剩余12页未读，继续阅读

weixin_38696836

粉丝: 3
资源: 932

多密度信息驱动的自适应半监督聚类算法

自适应k均值聚类

基于多密度信息的自适应半监督聚类方法

自适应半监督聚类：多密度信息方法

改进的亲和力传播聚类

在空间中寻找结构：基于密度的空间聚类算法

聚类分析：数据挖掘与模式识别的应用

MATLAB聚类算法在社交媒体分析中的【先进策略】

【Python并行计算】：聚类算法大数据处理加速方案

推荐算法中的无监督学习与半监督学习技术

半监督vs无监督学习：对比分析与应用场景深度解读

最新资源