设为首页
加入收藏
期刊导航
网站地图
首页
期刊
数学与物理
地球与环境
信息通讯
经济与管理
生命科学
工程技术
医药卫生
人文社科
化学与材料
会议
合作
新闻
我们
招聘
千人智库
我要投稿
办刊
期刊菜单
●领域
●编委
●投稿须知
●最新文章
●检索
●投稿
文章导航
●Abstract
●Full-Text PDF
●Full-Text HTML
●Full-Text ePUB
●Linked References
●How to Cite this Article
AdvancesinAppliedMathematics
应用数学进展
,2023,12(1),400-410
PublishedOnlineJanuary2023inHans.https://www.hanspub.org/journal/aam
https://doi.org/10.12677/aam.2023.121043
一个新的填充函数在优化核聚类中的应用
夏俊杨
浙江师范大学，数学与计算机科学学院，浙江金华
收稿日期：
2022
年
12
月
28
日；录用日期：
2023
年
1
月
21
日；发布日期：
2023
年
1
月
31
日
摘要
针对约束优化问题，本文提出一个新的单参数填充函数，并设计相应算法。然后将此填充函数应
用于对聚类问题中的权重优化，结合聚类模型的过程给出相应算法步骤，运用
Python
对数据集
进行聚类分析并得出权重参数。最后，实验结果表明该填充函数算法的可行性。
关键词
填充函数，权重优化，聚类
ANewFilledFunctionandthe
ApplicationinOptimizingKernel
ClusteringProblem
JunyangXia
CollegeofMathematicsandComputerScience,ZhejiangNormalUniversity,JinhuaZhejiang
Received:Dec.28
th
,2022;accepted:Jan.21
st
,2023;published:Jan.31
st
,2023
Abstract
Inthispaper,weproposeanewoneparameterfilledfunctionforconstrainedopti-
文章引用
:
夏俊杨
.
一个新的填充函数在优化核聚类中的应用
[J].
应用数学进展
,2023,12(1):
400-410.DOI:10.12677/aam.2023.121043
夏俊杨
mizationanddesignthecorrespondingalgorithm.Thenthisfilledfunctionisapplied
totheweightoptimizationofclusteringproblem,thecorrespondingalgorithmsteps
aregivenincombinationwiththeprocessofclusteringmodel,andPythonisused
toclusterthedatasetandobtaintheweightparameters.Finally,theexperimental
resultsshowthatthefilledfunctionalgorithmisfeasible.
Keywords
FilledFunction,WeightOptimization,Clustering
Copyright© 2023byauthor(s)andHansPublishersInc.
This work is licensed under theCreative Commons Attribution InternationalLicense (CCBY4.0).
http://creativecommons.org/licenses/by/4.0/
1.
引用
填充函数法是求解非线性全局优化问题的一种确定性算法，由西安交通大学葛仁溥
[1]
教授首
先提出，随后张连生教授等
[2–4]
对填充函数的定义进行了改进，不少学者又相继提出了双参数填
充函数法
[5]
、单参数填充函数法
[6,7]
和无参数填充函数法
[8].
在文献
[9]
中针对无
Lipschitz
连
续而在目标函数满足强制条件时，提出了一类新的单参数填充函数来解决一般无约束最优化问题
.
但在现实中，大多数的全局优化问题都有约束条件存在并且不一定满足强制性条件
.
在本文中避开
了强制性这个条件从而使得极小点可以在边界上达到
.
随后提出了一个新的单参数填充函数法，数
值实验结果表明该算法是有效可行的，并通过结合聚类模型的实例验证了该填充函数的实用性
.
2.
假设与定义
考虑如下不等式约束的全局优化问题
(P):
minf
(
x
)
,s.t.x
∈
S
=
{
x
∈
R
n
|
g
i
(
x
)
≤
0
,i
=1
,...,m
}
..
(1)
其中
f
(
x
)
,g
i
(
x
)
,i
=1
,...,m
:
R
n
→
R,
是连续可微函数
.
设
x
∗
k
为问题
(P)
的当前局部极小点，针对问题
(P)
给出填充函数所满足的定义如下
.
定义
1
[6]
函数
p
(
x,x
∗
k
,A
)
如果满足以下条件，则称它为
f
(
x
)
在局部极小点
x
∗
k
处的填充函
数
.
(1)
在
R
n
空间中，
x
∗
k
是
p
(
x,x
∗
k
,A
)
的一个严格局部极大点；
DOI:10.12677/aam.2023.121043401
应用数学进展
夏俊杨
(2)
对任意的
x
∈
S
1
∩
S
且
x
̸
=
x
∗
k
或
x
∈
R
n
\
S
有
∇
p
(
x,x
∗
k
,A
)
̸
=0
，这里
S
1
=
{
x
∈
R
n
|
f
(
x
)
≥
f
(
x
∗
k
)
,g
i
(
x
)
≤
0
,i
=1
,...,m
}
;
(3)
若
x
∗
k
不是全局极小点，那么
p
(
x,x
∗
k
,A
)
一定在
S
2
=
{
x
∈
S
|
f
(
x
)
<f
(
x
∗
k
)
,g
i
(
x
)
≤
0
,
i
=1
,...,m
上有局部极小点
.
以上定义的填充函数的意义为：对于带约束的最优化问题，首先要考虑的就是所求出来的点
是否可行
.
由
(2)
知，要找的点一定在可行域内；其次，用填充函数解决全局最优化问题，目的是
找到比当前局部极小点更好的点，由
(2)
知，要找的点一定不会再比当前局部极小点高的水平集上
得到
.
若
x
∗
k
是局部极小点但不是全局极小点，由
(1)
和
(3)
，则可以从
x
∗
k
的邻域中的任意一点出
发，用求带约束最优化问题的极小化方法极小化该填充函数，总能找到填充函数的局部极小点
x
∗
0
，
由
(3)
知，
f
(
x
∗
0
)
<f
(
x
∗
k
)
，再由
(2)
，对
x
∈
S
1
∩
S
且
x
̸
=
x
∗
k
或
x
∈
R
n
\
S
有
∇
p
(
x,x
∗
k
,A
)
̸
=0
，
得知
x
∗
0
∈
S
2
.
3.
介绍
基于定义
1
，本文构造如下填充函数：
p
(
x,x
∗
k
,A
)=
e
A
·
φ
(
f
(
x
)
−
f
(
x
∗
k
))
1+
∥
x
−
x
∗
k
∥
2
+
1
A
{
min
[0
,max
(
f
(
x
)
−
f
(
x
∗
k
)
,g
i
(
x
)
,i
=1
,
···
,m
)]
}
.
(2)
其中
φ
(
t
)=
{
1
,t
≥
0
,
0
,t<
0
.
(3)
这里
x
∗
k
是问题
(1)
的当前局部极小点，
A>
0
是参数
.
由以下定理易知函数
p
(
x,x
∗
k
,A
)
是满足定
义
1
的一个填充函数
.
定理
1
：
设
x
∗
k
是
f
(
x
)
的一个局部极小点，当
A>
0
时，
x
∗
k
是填充函数
p
(
x,x
∗
k
,A
)
的一个
严格局部极大点
.
证明
因为
x
∗
k
是
f
(
x
)
的一个局部极小点，存在它的一个领域
N
(
x
∗
k
,δ
)
,
(
δ>
0)
，对任意的
x
∈
N
(
x
∗
k
,δ
)
∩
S
且
x
̸
=
x
∗
k
或
x
∈
R
n
\
S
，有
f
(
x
)
≥
f
(
x
∗
k
)
.
于是
φ
(
x
)=1
.
则有
min
[0
,max
(
f
(
x
)
−
f
(
x
∗
k
)
,g
i
(
x
)
,i
=1
,
···
,m
)]=0
,
于是
p
(
x,x
∗
k
,A
)=
e
A
·
φ
(
f
(
x
)
−
f
(
x
∗
k
))
1+
∥
x
−
x
∗
k
∥
2
=
e
A
1+
∥
x
−
x
∗
k
∥
2
.
由于
A>
0
，得到
DOI:10.12677/aam.2023.121043402
应用数学进展
夏俊杨
e
A
1+
∥
x
−
x
∗
k
∥
2
<
1
<e
A
=
P
(
x
∗
k
,x
∗
k
,A
)
.
所以对任意的
x
∈
(
x
∗
k
,δ
)
S,x
̸
=
x
∗
k
，或
x
∈
R
n
\
S
,
有
P
(
x,x
∗
k
,A
)
<P
(
x
∗
k
,x
∗
k
,A
)
，故填充
函数
p
(
x,x
∗
k
,A
)
的一个严格局部极大点在
x
∗
k
处取得
.
定理
2
：
设
x
∗
k
是
f
(
x
)
的一个局部极小点，对任意的
A>
0
，
p
(
x,x
∗
k
,A
)
在
S
1
且
x
̸
=
x
∗
k
或
R
n
\
S
上有
∇
P
(
x,x
∗
k
,A
)
̸
=0
成立
.
证明
对任意的
x
∈
S
1
，且
x
̸
=
x
∗
k
或
R
n
\
S
有
min
[0
,max
(
f
(
x
)
−
f
(
x
∗
k
)
,g
i
(
x
)
,i
=1
,
···
,m
)]=0
.
此时
p
(
x,x
∗
k
,A
)=
e
A
·
φ
(
f
(
x
)
−
f
(
x
∗
k
))
1+
∥
x
−
x
∗
k
∥
2
=
e
A
1+
∥
x
−
x
∗
k
∥
2
,
从而
∇
p
(
x,x
∗
k
,A
)=
−
2
e
A
·
(
x
−
x
∗
k
)
(1+
∥
x
−
x
∗
k
∥
2
)
2
̸
=0
.
故对任意的
x
∈
S
1
，对任意
A>
0
且
x
̸
=
x
∗
k
或
R
n
\
S
，有
∇
P
(
x,x
∗
k
,A
)
̸
=0
.
定理
3
：
如果
x
∗
k
不是
f
(
x
)
的全局极小点，且
clintS
=
clS
，则当
A>
0
充分大时，填充函数
P
(
x,x
∗
k
,A
)
在
S
2
上一定存在局部极小点
x
∗
0
，其中
S
2
=
{
xϵS
|
f
(
x
)
<f
(
x
∗
k
)
,g
i
(
x
)
≤
0
,i
=1
,...,m
}
非空
.
证明
因为
x
∗
k
是
f
(
x
)
的局部极小点，不是
f
(
x
)
的全局极小点，故
S
2
̸
=
∅
,
存在
f
(
x
)
的另
一个局部极小点
x
∗
1
，使得
f
(
x
∗
1
)
<f
(
x
∗
k
)
,g
i
(
x
∗
1
)
≤
0
,i
=1
,...,m
.
由于
f
(
x
)
,g
i
(
x
)
,i
=1
,...,m
是连续函数，且
clintS
=
clS
，则一定存在
x
∗
2
∈
R
n
，使得
f
(
x
∗
2
)
<f
(
x
∗
k
)
，
g
i
(
x
∗
2
)
<
0
,i
=1
,...,m
，
从而
f
(
x
∗
2
)
−
f
(
x
∗
k
)
<
0
,
故
φ
[
f
(
x
∗
2
)
−
f
(
x
∗
k
)]=0
.max
(
f
(
x
∗
2
)
−
f
(
x
∗
k
)
,g
i
(
x
∗
2
)
,i
=1
,...,m
)
<
0
.
则
p
(
x
∗
2
,x
∗
k
,A
)=
e
A
·
φ
(
f
(
x
∗
2
)
−
f
(
x
∗
k
))
1+
∥
x
∗
2
−
x
∗
k
∥
2
+
1
A
{
min
[0
,max
(
f
(
x
∗
2
)
−
f
(
x
∗
k
)
,g
i
(
x
∗
2
)
,i
=1
,
···
,m
)]
}
=
1
1+
∥
x
∗
2
−
x
∗
k
∥
2
+
1
A
max
(
f
(
x
∗
2
)
−
f
(
x
∗
k
)
,g
i
(
x
∗
2
)
,i
=1
,
···
,m
)
.
另一方面，对任意的
x
∈
∂S
，至少存在一个指标
i
∈
{
1
,
···
,m
}
，使得
g
i
1
(
x
)=0
.
DOI:10.12677/aam.2023.121043403
应用数学进展
夏俊杨
(i)
x
∈
∂S
,
当
f
(
x
)
≥
f
(
x
∗
k
)
时
,
则
f
(
x
)
−
f
(
x
∗
k
)
≥
0
,
因此
,
min
[0
,max
(
f
(
x
)
−
f
(
x
∗
k
)
,g
i
(
x
)
,
)]=0
(ii)
x
∈
∂S
,
当
f
(
x
)
<f
(
x
∗
k
)
时
,
则
f
(
x
)
−
f
(
x
∗
k
)
<
0
,
因此
,
min
[0
,max
(
f
(
x
)
−
f
(
x
∗
k
)
,g
i
(
x
)
,
)]=0
综上
∀
x
∈
∂S
都有
min
[0
,max
(
f
(
x
)
−
f
(
x
∗
k
)
,g
i
(
x
)
,i
=1
,
···
,m
)]=0
.
所以
∀
x
∈
∂S
有
p
(
x,x
∗
k
,A
)=
e
A
·
φ
(
f
(
x
)
−
f
(
x
∗
k
))
1+
∥
x
−
x
∗
k
∥
2
+
1
A
·
0=
e
A
·
φ
(
f
(
x
)
−
f
(
x
∗
k
))
1+
∥
x
−
x
∗
k
∥
2
,
故当
A>
0
时，有
φ
[
f
(
x
)
−
f
(
x
∗
k
)]
≥
0
,
则有
e
A
·
φ
[
f
(
x
)
−
f
(
x
∗
k
)]
≥
1
.
所以，当
A
充分小时，对
∀
x
∈
∂S
，我们有
P
(
x
∗
2
,x
∗
k
,A
)
<
1
1+
∥
x
−
x
∗
k
∥
2
≤
P
(
x,x
∗
k
,A
)
.
因此存在一
点
x
∗
0
∈
S
\
∂S
使得
min
x
∈
S
P
(
x,x
∗
k
,A
)=
min
x
∈
S
\
∂S
P
(
x,x
∗
k
,A
)=
P
(
x
∗
0
,x
∗
k
,A
)
≤
P
(
x
∗
2
,x
∗
k
,A
)
,
由于
S
\
∂S
是开集，于是
A
充分小时存在一点
x
∗
0
∈
S
\
∂S
是
p
(
x,x
∗
k
,A
)
的局部极小点，又由定理
2
知
x
∗
0
∈
S
2
,
定理得证
.
综上所述，函数
p
(
x,x
∗
k
,A
)
符合填充函数的定义
.
4.
算法和数值实验
根据上述填充函数
p
(
x,x
∗
k
,A
)
的理论分析，提出以下关于问题（
1
）的填充函数算法：
步骤
1
初始步
.
选取初始点
x
1
∈
S
，选取
A
L
>
0
作为可接受的终止参数；令
A
=1
,k
=
1
,
0
<r<
1
,
一般取
r
=0
.
1
；
步骤
2
以
x
k
为初始点，运用已有的局部下降算法得到问题（
1
）的一个局部极小点，记作
x
∗
k
；
步骤
3
选取初始点列
{
x
i
k
|
i
=1
,
···
,m
}
，使得对某个
δ
k
>
0
，有
x
i
k
+1
∈
S
\
N
(
x
∗
k
,δ
k
)
；
步骤
4
令填充函数为
p
(
x,x
∗
k
,A
)
,i
=1
；
步骤
5
若
i
≤
m
，令
x
:=
x
i
k
+1
，转步骤
6
；否则，转步骤
8
；
步骤
6
若
f
(
x
)
<f
(
x
∗
k
)
，且
x
∈
S
，则以
x
为初始点，运用已有的局部下降算法得到问题
（
1
）的局部极小点
x
∗
k
+1
，使得
f
(
x
∗
k
+1
)
<f
(
x
∗
k
)
，令
x
∗
k
=
x
∗
k
+1
,k
=
k
+1
，转步骤
3
；否则，转步
骤
7
；
步骤
7
沿方向
D
=
−
p
(
x,x
∗
k
,A
)
，通过局部下降算法找到填充函数的一个新的点
x
，使得
p
(
x,x
∗
k
,A
)
能下降到一定程度使得
p
(
x,x
∗
k
+1
,A
)
<p
(
x,x
∗
k
,A
)
.
若在极小化过程中，
x
超出
S
的边
界，则令
i
=
i
+1
，转步骤
5
，否则，转步骤
6
；
步骤
8
令
A
=
r
·
A
.
若
A>A
L
，转步骤
4
；否则，算法终止，视
x
∗
k
为问题（
1
）的全局极
DOI:10.12677/aam.2023.121043404
应用数学进展
夏俊杨
小点
.
步骤
3
中对当前的局部极小点的初始点集选取方式为：令
m
=2
n
，并且初始点对称
.
例如，
当
n
=2
时，初始点为：
x
∗
k
+
δ
(1
,
0)
,x
∗
k
+
δ
(0
,
1)
,x
∗
k
−
δ
(1
,
0)
,x
∗
k
−
δ
(0
,
1)
,
这里
δ>
0
是预先给定的步长
.
由定理
3
可知：步骤
6
中若出现
f
(
x
)
<f
(
x
∗
k
)
，则
x
一定落在
S
2
中，由此以
x
为初始点极
小化目标函数
f
(
x
)
，得到比当前的局部极小值更小的局部极小值
.
由定理
1
得知若要使
p
(
x,x
∗
k
,A
)
的局部极小点在
x
∗
k
得到
,
则参数
A
应该充分小
.
在步骤
8
中，减小
A
的值
.
若对所有的初始点已进行计算且
A<A
L
，我们可以认为，根据现有的初始点，
找不到更小的局部极小点，所以把当前的局部极小点看作全局极小点，算法终止
.
选取文献
[8]
中的无参数填充函数算例，用
Python
对以上算法进行编程，以便于计算结果的
比较
.
取
m
=4
，记初始点为
x
1
，迭代次数为
k
，全局极小点为
x
∗
，全局极小值为
f
∗
.
算例
1
SimplifiedRosenbrock
′
s
函数
minf(x)=0.5(x
2
1
−
x
2
)
2
+(
x
1
−
1)
2
s.t.
−
3
≤
x
1
≤
3
,
−
3
≤
x
2
≤
3
.
已知该函数的全局极小点
x
∗
=(1
,
1)
T
，全局极小值
f
∗
=0
.
Table1.
Therunningresultofexample1
表
1.
算例
1
的运行结果
x
1
kx
∗
f
∗
本文
(
−
2
,
2)
T
2(1,1)
T
0
(
−
3
,
3)
T
2(0.99999999,0.99999998)
T
1.6264
×
10
−
16
文献
[8](-2,2)
T
5(1,1)
T
1
.
23
×
10
−
10
文献
[8](-3,3)
T
6(1,1)
T
0
算例
2
minf
(
x
)=
−
25(
x
1
−
2)
2
−
(
x
2
−
2)
2
−
(
x
3
−
1)
2
−
(
x
4
−
4)
2
−
(
x
5
−
1)
2
−
(
x
6
−
4)
2
s.t.(x
3
−
3)
2
+
x
4
≥
4
,
(
x
5
−
3)
2
+
x
6
≥
4
,x
1
−
3
x
2
≤
2
,
-x
1
+
x
2
≤
2
,x
1
+
x
2
≤
6
,x
1
+
x
2
≥
2
,
0
≤
x
1
,x
4
≤
6
,
0
≤
x
2
≤
8
,
1
≤
x
3
,x
5
≤
5
,
0
≤
x
6
≤
10
.
已知该函数的全局极小点
x
∗
=(5
,
1
,
5
,
0
,
5
,
10)
T
，全局最优值
f
(
x
∗
)=
−
310
.
DOI:10.12677/aam.2023.121043405
应用数学进展
夏俊杨
Table2.
Therunningresultofexample2
表
2.
算例
2
的运行结果
x
1
kx
∗
f
∗
本文
(4
.
9402
,
1
.
0598
,
4
.
8895
,
2
.
0000
,
5
.
0000
,
10
.
0000)
T
2
(4
.
9999
,
1
.
0000
,
5
.
0000
,
0
.
0000
,
4
.
9998
,
10
.
0000)
�
T
-309.9891
(5
.
0000
,
1
.
0000
,
5
.
0000
,
1
.
7864
,
5
.
0000
,
9
.
9999)
T
2
(5
.
0000
,
1
.
0000
,
5
.
0000
0
.
0000
,
4
.
9998
,
9
.
9998)
T
-297.9349
文献
[10]
(4
.
9402
,
1
.
0598
,
4
.
8895
2
.
0000
,
5
.
0000
,
10
.
0000)
T
2
(4
.
9680
,
1
.
0320
,
5
.
0000
1
.
9045
,
4
.
9136
,
10
.
0000)
T
-292.8629
文献
[10]
(5
.
0000
,
1
.
0000
,
5
.
0000
4
(5
.
0000
,
1
.
0000
,
5
.
0000
-297.9349
表
1
和表
2
数值算例结果表明本文所构造的单参数填充函数在求解不等式约束的优化问题时是
有效可行的，对比文献
[10]
中的结果，本文的填充函数法计算精度相对较高
.
在算例
2
的结果表
明：利用填充函数进行优化后，目标函数能找到全局极小点，与文献
[10]
相比，函数值更优
.
5.
填充函数在聚类中的应用
5.1.
聚类模型概述
聚类是指把相似的数据划分到一起，目标就是把相似的数据聚合到一起，聚类是机器学习中
一种无监督学习方法
.
支持向量机（
SVM
）是一种监督式学习方法，广泛应用于统计分类以及回归
分析中，通常是通过构造核映射将样本数据进行分类处理
.
本文的聚类模型表述如下
.
聚类过程中通常会遇到原始样本空间过于复杂从而使得聚类模型不精确的情况，为了克服这
一难题，本文首先建立一个合适的核映射，将原始样本中的线性不可分问题通过核映射的方式转
化为高维特征空间中的线性可分问题，使得之后在特征空间中的聚类更精确
.
给定一组数据
(
X
i
,y
i
)
,i
=1
,...,n
.
A
1
×
A
2
×···×
A
n
是数据在具有多种属性类型的
m
维
空间，某个区域内存在用来构造
K
类分类器的训练数据点对集
ˆ
S
=
<X
1
,y
1
>,<X
2
,y
2
>,
···
,<X
n
,y
n
>
，其中
X
i
=(
x
i
1
,x
i
2
,
···
,x
im
)
∈
A
1
×
A
2
×···×
A
m
(
i
=
1
,
···
,n
)
表示第
i
个训练数据点对在样本空间中的位置；
y
i
∈{
1
,
···
,K
}
表示第
i
个训练数据
点对的所属类别标号
.
在聚类、分类研究中，为了体现出每一个属性对分类预测的不同作用，
为了描述数据点
X
i
和
X
j
之间的差异，会设定一个带权重的“距离”度量，即：
D
(
X
i
,X
j
)=
(
m
k
=1
(
w
k
×
d
2
k
(
x
ik
,x
jk
)))
1
2
，其中
w
k
表示样本空间中的属性权重参数，为构造一个能拟合训练
数据点对集
ˆ
S
=
{
<X
1
,y
1
>,<X
2
,y
2
>,
···
,<X
n
,y
n
>
}
的最优分类器，可以按照每个数据点对
所属的类别来划分，从而得到多个样本数据点子集的集合
¯
S
=
S
1
,S
2
,
···
,S
K
，其中第
i
个数据点
子集
S
i
属于第
i
类；然后构造一个从样本空间到特征空间的映射
Φ:
A
1
×
A
2
×···×
A
m
→
R
H
，
DOI:10.12677/aam.2023.121043406
应用数学进展
夏俊杨
其中
R
H
是高维特征空间，样本空间中的线性不可分问题通过核映射转换为高维特征空间中的线
性可分问题来使得之后的聚类更精确
.
因此构造核映射应该尽量满足两个条件，即：特征空间中每
个子聚类内数据点之间的距离尽可能小，特征空间中不同聚类之间数据点之间的距离足够大
.
构造
这样一个映射后，使样本空间中属于第
i
类的数据点子集
S
i
的所有元素在特征空间的核映射下所
形成的像形成一个紧密的子聚类
.
为了满足上述使得特征空间中每个子聚类内数据点之间的距离尽可能小的目的，可以建立如
下的优化问题将特征空间的聚类优化问题和原始样本空间的分类问题联系起来
.
为寻找一组适合样
本空间中的数据点对集的属性权重组，我们提出了一种基于核映射的填充函数法来优化属性权重
.
优化属性权重向量
w
=(
w
1
,w
2
,
···
,w
m
)
T
可描述为如下的优化问题：
minF
(
w
)=
K
h
=1
Φ(
X
i
)
,
Φ(
X
j
)
ϵF
h
D
F
(Φ(
X
i
)
,
Φ(
X
j
))
2
=
K
h
=1
X
i
,X
j
ϵS
h
2
−
2
e
m
k
=1
(
w
k
·
d
2
k
(
x
ik
,x
jk
))
2
σ
2
,
s.t.
m
k
=1
w
k
≤
m,
0
≤
w
k
≤
1
,
(
k
=1
,
2
,
···
,m
)
.
(4)
其中，
F
(
w
)
表示同一个聚类块内
,
像向量最大限度地接近以保证数据点尽可能地接近聚类中心
.
F
为特征空间的映射集，
F
h
为映射集第
h
个子聚类
.
Φ(
X
i
)
,
Φ(
X
j
)
是第
h
个子聚类的两个像向量
.
为了满足上述使得特征空间中每个子聚类数据点之间的距离尽可能大的目的，可以建立如下
的优化问题将特征空间的聚类优化问题和原始样本空间的分类问题联系起来
.
maxG
(
w
)=
F
h
̸
=
F
r
Φ(
X
i
)
∈
F
h
,
Φ(
X
j
)
∈
F
r
D
F
(Φ(
X
i
)
,
Φ(
X
j
))
2
=
S
h
̸
=
S
r
X
i
∈
S
h
,X
j
∈
S
r
2
−
2
e
−
m
k
=1
(
w
k
·
d
2
k
(
x
ik
,x
jk
))
2
σ
2
,
s.t.
m
k
=1
w
k
≤
m,
0
≤
w
k
≤
1
,
(
k
=1
,
2
,
···
,m
)
.
上式中，
Φ(
X
i
)
和
Φ(
X
j
)
分别是特征空间中第
h
个子聚类
F
h
(
h
=1
,
·
,K
)
和第
r
个子聚类
F
r
(
r
=1
,
···
,K
)
的两个像向量
.
σ
表示高斯核函数的宽度，本文用固定核宽度表示
.
d
k
(
x
ik
,x
jk
)
根据第
k
个属性的类型决定其具体定义式
.
如果第
k
个属性是无序类别属性，则定义为
d
k
(
x
ik
,x
jk
)=
{
0
,x
ij
=
x
jk
,
1
,x
ik
̸
=
x
jk
.
如果第
k
个属性是有序类别属性，则定义为
d
k
(
x
ik
,x
jk
)=
|
x
ik
−
x
jk
|
.
一般设定
m
k
=1
w
k
≤
m,
0
≤
w
k
≤
1(
k
=1
,
···
,m
)
是为了将权重归一化
.
DOI:10.12677/aam.2023.121043407
应用数学进展
夏俊杨
为了找到更优配置的属性权重向量，使建立在加权后的“距离”度量下的分类器的分类效果
更佳，可构造
F
(
W
)
和
G
(
W
)
的一个最小化混合目标函数：
minE
(
W,λ
)=
λ
·
F
(
W
)
−
(1
−
λ
)
·
G
(
W
)
s.t.
m
k
=1
w
k
≤
m,
0
≤
w
k
≤
1
,
(
k
=1
,
2
,
···
,m
)
.
(5)
5.2.
用填充函数法求解聚类模型
根据上节填充函数
P
(
x,x
∗
,A
)
的理论依据，提出了求解上述优化问题
(4)
的算法
.
步骤
1
初始步
.
选取初始点
w
1
∈
S
，其中
S
是问题
(4
）中
w
k
的取值范围
.
选取
A
L
>
0
作
为终止参数；令
A
=1
,k
=1
,
0
<r<
1
,
一般取
r
=0
.
1
；
步骤
2
以
w
k
为初始点，应用梯度下降算法求得问题
(4)
的一个局部极小点，记作
w
∗
k
；
步骤
3
选取初始点列
{
w
i
k
|
i
=1
,
2
,
···
,m
}
，使得对某个
δ
k
>
0
，有
w
i
k
+1
∈
S
\
N
(
w
∗
k
,δ
k
)
；
步骤
4
令填充函数为
p
(
w,w
∗
k
,A
)
，
i
=1
；
步骤
5
若
i
≤
m
，令
w
:=
w
i
k
+1
，转步骤
6
；否则，转步骤
8
；
步骤
6
若
F
(
w
)
<F
(
w
∗
k
)
，且
w
∈
S
，则以
w
为初始点，应用梯度下降算法求问题
(4)
的局
部极小点
w
∗
k
+1
，使得
F
(
w
∗
k
+1
)
<F
(
w
∗
k
)
，令
w
∗
k
=
w
∗
k
+1
，
k
=
k
+1
，转步骤
3
；否则，转步骤
7
；
步骤
7
沿方向
D
=
−
p
(
w,w
∗
k
,A
)
，使用梯度下降算法找到填充函数的一个新的点
w
，使得
p
(
w,w
∗
k
,A
)
能下降到一定程度使得
p
(
w,w
∗
k
+1
,A
)
<p
(
w,w
∗
k
,A
)
.
若在极小化过程中，
w
超出
S
的
边界，则令
i
=
i
+1
，转步骤
5
，否则，转步骤
6
；
步骤
8
令
A
=
r
·
A
.
若
A>A
L
，转步骤
4
；否则，算法终止，视
w
∗
k
为问题
(4)
的全局极
小点
.
步骤
3
中的初始点集选取为：
m
=2
n
，对当前的局部极小点，假设初始点是对称的
.
例如，
当
n
=4
时，初始点为：
w
∗
k
+
α
(1
,
0
,
0
,
0)
T
,x
∗
k
+
α
(0
,
1
,
0
,
0)
T
,x
∗
k
−
α
(1
,
0
,
0
,
0)
T
,x
∗
k
−
α
(0
,
1
,
0
,
0)
T
,...,
这里
α>
0
是预先给定的步长
.
对于步
6
，我们首先比较
F
(
w
)
与
F
(
w
∗
k
)
的大小，若
F
(
w
)
<F
(
w
∗
k
))
直接进入极小化目标函
数阶段，不需要在该点处极小化填充函数，用
Python
编码上述算法
,
选取不同的初始点和步长代
入算法中，代码运行得到最终结果后发现当选取适当的初始点和步长时，得到的最小值为全局最
优解
.
5.3.
模型结果的比较和分析
通过对文献
[11]
中鸢尾花数据进行聚类分析，已知有四个属性共同决定鸢尾花类别时，为了
使得在同一聚类中的像向量距离最小，在不同聚类中的像向量距离最大，即使得聚类块更紧密，
DOI:10.12677/aam.2023.121043408
应用数学进展
夏俊杨
通过填充函数优化混合目标函数的极小值得到的权重向量
.
图
1
表示未用填充函数进行优化时得到
的函数值
.
图
1
表示在运用填充函数对上述问题进行优化后得出的最优值
.
Figure1.
Objectivefunctionvalues
图
1.
目标函数值
通过以上过程可以看出当
W
=(0
.
34294512
,
0
.
13697411
,
0
.
06632191
,
0
.
45375887)
T
时得到图
1
的最优权重参数，此时目标函数值为
15000.
图
1
在未用填充函数法对目标函数优化情况下得到
的函数值为
20000.
由此可以看出利用填充函数后得到的优化效果更好
.
6.
总结
本文提出了一类单参数填充函数，新设计的填充函数算法解决了不等式约束
[12]
的优化问题，
由于不需要考虑强制性条件的情况，并且运用填充函数进行优化时可以使得原目标函数跳出当前
局部极小点，找到全局极小点，因此该方法更具有精确性
.
通过引入基于核映射的属性权重自适应优化模型，结合填充函数法进行求解，通过分析虹膜
数据集来证实了算法在聚类问题中的可用性
.
参考文献
[1]Ge,R.P.(1990)TheFilledFunctionTransformationsforConstrainedGlobalOptimization.
Ap-
pliedMathematics andComputation
,
39
, 1-20.https://doi.org/10.1016/0096-3003(90)90118-M
[2]
张连生
.
求解全局优化的填充函数法的进展
[C]//
中国运筹学会
.2001
年全国数学规划及运筹
研讨会论文集
.
贵阳
:
贵州大学学报编辑部
,2001:154-156.
[3]
王伟祥
,
尚有林
,
张连生
.
约束全局优化问题的一个单参数填充函数方法
[J].
工程数学学报
,
2008,25(5):795-803.
DOI:10.12677/aam.2023.121043409
应用数学进展
夏俊杨
[4]
朱文兴
.
一类不依赖于局部极小解个数的填充函数法
[J],
统计科学与数学
,2002,22(4):
406-413.
[5]
孔敏
.
一类改进的非光滑规划的填充函数法
[J],
统计科学与数学
,2004,20(4):149-154.
[6]
钟以维
,
徐应涛
,
张莹
.
用填充函数法改进的人脸识别算法
[J].
计算机技术与发展
,2009,19(8):
78-81.
[7]Wang,W.X.,Shang,Y.L.andZhang,L.S.(2007)AFilledFunctionMethodforGlobalOpti-
mizationProblem.
OperationsResearchTransactions
,
11
,43-50.
[8]
吴波
,
高岳林
.
全局优化问题的一个无参数填充函数算法
[J].
数学的实践与认识
,2017,47(4):
170-174.
[9]Zhang,Y.,Zhang,L.S. and Xu,Y.T. (2010) AOne-Parameter Filled Function for Nonsmooth
GlobalOptimizationandItsApplication.
JournalofSystemsScienceandComplexity
,
23
,
1195-1209.https://doi.org/10.1007/s11424-010-7199-5
[10]
赵德芬
,
王薇
.
一类求解约束全局优化问题的填充函数
[J].
运筹学学报
,2010,14(2):119-126.
[11]
陈新泉
.
一种基于核映射的自适应优化配置属性权重组的方法
[J].
数值计算与计算机应用
,
2008,29(2):105-118.
[12]
陈佳利
,
张莹
,
王胜刚
,
谢笑盈
.
一个新的填充函数及其在数据拟合问题中的应用
[J].
运筹学学
报
,2021,25(1):81-88.
DOI:10.12677/aam.2023.121043410
应用数学进展
