In clustering, the cost function that is commonly used involves calculating all-pairwise squared distances. In this paper, we formulate the cost function using mean squared error and show that this leads to more balanced clustering compared to centroid-based distance functions, like the sum of squared distances in k-means. The clustering method has been formulated as a cut-based approach, more intuitively called Squared cut (Scut). We introduce an algorithm for the problem which is faster than the existing one based on the Stirling approximation. Our algorithm is a sequential variant of a local search algorithm. We show by experiments that the proposed approach provides better overall optimization of both mean squared error and cluster balance compared to existing methods.
Citation: Mikko I. Malinen, Pasi Fränti. All-pairwise squared distances lead to more balanced clustering[J]. Applied Computing and Intelligence, 2023, 3(1): 93-115. doi: 10.3934/aci.2023006
[1] | Ye Shuang, Feng Qi . Integral inequalities of Hermite-Hadamard type for GA-F-convex functions. AIMS Mathematics, 2021, 6(9): 9582-9589. doi: 10.3934/math.2021557 |
[2] | Thongchai Botmart, Soubhagya Kumar Sahoo, Bibhakar Kodamasingh, Muhammad Amer Latif, Fahd Jarad, Artion Kashuri . Certain midpoint-type Fejér and Hermite-Hadamard inclusions involving fractional integrals with an exponential function in kernel. AIMS Mathematics, 2023, 8(3): 5616-5638. doi: 10.3934/math.2023283 |
[3] | Shuang-Shuang Zhou, Saima Rashid, Muhammad Aslam Noor, Khalida Inayat Noor, Farhat Safdar, Yu-Ming Chu . New Hermite-Hadamard type inequalities for exponentially convex functions and applications. AIMS Mathematics, 2020, 5(6): 6874-6901. doi: 10.3934/math.2020441 |
[4] | Yousaf Khurshid, Muhammad Adil Khan, Yu-Ming Chu . Conformable integral version of Hermite-Hadamard-Fejér inequalities via η-convex functions. AIMS Mathematics, 2020, 5(5): 5106-5120. doi: 10.3934/math.2020328 |
[5] | Muhammad Amer Latif, Mehmet Kunt, Sever Silvestru Dragomir, İmdat İşcan . Post-quantum trapezoid type inequalities. AIMS Mathematics, 2020, 5(4): 4011-4026. doi: 10.3934/math.2020258 |
[6] | Saad Ihsan Butt, Ahmet Ocak Akdemir, Muhammad Nadeem, Nabil Mlaiki, İşcan İmdat, Thabet Abdeljawad . (m,n)-Harmonically polynomial convex functions and some Hadamard type inequalities on the co-ordinates. AIMS Mathematics, 2021, 6(5): 4677-4690. doi: 10.3934/math.2021275 |
[7] | Wenbing Sun, Rui Xu . Some new Hermite-Hadamard type inequalities for generalized harmonically convex functions involving local fractional integrals. AIMS Mathematics, 2021, 6(10): 10679-10695. doi: 10.3934/math.2021620 |
[8] | Eze R. Nwaeze, Muhammad Adil Khan, Ali Ahmadian, Mohammad Nazir Ahmad, Ahmad Kamil Mahmood . Fractional inequalities of the Hermite–Hadamard type for m-polynomial convex and harmonically convex functions. AIMS Mathematics, 2021, 6(2): 1889-1904. doi: 10.3934/math.2021115 |
[9] | Sabila Ali, Shahid Mubeen, Rana Safdar Ali, Gauhar Rahman, Ahmed Morsy, Kottakkaran Sooppy Nisar, Sunil Dutt Purohit, M. Zakarya . Dynamical significance of generalized fractional integral inequalities via convexity. AIMS Mathematics, 2021, 6(9): 9705-9730. doi: 10.3934/math.2021565 |
[10] | Aqeel Ahmad Mughal, Deeba Afzal, Thabet Abdeljawad, Aiman Mukheimer, Imran Abbas Baloch . Refined estimates and generalization of some recent results with applications. AIMS Mathematics, 2021, 6(10): 10728-10741. doi: 10.3934/math.2021623 |
In clustering, the cost function that is commonly used involves calculating all-pairwise squared distances. In this paper, we formulate the cost function using mean squared error and show that this leads to more balanced clustering compared to centroid-based distance functions, like the sum of squared distances in k-means. The clustering method has been formulated as a cut-based approach, more intuitively called Squared cut (Scut). We introduce an algorithm for the problem which is faster than the existing one based on the Stirling approximation. Our algorithm is a sequential variant of a local search algorithm. We show by experiments that the proposed approach provides better overall optimization of both mean squared error and cluster balance compared to existing methods.
The radial addition K˜+L of star sets K and L can be defined by
ρ(K˜+L,⋅)=ρ(K,⋅)+ρ(L,⋅), |
where a star set is a compact set that is star-shaped at o and contains o and ρ(K,⋅) denotes the radial function of star set K. The radial function is defined by
ρ(K,u)=max{c≥0:cu∈K}, | (1.1) |
for u∈Sn−1, where Sn−1 denotes the surface of the unit ball centered at the origin. The initial study of the radial addition can be found in [1, p. 235]. K is called a star body if ρ(K,⋅) is positive and continuous, and let Sn denote the set of star bodies. The radial addition and volume are the basis and core of the dual Brunn-Minkowski theory (see, e.g., [2,3,4,5,6,7,8,9,10]). It is important that the dual Brunn-Minkowski theory can count among its successes the solution of the Busemann-Petty problem in [3,11,12,13,14]. Recently, it has turned to a study extending from Lp-dual Brunn-Minkowski theory to Orlicz dual Brunn-Minkowski theory. The Orlicz dual Brunn-Minkowski theory and its dual have attracted people's attention [15,16,17,18,19,20,21,22,23,24,25,26,27,28].
For K∈Sn and u∈Sn−1, the half chord of K in the direction u is defined by
d(K,u)=12(ρ(K,u)+ρ(K,−u)). |
If there exists a constant λ>0 such that d(K,u)=λd(L,u), for all u∈Sn−1, then star bodies K,L are said to have similar chord (see Gardner [1] or Schneider [29]). Lu [30] introduced the i-th chord integral of star bodies: For K∈Sn and 0≤i<n, the i-th chord integral of K, is denoted by Bi(K), is defined by
Bi(K)=1n∫Sn−1d(K,u)n−idS(u). | (1.2) |
Obviously, for i=0, Bi(K) becomes the chord integral B(K).
The main aim of the present article is to generalize the chord integrals to Orlicz space. We introduce a new affine geometric quantity which we shall call Orlicz mixed chord integrals. The fundamental notions and conclusions of the chord integral and related isoperimetric inequalities for the chord integral are extended to an Orlicz setting. The new inequalities in special cases yield the Lp-dual Minkowski and Lp-dual Brunn-Minkowski inequalities for the Lp-mixed chord integrals. The related concepts and inequalities of Lp-mixed chord integrals are derived. As extensions, Orlicz multiple mixed chord integrals and Orlicz-Aleksandrov-Fenchel inequality for the Orlicz multiple mixed chord integrals are also derived.
In Section 3, we introduce the following new notion of Orlicz chord addition of star bodies.
Orlicz chord addition Let K and L be star bodies, the Orlicz chord addition of K and L, is denoted by Kˇ+ϕL, is defined by
ϕ(d(K,u)d(Kˇ+ϕL,u),d(L,u)d(Kˇ+ϕL,u))=1, | (1.3) |
where u∈Sn−1, and ϕ∈Φ2, which is the set of convex functions ϕ:[0,∞)2→(0,∞) that are decreasing in each variable and satisfy ϕ(0,0)=∞ and ϕ(∞,1)=ϕ(1,∞)=1.
The particular instance of interest corresponds to using (1.3) with ϕ(x1,x2)=ϕ1(x1)+εϕ2(x2) for ε>0 and some ϕ1,ϕ2∈Φ, which are the sets of convex functions ϕ1,ϕ2:[0,∞)→(0,∞) that are decreasing and satisfy ϕ1(0)=ϕ2(0)=∞, ϕ1(∞)=ϕ2(∞)=0 and ϕ1(1)=ϕ2(1)=1.
In accordance with the spirit of Aleksandrov [31], Fenchel and Jessen's [32] introduction of mixed quermassintegrals, and introduction of Lutwak's [33] Lp-mixed quermassintegrals, we are based on the study of first-order variations of the chord integrals. In Section 4, we prove that the first order Orlicz variation of the mixed chord integral can be expressed as: For K,L∈Sn, ϕ1,ϕ2∈Φ, 0≤i<n and ε>0,
ddε|ε=0+Bi(Kˇ+ϕε⋅L)=(n−i)⋅1(ϕ1)′r(1)⋅Bϕ2,i(K,L), | (1.4) |
where (ϕ1)′r(1) denotes the value of the right derivative of convex function ϕ1 at point 1. In this first order variational equation (1.4), we find a new geometric quantity. Based on this, we extract the required geometric quantity, denoted by Bϕ,i(K,L) which we shall call Orlicz mixed chord integrals of K and L, as follows
Bϕ2,i(K,L)=1n−i⋅(ϕ1)′r(1)⋅ddε|ε=0+Bi(Kˇ+ϕε⋅L). | (1.5) |
We show also that the new affine geometric quantity has an integral representation as follows:
Bϕ,i(K,L)=1n∫Sn−1ϕ(d(L,u)d(K,u))d(K,u)n−idS(u). | (1.6) |
When ϕ(t)=t−p and p≥1, the new affine geometric quantity becomes a new Lp-mixed chord integrals of K and L, denoted by Bp,i(K,L), which as is in (2.7).
In Section 5, we establish an Orlicz Minkowski inequality for the mixed chord and Orlicz mixed chord integrals.
Orlicz Minkowski inequality for the Orlicz mixed chord integrals If K,L∈Sn, 0≤i<n and ϕ∈Φ, then
Bϕ,i(K,L)≥Bi(K)⋅ϕ((Bi(L)Bi(K))1/(n−i)). | (1.7) |
If ϕ is strictly convex, the equality holds if and only if K and L are similar chord.
When ϕ(t)=t−p and p≥1, (1.7) becomes a new Lp-Minkowski inequality (2.8) for the Lp-mixed chord integrals.
In Section 6, as an application, we establish an Orlicz Brunn-Minkowski inequality for the Orlicz chord additions and the mixed chord integrals:
Orlicz Brunn-Minkowski inequality for the Orlicz chord additions If K,L∈Sn, 0≤i<n and ϕ∈Φ2, then
1≥ϕ((Bi(K)Bi(Kˇ+ϕL))1/(n−i),(Bi(L)Bi(Kˇ+ϕL))1/(n−i)). | (1.8) |
If ϕ is strictly convex, the equality holds if and only if K and L are similar chord.
When ϕ(t)=t−p and p≥1, (1.8) becomes a new Lp-Brunn-Minkowski inequality (2.9) for the mixed chord integrals.
A new isoperimetric inequality for the chord integrals is given in Section 7. In Section 8, Orlicz multiple mixed chord integrals is introduced and Orlicz-Aleksandrov-Fenchel inequality for the Orlicz multiple mixed chord integrals is established.
The setting for this paper is n-dimensional Euclidean space Rn. A body in Rn is a compact set equal to the closure of its interior. For a compact set K⊂Rn, we write V(K) for the (n-dimensional) Lebesgue measure of K and call this the volume of K. Associated with a compact subset K of Rn which is star-shaped with respect to the origin and contains the origin, its radial function is ρ(K,⋅):Sn−1→[0,∞) is defined by
ρ(K,u)=max{λ≥0:λu∈K}. |
Note that the class (star sets) is closed under union, intersection, and intersection with subspace. The radial function is homogeneous of degree −1, that is (see e.g. [1]),
ρ(K,ru)=r−1ρ(K,u), |
for all u∈Sn−1 and r>0. Let ˜δ denote the radial Hausdorff metric, as follows: if K,L∈Sn, then
˜δ(K,L)=|ρ(K,u)−ρ(L,u)|∞. |
From the definition of the radial function, it follows immediately that for A∈GL(n) the radial function of the image AK={Ay:y∈K} of K is given by (see e.g. [29])
ρ(AK,x)=ρ(K,A−1x), | (2.1) |
for all x∈Rn.
For Ki∈Sn,i=1,…,m, define the real numbers RKi and rKi by
RKi=maxu∈Sn−1d(Ki,u),andrKi=minu∈Sn−1d(Ki,u). | (2.2) |
Obviously, 0<rKi<RKi, for all Ki∈Sn. Writing R=max{RKi} and r=min{rKi}, where i=1,…,m.
If K1,…,Kn∈Sn, the mixed chord integral of K1,…,Kn, is denoted by B(K1,…,Kn), is defined by (see [30])
B(K1,…,Kn)=1n∫Sn−1d(K1,u)⋯d(Kn,u)dS(u). |
If K1=⋯=Kn−i=K, Kn−i+1=⋯=Kn=L, the mixed chord integral B(K1,…,Kn) is written as Bi(K,L). If L=B (B is the unit ball centered at the origin), the mixed chord integral Bi(K,L)=Bi(K,B) is written as Bi(K) and called the i-th chord integral of K. Obviously, For K∈Sn and 0≤i<n, we have
Bi(K)=1n∫Sn−1d(K,u)n−idS(u). | (2.3) |
If K1=⋯=Kn−i−1=K, Kn−i=⋯=Kn−1=B and Kn=L, the mixed chord integral B(K,…,K⏟n−i−1,B,…,B⏟i,L) is written as Bi(K,L) and called the i-th mixed chord integral of K and L. For K,L∈Sn and 0≤i<n, it is easy to see that
Bi(K,L)=1n∫Sn−1d(K,u)n−i−1d(L,u)dS(u). | (2.4) |
This integral representation (2.4), together with the Hölder inequality, immediately give the Minkowski inequality for the i-th mixed chord integral: If K,L∈Sn and 0≤i<n, then
Bi(K,L)n−i≤Bi(K)n−i−1Bi(L), | (2.5) |
with equality if and only if K and L are similar chord.
Definition 2.1 (The Lp-chord addition) Let K,L∈Sn and p≥1, the Lp chord addition ˇ+p of star bodies K and L, is defined by
d(Kˇ+pL,u)−p=d(K,u)−p+d(L,u)−p, | (2.6) |
for u∈Sn−1.
Obviously, putting ϕ(x1,x2)=x−p1+x−p2 and p≥1 in (1.3), (1.3) becomes (2.6). The following result follows immediately from (2.6) with p≥1.
−npn−ilimε→0+Bi(Kˇ+pε⋅L)−Bi(L)ε=1n∫Sn−1d(K,u)n−i+pd(L,u)−pdS(u). |
Definition 2.2 (The Lp-mixed chord integrals) Let K,L∈Sn, 0≤i<n and p≥1, the Lp-mixed chord integral of star K and L, denoted by Bp,i(K,L), is defined by
Bp,i(K,L)=1n∫Sn−1d(K,u)n−i+pd(L,u)−pdS(u). | (2.7) |
Obviously, when K=L, the Lp-mixed chord integral Bp,i(K,K) becomes the i-th chord integral Bi(K). This integral representation (2.7), together with the Hölder inequality, immediately gives:
Proposition 2.3 If K,L∈Sn, 0≤i<n and p≥1, then
Bp,i(K,L)n−i≥Bi(K)n−i+pBi(L)−p, | (2.8) |
with equality if and only if K and L are similar chord.
Proposition 2.4 If K,L∈Sn, 0≤i<n and p≥1, then
Bi(Kˇ+pL)−p/(n−i)≥Bi(K)−p/(n−i)+Bi(L)−p/(n−i), | (2.9) |
with equality if and only if K and L are similar chord.
Proof From (2.6) and (2.7), it is easily seen that the Lp-chord integrals is linear with respect to the Lp-chord addition, and together with inequality (2.8), we have for p≥1
Bp,i(Q,Kˇ+pL)=Bp,i(Q,K)+Bp,i(Q,L)≥Bi(Q)(n−i+p)/(n−i)(Bi(K)−p/(n−i)+Bi(L)−p/(n−i)), |
with equality if and only if K and L are similar chord.
Take Kˇ+pL for Q, recall that Bp,i(Q,Q)=Bi(Q), inequality (2.9) follows easily.
Throughout this paper, the standard orthonormal basis for Rn will be {e1,…,en}. Let Φn, n∈N, denote the set of convex functions ϕ:[0,∞)n→(0,∞) that are strictly decreasing in each variable and satisfy ϕ(0)=∞ and ϕ(ej)=1, j=1,…,n. When n=1, we shall write Φ instead of Φ1. The left derivative and right derivative of a real-valued function f are denoted by (f)′l and (f)′r, respectively. We first define the Orlicz chord addition.
Definition 3.1 (The Orlicz chord addition) Let m≥2,ϕ∈Φm, Kj∈Sn and j=1,…,m, the Orlicz chord addition of K1,…,Km, is denoted by ˇ+ϕ(K1,…,Km), is defined by
d(ˇ+ϕ(K1,…,Km),u)=sup{λ>0:ϕ(d(K1,u)λ,…,d(Km,u)λ)≤1}, | (3.1) |
for u∈Sn−1. Equivalently, the Orlicz chord addition ˇ+ϕ(K1,…,Km) can be defined implicitly by
ϕ(d(K1,u)d(ˇ+ϕ(K1,…,Km),u),…,d(Km,u)d(ˇ+ϕ(K1,…,Km),u))=1, | (3.2) |
for all u∈Sn−1.
An important special case is obtained when
ϕ(x1,…,xm)=m∑j=1ϕj(xj), |
for some fixed ϕj∈Φ such that ϕ1(1)=⋯=ϕm(1)=1. We then write ˇ+ϕ(K1,…,Km)=K1ˇ+ϕ⋯ˇ+ϕKm. This means that K1ˇ+ϕ⋯ˇ+ϕKm is defined either by
d(K1ˇ+ϕ⋯ˇ+ϕKm,u)=sup{λ>0:m∑j=1ϕj(d(Kj,u)λ)≤1}, | (3.3) |
for all u∈Sn−1, or by the corresponding special case of (3.2).
Lemma 3.2 The Orlicz chord addition ˇ+ϕ:(Sn)m→Sn is monotonic.
Proof This follows immediately from (3.1).
Lemma 3.3 The Orlicz chord addition ˇ+ϕ:(Sn)m→Sn is GL(n) covariant.
Proof From (2.1), (3.1) and let A∈GL(n), we obtain
d(ˇ+ϕ(AK1,AK2…,AKm),u) |
=sup{λ>0:ϕ(d(AK1,u)λ,d(AK2,u)λ,…,d(AKm,u)λ)≤1}=sup{λ>0:ϕ(d(K1,A−1u)λ,d(K2,A−1u)λ,…,d(Km,A−1u)λ)≤1}=d(ˇ+ϕ(K1,…,Km),A−1u)=d(ˇ+ϕ(K1,…,Km),u). |
This shows Orlicz chord addition ˇ+ϕ is GL(n) covariant.
Lemma 3.4 Suppose K1,…,Km∈Sn. If ϕ∈Φ, then
ϕ(d(K1,u)t)+⋯+ϕ(d(Km,u)t)=1 |
if and only if
d(ˇ+ϕ(K1,…,Km),u)=t |
Proof This follows immediately from Definition 3.1.
Lemma 3.5 Suppose Km,…,Km∈Sn. If ϕ∈Φ, then
rϕ−1(1m)≤d(ˇ+ϕ(K1,…,Km),u)≤Rϕ−1(1m). |
Proof Suppose d(ˇ+ϕ(K1,…,Km),u)=t, from Lemma 3.4 and noting that ϕ is strictly deceasing on (0,∞), we have
1=ϕ(d(K1,u)t)+⋯+ϕ(d(Km,u)t)≤ϕ(rK1t)+⋯+ϕ(rKmt)=mϕ(rt). |
Noting that the inverse ϕ−1 is strictly deceasing on (0,∞), we obtain the lower bound for d(ˇ+ϕ(K1,…,Km),u):
t≥rϕ−1(1m). |
To obtain the upper estimate, observe the fact from the Lemma 3.4, together with the convexity and the fact ϕ is strictly deceasing on (0,∞), we have
1=ϕ(d(K1,u)t)+⋯+ϕ(d(Km,u)t)≥mϕ(d(K1,u)+⋯+d(Km,u)mt)≥mϕ(Rt). |
Then we obtain the upper estimate:
t≤Rϕ−1(1m). |
Lemma 3.6 The Orlicz chord addition ˇ+ϕ:(Sn)m→Sn is continuous.
Proof To see this, indeed, let Kij∈Sn, i∈N∪{0}, j=1,…,m, be such that Kij→K0j as i→∞. Let
d(ˇ+ϕ(Ki1,…,Kim),u)=ti. |
Then Lemma 3.5 shows
rijϕ−1(1m)≤ti≤Rijϕ−1(1m), |
where rij=min{rKij} and Rij=max{RKij}. Since Kij→K0j, we have RKij→RK0j<∞ and rKij→rK0j>0, and thus there exist a,b such that 0<a≤ti≤b<∞ for all i. To show that the bounded sequence {ti} converges to d(ˇ+ϕ(K01,…,K0m),u), we show that every convergent subsequence of {ti} converges to d(ˇ+ϕ(K01,…,K0m),u). Denote any subsequence of {ti} by {ti} as well, and suppose that for this subsequence, we have
ti→t∗. |
Obviously a≤t∗≤b. Noting that ϕ is a continuous function, we obtain
t∗→sup{t∗>0:ϕ(d(K01,u)t∗,…,d(K0m,u)t∗)≤1} |
=d(ˇ+ϕ(K01,…,K0m),u). |
Hence
d(ˇ+ϕ(Ki1,…,Kim),u)→d(ˇ+ϕ(K01,…,K0m),u) |
as i→∞.
This shows that the Orlicz chord addition ˇ+ϕ:(Sn)m→Sn is continuous.
Next, we define the Orlicz chord linear combination for the case m=2.
Definition 3.7 (The Orlicz chord linear combination) The Orlicz chord linear combination, denoted by ˇ+ϕ(K,L,α,β) for K,L∈Sn, and α,β≥0 (not both zero), is defined by
α⋅ϕ1(d(K,u)d(ˇ+ϕ(K,L,α,β),u))+β⋅ϕ2(d(L,u)d(ˇ+ϕ(K,L,α,β),u))=1, | (3.4) |
for ϕ1,ϕ2∈Φ and all u∈Sn−1.
We shall write Kˇ+ϕε⋅L instead of ˇ+ϕ(K,L,1,ε), for ε≥0 and assume throughout that this is defined by (3.1), if α=1,β=ε and ϕ∈Φ. We shall write Kˇ+ϕL instead of ˇ+ϕ(K,L,1,1) and call it the Orlicz chord addition of K and L.
In order to define Orlicz mixed chord integrals, we need the following Lemmas 4.1-4.4.
Lemma 4.1 Let ϕ∈Φ and ε>0. If K,L∈Sn, then Kˇ+ϕε⋅L∈Sn.
Proof Let u0∈Sn−1, and {ui}⊂Sn−1 be any subsequence such that ui→u0 as i→∞.
Let
d(Kˇ+ϕL,ui)=λi. |
Then Lemma 3.5 shows
rϕ−1(12)≤λi≤Rϕ−1(12), |
where R=max{RK,RL} and r=min{rK,rL}.
Since K,L∈Sn, we have 0<rK≤RK<∞ and 0<rL≤RL<∞, and thus there exist a,b such that 0<a≤λi≤b<∞ for all i. To show that the bounded sequence {λi} converges to d(Kˇ+ϕε⋅L,u0), we show that every convergent subsequence of {λi} converges to d(Kˇ+ϕε⋅L,u0). Denote any subsequence of {λi} by {λi} as well, and suppose that for this subsequence, we have
λi→λ0. |
Obviously a≤λ0≤b. From (3.4) and note that ϕ1,ϕ2 are continuous functions, so ϕ−11 is continuous, we obtain
λi→d(K,u0)ϕ−11(1−εϕ2(d(L,u0)λ0)) |
as i→∞. Hence
ϕ1(d(K,u0)λ0)+εϕ2(d(L,u0)λ0)=1. |
Therefore
λ0=d(Kˇ+ϕε⋅L,u0). |
That is
d(Kˇ+ϕε⋅L,ui)→d(Kˇ+ϕε⋅L,u0). |
as i→∞.
This shows that Kˇ+ϕε⋅L∈Sn.
Lemma 4.2 If K,L∈Sn, ε>0 and ϕ∈Φ, then
Kˇ+ϕε⋅L→K | (4.1) |
as ε→0+.
Proof This follows immediately from (3.4).
Lemma 4.3 If K,L∈Sn, 0≤i<n and ϕ1,ϕ2∈Φ, then
ddε|ε=0+d(Kˇ+ϕε⋅L,u)n−i=n−i(ϕ1)′r(1)⋅ϕ2(d(L,u)d(K,u))⋅d(K,u)n−i. | (4.2) |
Proof From (3.4), Lemma 4.2 and notice that ϕ−11, ϕ2 are continuous functions, we obtain for 0≤i<n
ddε|ε=0+d(Kˇ+ϕε⋅L,u)n−i |
=limε→0+(n−i)d(K,u)n−i−1(d(K,u)ϕ2(d(L,u)d(Kˇ+ϕε⋅L,u)))×limy→1−ϕ−11(y)−ϕ−11(1)y−1=n−i(ϕ1)′r(1)⋅ϕ2(d(L,u)d(K,u))⋅d(K,u)n−i, |
where
y=1−εϕ2(d(L,u)d(Kˇ+ϕε⋅L,u)), |
and note that y→1− as ε→0+.
Lemma 4.4 If ϕ∈Φ2, 0≤i<n and K,L∈Sn, then
(ϕ1)′r(1)n−i⋅ddε|ε=0+Bi(Kˇ+ϕε⋅L)=1n∫Sn−1ϕ2(d(L,u)d(K,u))⋅d(K,u)n−idS(u). | (4.3) |
Proof This follows immediately from (2.1) and Lemma 4.3.
Denoting by Bϕ,i(K,L), for any ϕ∈Φ and 0≤i<n, the integral on the right-hand side of (4.3) with ϕ2 replaced by ϕ, we see that either side of the equation (4.3) is equal to Bϕ2,i(K,L) and hence this new Orlicz mixed chord integrals Bϕ,i(K,L) has been born.
Definition 4.5 (The Orlicz mixed chord integral) For ϕ∈Φ and 0≤i<n, Orlicz mixed chord integral of star bodies K and L, Bϕ,i(K,L), is defined by
Bϕ,i(K,L)=:1n∫Sn−1ϕ(d(L,u)d(K,u))⋅d(K,u)n−idS(u). | (4.4) |
Lemma 4.6 If ϕ1,ϕ2∈Φ, 0≤i<n and K,L∈Sn, then
Bϕ2,i(K,L)=(ϕ1)′r(1)n−ilimε→0+Bi(Kˇ+ϕε⋅L)−Bi(K)ε. | (4.5) |
Proof This follows immediately from Lemma 4.4 and (4.4).
Lemma 4.7 If K,L∈Sn, ϕ∈Φ and any A∈SL(n), then for ε>0
A(Kˇ+ϕε⋅L)=(AK)ˇ+ϕε⋅(AL). | (4.6) |
Proof This follows immediately from (2.1) and (3.3).
We find easily that Bϕ,i(K,L) is invariant under simultaneous unimodular centro-affine transformation.
Lemma 4.8 If ϕ∈Φ, 0≤i<n and K,L∈Sn, then for A∈SL(n),
Bϕ,i(AK,AL)=Bϕ,i(K,L). | (4.7) |
Proof This follows immediately from Lemmas 4.6 and 4.7.
In this section, we will define a Borel measure in Sn−1, denoted by Bn,i(K,υ), which we shall call the chord measure of star body K.
Definition 5.1 (The chord measure) Let K∈Sn and 0≤i<n, the chord measure of star body K, denoted by Bn,i(K,υ), is defined by
dBn,i(K,υ)=1n⋅d(K,υ)n−iBi(K)dS(υ). | (5.1) |
Lemma 5.2 (Jensen's inequality) Let μ be a probability measure on a space X and g:X→I⊂R be a μ-integrable function, where I is a possibly infinite interval. If ψ:I→R is a convex function, then
∫Xψ(g(x))dμ(x)≥ψ(∫Xg(x)dμ(x)). | (5.2) |
If ψ is strictly convex, the equality holds if and only if g(x) is constant for μ-almost all x∈X (see [34, p. 165]).
Lemma 5.3 Suppose that ϕ:[0,∞)→(0,∞) is decreasing and convex with ϕ(0)=∞. If K,L∈Sn and 0≤i<n, then
1nBi(K)∫Sn−1ϕ(d(L,u)d(K,u))d(K,u)n−idS(u)≥ϕ((Bi(L)Bi(K))1/(n−i)). | (5.3) |
If ϕ is strictly convex, the equality holds if and only if K and L are similar chord.
Proof For K∈Sn−1, 0≤i<n and any u∈Sn−1, the chord measure d(K,u)n−inBi(K)dS(u) is a probability measure on Sn−1. Hence, from (2.4), (2.5), (5.1) and by using Jensen's inequality, and in view of ϕ is decreasing, we obtain
1nBi(K)∫Sn−1ϕ(d(L,u)d(K,u))d(K,u)n−idS(u) |
=∫Sn−1ϕ(d(L,u)d(K,u))dBn,i(K,u)≥ϕ(Bi(K,L)Bi(K))≥ϕ((Bi(L)Bi(K))1/(n−i)). |
Next, we discuss the equality in (5.3). If ϕ is strictly convex, suppose the equality holds in (5.3), form the equality necessary conditions of Jensen's inequality and (2.5), it follows that d(L,u)/d(K,u) is constant, and K and L are similar chord, respectively. This yields that there exists r>0 such that d(L,u)=rd(K,u), for all u∈Sn−1. On the other hand, suppose that K and L are similar chord, i.e. there exists λ>0 such that d(L,u)=λd(K,u) for all u∈Sn−1. Hence
1nBi(K)∫Sn−1ϕ(d(L,u)d(K,u))d(K,u)n−idS(u) |
=1nBi(K)∫Sn−1ϕ((Bi(L)Bi(K))1/(n−i))d(K,u)n−idS(u)=ϕ((Bi(L)Bi(K))1/(n−i)). |
This implies the equality in (5.3) holds.
Theorem 5.4 (Orlicz chord Minkowski inequality) If K,L∈Sn, 0≤i<n and ϕ∈Φ, then
Bϕ,i(K,L)≥Bi(K)⋅ϕ((Bi(L)Bi(K))1/(n−i)). | (5.4) |
If ϕ is strictly convex, the equality holds if and only if K and L are similar chord.
Proof This follows immediately from (4.4) and Lemma 5.3.
Corollary 5.5 If K,L∈Sn, 0≤i<n and p≥1, then
Bp,i(K,L)n−i≥Bi(K)n−i+pBi(L)−p, | (5.5) |
with equality if and only if K and L are similar chord.
Proof This follows immediately from Theorem 5.4 with ϕ1(t)=ϕ2(t)=t−p and p≥1.
Taking i=0 in (5.5), this yields Lp-Minkowski inequality: If K,L∈Sn and p≥1, then
Bp(K,L)n≥B(K)n+pB(L)−p, |
with equality if and only if K and L are similar chord.
Corollary 5.6 Let K,L∈M⊂Sn, 0≤i<n and ϕ∈Φ, and if either
Bϕ,i(Q,K)=Bϕ,i(Q,L),forallQ∈M | (5.6) |
or
Bϕ,i(K,Q)Bi(K)=Bϕ,i(L,Q)Bi(L),forallQ∈M, | (5.7) |
then K=L.
Proof Suppose (5.6) holds. Taking K for Q, then from (2.3), (4.4) and (5.3), we obtain
Bi(K)=Bϕ,i(K,L)≥Bi(K)ϕ((Bi(L)Bi(K))1/(n−i)) |
with equality if and only if K and L are similar chord. Hence
Bi(K)≤Bi(L), |
with equality if and only if K and L are similar chord. On the other hand, if taking L for Q, by similar arguments, we get Bi(K)≥Bi(L), with equality if and only if K and L are similar chord. Hence Bi(K)=Bi(L), and K and L are similar chord, it follows that K and L must be equal.
Suppose (5.7) holds. Taking L for Q, then from from (2.3), (4.4) and (5.3), we obtain
1=Bϕ,i(K,L)Bi(K)≥ϕ((Bi(L)Bi(K))1/(n−i)), |
with equality if and only if K and L are similar chord. Hence
Bi(K)≤Bi(L), |
with equality if and only if K and L are similar chord. On the other hand, if taking K for Q, by similar arguments, we get Bi(K)≥Bi(L), with equality if and only if K and L are similar chord. Hence Bi(K)=Bi(L), and K and L have similar chord, it follows that K and L must be equal.
When ϕ1(t)=ϕ2(t)=t−p and p≥1, Corollary 5.6 becomes the following result.
Corollary 5.7 Let K,L∈M⊂Sn, 0≤i<n and p≥1, and if either
Bp,i(K,Q)=Bp,i(L,Q),forallQ∈M |
or
Bp,i(K,Q)Bi(K)=Bp,i(L,Q)Bi(L),forallQ∈M, |
then K=L.
Lemma 6.1 If K,L∈Sn, 0≤i<n, and ϕ1,ϕ2∈Φ, then
Bi(Kˇ+ϕL)=Bϕ1,i(Kˇ+ϕL,K)+Bϕ2,i(Kˇ+ϕL,L). | (6.1) |
Proof From (3.1), (3.4) and (4.4), we have for Kˇ+ϕL=Q∈Sn
Bϕ1,i(Q,K)+Bϕ2,i(Q,L) |
=1n∫Sn−1ϕ(d(K,u)d(Q,u),d(L,u)d(Q,u))d(Q,u)n−idS(u) |
=Bi(Q). | (6.2) |
The completes the proof.
Lemma 6.2 Let K,L∈Sn, ε>0 and ϕ∈Φ.
(1) If K and L are similar chord, then K and Kˇ+ϕε⋅L are similar chord.
(2) If K and Kˇ+ϕε⋅L are similar chord, then K and L are similar chord.
Proof Suppose exist a constant λ>0 such that d(L,u)=λd(K,u), we have
ϕ(d(K,u)d(Kˇ+ϕε⋅L,u))+εϕ(λd(K,u)d(Kˇ+ϕε⋅L,u))=1. |
On the other hand, the exist unique constant δ>0 such that
ϕ(d(K,u)d(δK,u))+εϕ(λd(K,u)d(δK,u))=1, |
where δ satisfies that
ϕ(1δ)+εϕ(λδ)=1. |
This shows that d(Kˇ+ϕε⋅L,u)=δd(K,u).
Suppose exist a constant λ>0 such that d(Kˇ+ϕε⋅L,u)=λd(K,u). Then
ϕ(1λ)+εϕ(d(L,u)d(Kˇ+ϕε⋅L,u))=1. |
This shows that
d(L,u)d(Kˇ+ϕε⋅L,u) |
is a constant. This yields that Kˇ+ϕε⋅L and L are similar chord. Namely K and L are similar chord.
Theorem 6.3 (Orlicz chord Brunn-Minkowski inequality) If K,L∈Sn, 0≤i<n and ϕ∈Φ2, then
1≥ϕ((Bi(K)Bi(Kˇ+ϕL))1/(n−i),(Bi(L)Bi(Kˇ+ϕL))1/(n−i)). | (6.3) |
If ϕ is strictly convex, the equality holds if and only if K and L are similar chord.
Proof From (5.4) and Lemma 6.1, we have
Bi(Kˇ+ϕL)=Bϕ1,i(Kˇ+ϕL,K)+Bϕ2,i(Kˇ+ϕL,L)≥Bi(Kˇ+ϕL)(ϕ1((Bi(K)Bi(Kˇ+ϕL))1/(n−i))+ϕ2((Bi(L)kBi(Kˇ+ϕL))1/(n−i)))=Bi(Kˇ+ϕL)ϕ((Bi(K)Bi(Kˇ+ϕL))1/(n−i),(Bi(L)Bi(Kˇ+ϕL))1/(n−i)). |
This is just inequality (6.3). From the equality condition of (5.4) and Lemma 6.3, it yields that if ϕ is strictly convex, equality in (6.3) holds if and only if K and L are similar chord.
Corollary 6.4 If K,L∈Sn, 0≤i<n and p≥1, then
Bi(Kˇ+pL)−p/(n−i)≥Bi(K)−p/(n−i)+Bi(L)−p/(n−i), | (6.4) |
with equality if and only if K and L are similar chord.
Proof This follows immediately from Theorem 6.2 with ϕ(x1,x2)=x−p1+x−p2 and p≥1.
Taking i=0 in (6.4), this yields the Lp-Brunn-Minkowski inequality for the chord integrals. If K,L∈Sn and p≥1, then
B(Kˇ+pL)−p/n≥B(K)−p/n+B(L)−p/n, |
with equality if and only if K and L are similar chord.
As a application, in the section, we give a new isoperimetric inequality for chord integrals. As we all know, the isoperimetric inequality for convex bodies can be stated below (see e.g. [26], p. 318).
The isoperimetric inequality If K is convex body in Rn, then
(V(K)V(B))n−1≤(S(K)S(B))n, | (7.1) |
with equality if and only if K is an n-ball.
Here B is the unit ball centered at the origin, V(K) denotes the volume of K and S(K) is the surface area of K, defined by (see [26], p. 318)
S(K)=limε→0V(K+εB)−V(K)ε=nV1(K,B), |
where + the usual Minkowski sum. Here, the mixed volume of convex bodies K and L, V1(K,L), defined by (see e.g. [1])
V1(K,L)=1n∫Sn−1h(L,u)dS(K,u). | (7.2) |
Next, we give some new isoperimetric inequalities for mixed chord integrals by using the Orlicz chord Minkowski inequality established in Section 5.
Theorem 7.1 (The Lp-isoperimetric inequality for mixed chord integrals) If K∈Sn, 0≤i<n and p≥1, then
(˜Bp,i(K)S(B))n−i≥(Bi(K)V(B))n−i+p, | (7.3) |
with equality if and only if K is an n-ball, where ˜Bp,i(K)=nBp,i(K,B).
Proof Putting L=B, ϕ(t)=t−p and p≥1 in Orlicz chord Minkowski inequality (5.4)
Bp,i(K,B)Bi(K)≥(Bi(B)Bi(K))−p/(n−i). |
That is
(Bp,i(K,B)Bi(K))n−i≥(Bi(K)V(B))p. |
Hence
(nBp,i(K,B)S(B))n−i≥(Bi(K)V(B))n−i+p. |
From the equality of (5.4), we find that the equality in (7.3) holds if and only if K and B are similar chord. This yields that the equality in (7.3) holds if and only if K is an n-ball.
Theorem 7.2 (The isoperimetric inequality for the chord integrals) If K∈Sn, then
(˜B(K)S(B))n≥(B(K)V(B))n+1, | (7.4) |
with equality if and only if K is an n-ball, where ˜B(K)=nB1(K,B).
Proof This follows immediately from (7.3) with p=1 and i=0.
This is just a similar form of the classical isoperimetric inequality (7.1).
As extensions, in the Section, the Orlicz mixed chord integral of K and L, Bϕ(K,L), is generalized into Orlicz multiple mixed chord integral of (n+1) star bodies L1,K1,…,Kn. Further, we generalize the Orlicz-Minklowski inequality into Orlicz-Aleksandrov-Fenchel inequality for the Orlicz multiple mixed chord integrals.
Theorem 8.1 If L1,K1,…,Kn∈Sn and ϕ1,ϕ2∈Φ, then
ddε|ε=0+B(L1ˇ+ϕε⋅K1,K2,⋯,Kn)=1n(ϕ1)′r(1) |
×∫Sn−1ϕ2(d(K1,u)d(L1,u))d(L1,u)d(K2,u)⋯d(Kn,u)dS(u). | (8.1) |
Proof This may yield by using a generalized idea and method of proving Lemma 4.4. Here, we omit the details.
Obviously, (4.3) is a special case of (8.1). Moreover, from Theorem 8.1, we can find the following definition:
Definition 8.2 (Orlicz multiple mixed chord integrals) Let L1,K1,…,Kn∈Sn and ϕ∈Φ, the Orlicz multiple mixed chord integral of (n+1) star bodies L1,K1,…,Kn, is denoted by Bϕ(L1,K1,…,Kn), is defined by
Bϕ(L1,K1,…,Kn)=1n∫Sn−1ϕ(d(K1,u)d(L1,u))d(L1,u)d(K2,u)⋯d(Kn,u)dS(u). | (8.2) |
When L1=K1, Bϕ(L1,K1,…,Kn) becomes the well-known mixed chord integral B(K1,…,Kn). Obviously, for 0≤i<n, Bϕ,i(K,L) is also a special case of Bϕ(L1,K1,…,Kn).
Corollary 8.3 If L1,K1,…,Kn∈Sn and ϕ1,ϕ2∈Φ, then
Bϕ2(L1,K1,…,Kn)=(ϕ1)′r(1)⋅ddε|ε=0B(L1+ϕε⋅K1,K2,…,Kn). | (8.3) |
Proof This yields immediately from (8.1) and (8.2).
Similar to the proof of Theorem 5.4, we may establish an Orlicz-Aleksandrov-Fenchel inequality as follows:
Theorem 8.4 (Orlicz-Aleksandrov-Fenchel inequality for the Orlicz multiple mixed chord integrals) If L1,K1,…,Kn∈Sn, ϕ∈Φ and 1≤r≤n, then
Bϕ(L1,K1,K2,⋯,Kn)≥B(L1,K2,⋯,Kn)⋅ϕ(r∏i=1B(Ki…,Ki,Kr+1,…,Kn)1rB(L1,K2…,Kn)). | (8.4) |
If ϕ is strictly convex, equality holds if and only if L1,K1,…,Kr are all of similar chord.
Proof This yields immediately by using a generalized idea and method of proving Theorem 5.4. Here, we omit the details.
Obviously, the Orlicz-Minklowski inequality (5.4) is a special case of the Orlicz-Aleksandrov-Fenchel inequality (8.4). Moreover, when L1=K1, (8.4) becomes the following Aleksandrov-Fenchel inequality for the mixed chords.
Corollary 8.5 (Aleksandrov-Fenchel inequality for the mixed chord integrals) If K1,…,Kn∈Sn and 1≤r≤n, then
B(K1,⋯,Kn)≤r∏i=1B(Ki…,Ki,Kr+1,…,Kn)1r. | (8.5) |
with equality if and only if K1,…,Kr are all of similar chord.
Finally, it is worth mentioning: when ϕ(t)=t−p and p≥1, Bϕ(L1,K1,…,Kn) written as Bp(L1,K1,…,Kn) and call it Lp-multiple mixed chord integrals of (n+1) star bodies L1,K1,…,Kn. So, the new concept of Lp-multiple mixed chord integrals and Lp-Aleksandrov-Fenchel inequality for the Lp-multiple mixed chord integrals may be also derived. Here, we omit the details of all derivations.
Research is supported by National Natural Science Foundation of China (11371334, 10971205).
The author declares that no conflicts of interest in this paper.
[1] |
J. H. Ward Jr, Hierarchical grouping to optimize an objective function, J. Am. Stat. Assoc., 58 (1963), 236–244. https://doi.org/10.1080/01621459.1963.10500845 doi: 10.1080/01621459.1963.10500845
![]() |
[2] |
T. Kohonen, Median strings, Pattern Recogn. Lett., 3 (1985), 309–313. https://doi.org/10.1016/0167-8655(85)90061-3 doi: 10.1016/0167-8655(85)90061-3
![]() |
[3] | V. Hautamäki, P. Nykänen, P. Fränti, Time-series clustering by approximate prototypes, 19th International conference on pattern recognition, (2008), 1–4. IEEE. https://doi.org/10.1109/ICPR.2008.4761105 |
[4] |
P. Fränti, R. Mariescu-Istodor, Averaging gps segments: competition 2019, Pattern Recogn., 112 (2021), 107730. https://doi.org/10.1016/j.patcog.2020.107730 doi: 10.1016/j.patcog.2020.107730
![]() |
[5] | P. Fränti, S. Sieranoja, K. Wikström, T. Laatikainen, Clustering diagnoses from 58m patient visits in Finland 2015-2018, 2022. |
[6] | M. Fatemi, P. Fränti, Clustering nordic twitter users based on their connections, 2023. |
[7] |
M. I. Malinen, P. Fränti, Clustering by analytic functions, Inform. Sciences, 217 (2012), 31–38. https://doi.org/10.1016/j.ins.2012.06.018 doi: 10.1016/j.ins.2012.06.018
![]() |
[8] | M. I. Malinen, P. Fränti, Balanced k-means for clustering, in: Joint Int. Workshop on Structural, Syntactic, and Statistical Pattern Recognition (S+SSPR 2014), LNCS 8621, Joensuu, Finland, 2014. |
[9] |
D. Aloise, A. Deshpande, P. Hansen, P. Popat, NP-hardness of Euclidean sum-of-squares clustering, Mach. Learn., 75 (2009), 245–248. https://doi.org/10.1007/s10994-009-5103-0 doi: 10.1007/s10994-009-5103-0
![]() |
[10] |
M. Inaba, N. Katoh, H. Imai, Applications of Weighted Voronoi Diagrams and Randomization to Variance-Based k-Clustering, ACM symposium on computational geometry (SCG 1994), (1994), 332–339. https://doi.org/10.1145/177424.178042 doi: 10.1145/177424.178042
![]() |
[11] | J. MacQueen, Some methods of classification and analysis of multivariate observations, Berkeley Symp. Mathemat. Statist. Probab., 1 (1967), 281–297. |
[12] |
W. H. Equitz, A New Vector Quantization Clustering Algorithm, IEEE Trans. Acoust., Speech, Signal Processing, 37 (1989), 1568–1575. https://doi.org/10.1109/29.35395 doi: 10.1109/29.35395
![]() |
[13] |
P. Fränti, O. Virmajoki, V. Hautamäki, Fast agglomerative clustering using a k-nearest neighbor graph, IEEE T. Pattern Anal., 28 (2006), 1875–1881. https://doi.org/10.1109/TPAMI.2006.227 doi: 10.1109/TPAMI.2006.227
![]() |
[14] |
P. Fränti, O. Virmajoki, Iterative shrinking method for clustering problems, Pattern Recogn., 39 (2006), 761–765. https://doi.org/10.1016/j.patcog.2005.09.012 doi: 10.1016/j.patcog.2005.09.012
![]() |
[15] |
P. Fränti, Efficiency of random swap clustering, Journal of Big Data, 5 (2018), 1–29. https://doi.org/10.1186/s40537-018-0122-y doi: 10.1186/s40537-018-0122-y
![]() |
[16] | B. Fritzke, Breathing k-means, arXiv: 2006.15666. |
[17] | C. Baldassi, Recombinator-k-means:an evolutionary algorithm that exploits k-means++ for recombination, IEEE T. Evolut. Comput., 26 (2022), 991–1003. |
[18] |
A. P. Dempster, N. M. Laird, D. B. Rubin, Maximun likelihood from incomplete data via the EM algorithm, J. R. Stat. Soc. B, 39 (1977), 1–38. https://doi.org/10.1111/j.2517-6161.1977.tb01600.x doi: 10.1111/j.2517-6161.1977.tb01600.x
![]() |
[19] |
Q. Zhao, V. Hautamäki, I. Kärkkäinen, P. Fränti, Random swap EM algorithm for finite mixture models in image segmentation, IEEE International Conference on Image Processing (ICIP), (2009), 2397–2400. https://doi.org/10.1109/ICIP.2009.5414459 doi: 10.1109/ICIP.2009.5414459
![]() |
[20] |
J. Shi, J. Malik, Normalized cuts and image segmentation, IEEE T. Pattern Anal., 22 (2000), 888–905. https://doi.org/10.1109/34.868688 doi: 10.1109/34.868688
![]() |
[21] | C. H. Q. Ding, X. He, H. Zha, M. Gu, H. D. Simon, A min-max cut algorithm for graph partitioning and data clustering, IEEE International Conference on Data Mining (ICDM), (2001), 107–114. |
[22] |
M. I. Malinen, P. Fränti, K-means*: Clustering by gradual data transformation, Pattern Recogn., 47 (2014), 3376–3386. https://doi.org/10.1016/j.patcog.2014.03.034 doi: 10.1016/j.patcog.2014.03.034
![]() |
[23] | R. Nallusamy, K. Duraiswamy, R. Dhanalaksmi, P. Parthiban, Optimization of non-linear multiple traveling salesman problem using k-means clustering, shrink wrap algorithm and meta-heuristics, International Journal of Nonlinear Science, 9 (2010), 171–177. |
[24] |
R. Mariescu-Istodor, P. Fränti, Solving the large-scale tsp problem in 1 h: Santa claus challenge 2020, Front. Robot. AI, (2021), 1–20. https://doi.org/10.3389/frobt.2021.689908 doi: 10.3389/frobt.2021.689908
![]() |
[25] | D. W. Sambo, B. O. Yenke, A. Förster, P. Dayang, Optimized clustering algorithms for large wireless sensor networks: A review, Sensors, 19 (2019), 322. |
[26] | J. Singh, R. Kumar, A. K. Mishra, Clustering algorithms for wireless sensor networks: A review, International Conference on Computing for Sustainable Global Development (INDIACom), (2015), 637–642. |
[27] |
Y. Liao, H. Qi, W. Li, Load-Balanced Clustering Algorithm With Distributed Self-Organization for Wireless Sensor Networks, IEEE Sens. J., 13 (2013), 1498–1506. https://doi.org/10.1109/JSEN.2012.2227704 doi: 10.1109/JSEN.2012.2227704
![]() |
[28] | L. Yao, X. Cui, M. Wang, An energy-balanced clustering routing algorithm for wireless sensor networks, IEEE World Congress on Computer Science and Information Engineering, 3 (2009), 316–320. |
[29] | P. S. Bradley, K. P. Bennett, A. Demiriz, Constrained k-means clustering, Tech. rep., MSR-TR-2000-65, Microsoft Research, 2000. |
[30] |
S. Zhu, D. Wang, T. Li, Data clustering with size constraints, Knowledge-Based Syst., 23 (2010), 883–889. https://doi.org/10.1016/j.knosys.2010.06.003 doi: 10.1016/j.knosys.2010.06.003
![]() |
[31] |
A. Banerjee, J. Ghosh, Frequency sensitive competitive learning for balanced clustering on high-dimensional hyperspheres, IEEE Transactions on Neural Networks, 15 (2004), 702–719. https://doi.org/10.1109/TNN.2004.824416 doi: 10.1109/TNN.2004.824416
![]() |
[32] | C. T. Althoff, A. Ulges, A. Dengel, Balanced clustering for content-based image browsing, in: GI-Informatiktage 2011, Gesellschaft für Informatik e.V., 2011. |
[33] |
A. Banerjee, J. Ghosh, On scaling up balanced clustering algorithms, SIAM International Conference on Data Mining, (2002), 333–349. https://doi.org/10.1137/1.9781611972726.20 doi: 10.1137/1.9781611972726.20
![]() |
[34] | Y. Chen, Y. Zhang, X. Ji, Size regularized cut for data clustering, Advances in Neural Information Processing Systems, 2005. |
[35] |
Y. Kawahara, K. Nagano, Y. Okamoto, Submodular fractional programming for balanced clustering, Pattern Recogn. Lett., 32 (2011), 235–243. https://doi.org/10.1016/j.patrec.2010.08.008 doi: 10.1016/j.patrec.2010.08.008
![]() |
[36] |
G. Tzortzis, A. Likas, The minmax k-means clustering algorithm, Pattern Recogn., 47 (2014), 2505–2516. https://doi.org/10.1016/j.patcog.2014.01.015 doi: 10.1016/j.patcog.2014.01.015
![]() |
[37] |
W. Tang, Y. Yang, L. Zeng, Y. Zhan, Optimizing mse for clustering with balanced size constraints, Symmetry, 11 (2019), 338. https://doi.org/10.3390/sym11030338 doi: 10.3390/sym11030338
![]() |
[38] |
L. Hagen, A. B. Kahng, New spectrxal methods for ratio cut partitioning and clustering, IEEE T. Computer-Aided D., 11 (1992), 1074–1085. https://doi.org/10.1109/43.159993 doi: 10.1109/43.159993
![]() |
[39] | T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to algorithms (2nd ed.), MIT Press and McGraw-Hill, 2001. |
[40] |
M. X. Goemans, D. P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM, 42 (1995), 1115–1145. https://doi.org/10.1145/227683.227684 doi: 10.1145/227683.227684
![]() |
[41] |
S. Arora, S. Rao, U. Vazirani, Expander flows, geometric embeddings and graph partitioning, J. ACM, 56 (2009), 1–37. https://doi.org/10.1145/1502793.1502794 doi: 10.1145/1502793.1502794
![]() |
[42] |
U. von Luxburg, A tutorial on spectral clustering, Stat. Comput., 17 (2007), 395–416. https://doi.org/10.1007/s11222-007-9033-z doi: 10.1007/s11222-007-9033-z
![]() |
[43] | M. R. Garey, D. S. Johnson, Computers and intractability: A guide to the theory of NP-completeness, W. H. Freeman, 1979. |
[44] | T. D. Bie, N. Cristianini, Fast sdp relaxations of graph cut clustering, transduction, and other combinatorial problems, J. Mach. Learn. Res., 7 (2006), 1409–1436. |
[45] |
A. Frieze, M. Jerrum, Improved approximation algorithms for max-k-cut and max bisection, Algorithmica, 18 (1997), 67–81. https://doi.org/10.1007/BF02523688 doi: 10.1007/BF02523688
![]() |
[46] |
W. Zhu, C. Guo, A local search approximation algorithm for max-k-cut of graph and hypergraph, International Symposium on Parallel Architectures, Algorithms and Programming, (2011), 236–240. https://doi.org/10.1109/PAAP.2011.35 doi: 10.1109/PAAP.2011.35
![]() |
[47] |
A. V. Kel'manov, A. V. Pyatkin, On the complexity of some quadratic euclidean 2-clustering problems, Comput. Math. Math. Phys., 56 (2016), 491–497. https://doi.org/10.1134/S096554251603009X doi: 10.1134/S096554251603009X
![]() |
[48] |
L. J. Schulman, Clustering for edge-cost minimization, Ann. ACM Symp. on Theory of Computing (STOC), (2000), 547–555. https://doi.org/10.1145/335305.335373 doi: 10.1145/335305.335373
![]() |
[49] |
S. Sahni, T. Gonzalez, P-complete approximation problems, J. ACM, 23 (1976), 555–565. https://doi.org/10.1145/321958.321975 doi: 10.1145/321958.321975
![]() |
[50] |
W. F. de la Vega, M. Karpinski, C. Kenyon, Y. Rabani, Approximation schemes for clustering problems, ACM symposium on Theory of computing (STOC '03), (2003), 50–58. https://doi.org/10.1145/780542.780550 doi: 10.1145/780542.780550
![]() |
[51] |
N. Guttmann-Beck, R. Hassin, Approximation algorithms for min-sum p-clustering, Discrete Appl. Math., 89 (1998), 125–142. https://doi.org/10.1016/S0166-218X(98)00100-0 doi: 10.1016/S0166-218X(98)00100-0
![]() |
[52] | H. Späth, Cluster analysis algorithms for data reduction and classification of objects, Wiley, New York, 1980. |
[53] | P. Fränti, S. Sieranoja, Clustering datasets, University of Eastern Finland, 2020. Available from: http://cs.uef.fi/sipu/datasets/. |
[54] |
P. Fränti, M. Rezaei, Q. Zhao, Centroid index: Cluster level similarity measure, Pattern Recogn., 47 (2014), 3034–3045. https://doi.org/10.1016/j.patcog.2014.03.017 doi: 10.1016/j.patcog.2014.03.017
![]() |
[55] |
S. Sieranoja, P. Fränti, Fast and general density peaks clustering, Pattern Recogn. Lett., 128 (2019), 551–558. https://doi.org/10.1016/j.patrec.2019.10.019 doi: 10.1016/j.patrec.2019.10.019
![]() |
[56] |
P. Fränti, Genetic algorithm with deterministic crossover for vector quantization, Pattern Recogn. Lett., 21 (2000), 61–68. https://doi.org/10.1016/S0167-8655(99)00133-6 doi: 10.1016/S0167-8655(99)00133-6
![]() |
[57] | T. Cour, S. Yu, J. Shi, Normalized Cut Segmentation Code, 2004. |
1. | Zhen-Hang Yang, Feng Qi, Bivariate homogeneous functions of two parameters: monotonicity, convexity, comparisons, and functional inequalities, 2024, 0022247X, 129091, 10.1016/j.jmaa.2024.129091 |