1 GBSVM Granular-ball Support Vector Machine Shuyin Xia Xiaoyu Lian Guoyin Wang Xinbo Gao Jiancu Chen Xiaoli Peng

2025-04-28 0 0 3.22MB 15 页 10玖币

侵权投诉

GBSVM: Granular-ball Support Vector Machine

Shuyin Xia, Xiaoyu Lian, Guoyin Wang*, Xinbo Gao, Jiancu Chen*, Xiaoli Peng

Abstract—GBSVM (Granular-ball Support Vector Machine) is

a signiﬁcant attempt to construct a classiﬁer using the coarse-

to-ﬁne granularity of a granular-ball as input, rather than a

single data point. It is the ﬁrst classiﬁer whose input contains

no points. However, the existing model has some errors, and

its dual model has not been derived. As a result, the current

algorithm cannot be implemented or applied. To address these

problems, this paper has ﬁxed the errors of the original model

of the existing GBSVM, and derived its dual model. Fur-

thermore, a particle swarm optimization algorithm is designed

to solve the dual model. The sequential minimal optimization

algorithm is also carefully designed to solve the dual model.

The solution is faster and more stable than the particle swarm

optimization based version. The experimental results on the

UCI benchmark datasets demonstrate that GBSVM has good

robustness and efﬁciency. All codes have been released in the open

source library at http://www.cquptshuyinxia.com/GBSVM.html

or https://github.com/syxiaa/GBSVM.

Index Terms—granular computing, granular-ball, classiﬁer,

classiﬁcation, SVM.

I. INTRODUCTION

HUman cognition has the characteristic of global prece-

dence, i.e., from large to small, coarse to ﬁne [1]. Human

beings have the ability of granulating data and knowledge

into different granularity according to different tasks, and then

solve problems using the relation between these granularity.

Since Lin and Zadeh proposed granular computing in 1996,

more and more scholars began to study information granular

[2], [3], [4], which simulates human cognition to deal with

complexity problems [5], [6]. Granular computing advocates

observing and analyzing the same problem from different

granularity. The coarser the granularity, the more efﬁcient

the learning process and the more robust to noise; while

the ﬁner the granularity, the more details of things can be

reﬂected. Choosing different granularity according to differ-

ent application scenarios can more effectively solve practical

problems [7], [8], [9], [10]. Wang introduced the cognitive law

of “global precedence” into granular computing and proposed

multi-granularity cognitive computing [1], [11].

Based on multi-granularity cognitive computing, Xia and

Wang further proposed granular-ball computing by partitioning

the dataset into some hyper-balls with different sizes (i.e.,

different granularity), called granular-balls [8]. The reason

why a hyper-ball is used instead of other geometries is that

it has completely symmetrical geometric characteristics and a

simple representation, i.e., that it only contains two parameters

S. Xia, X. Lian, G. Wang, J. Chen, X. Pemg & X. Gao are with

the Chongqing Key Laboratory of Computational Intelligence, Key Labo-

ratory of Big Data Intelligent Computing, Key Laboratory of Cyberspace

Big Data Intelligent Security, Ministry of Education, Chongqing Uni-

versity of Posts and Telecommunications, 400065, Chongqing, China.

E-mail: xiasy@cqupt.edu.cn, 1258852995@qq.com, wanggy@cqupt.edu.cn,

gaoxb@cqupt.edu.cn, chenchen2153@163.com, 93334586@cqupt.edu.cn.

including the center and radius in any dimension. So, it is suit-

able for scaling up to high dimensional data. Other geometries

do not have this characteristic. To simulate the cognitive law of

“global precedence”, granular-balls are generated by splitting

the initial granular-ball of a whole data set from coarse to

ﬁne. As granular-balls adaptively have different sizes, they can

ﬁt various datasets with complex distribution. Instead of the

ﬁnest granularity of a data point, a granular-ball can describe

the coarse features of the covered samples. Different from the

traditional AI learning methods whose input representation is

the ﬁnest granularity of a point input, based on the granular-

ball representation, granular-ball computing needs to create

new computation models for various AI ﬁelds, such as classi-

ﬁcation, clustering, optimization, artiﬁcial neural networks and

others. As the number of coarse granular-balls is much smaller

than the ﬁnest data points, granular-ball computing is much

more efﬁcient than traditional AI computations; in addition,

as a granular-ball is coarse and not easily affected by noise

points, it is robust; furthermore, in comparison with a data

point, a granular-ball can represent a point set and describe an

equivalence class, it has better interpretability. In summary,

Xia and Wang ﬁnd that the cognitive law of “global prece-

dence” and granular-ball computing have good computation

performance in efﬁciency, robustness and interpretability at the

same time [8], [12]. These characteristics can be described in

Fig. 1, in the cognitive law of “global precedence”, the human

brain does not need to see the details or information of each

point when recognizing large “H” and large “T”; however,

existing convolutional neural networks need to ﬁrst convert

the image into a pixel matrix, the ﬁnest granularity, and then

calculate the contour information of large “H” and large “T”

based on the pixel matrix. Obviously, the former is efﬁcient.

In addition, “H” and “T” are seen ﬁrst, and then the “h” and

“t” that make up them. There are two “t”s in the left “H”,

which can be considered as noise, but it still does not affect

the overall appearance of “H”. Therefore, the cognitive law

is robust. Finally, human recognition is based on semantic

“point sets” such as “lines”, rather than the ﬁnest granularity

of “points” without any semantics. Therefore, the recognition

process is interpretable. As a “global precedence” cognitive

method, the characteristics of granular-ball computing and the

aforementioned cognition are completely consistent.

The origin of granular-ball computing was originally used

to solve the problem of traditional classiﬁers not being able

to achieve multi granularity learning. The existing classiﬁers

such as traditional SVM process data with the ﬁnest gran-

ularity, i.e., a sample point or pixel point, as in Fig. 2(a).

Consequently, those classiﬁers have the disadvantages of low

efﬁciency and low anti-noise ability [13], [14]. To address

this problem, Xia et al. proposed the granular-ball support

vector machine (GBSVM) using the granular-balls generated

arXiv:2210.03120v2 [cs.LG] 11 Feb 2024

Fig. 1. Human cognition “global precedence”.

(a) The existing classiﬁers (b) The granular-ball classiﬁers

Fig. 2. The comparison of the granular-ball classiﬁers and the existing

classiﬁers.

on the dataset as its input instead of the data points [8],

as shown in Fig. 2(b). As granular-ball computing has the

advantages of robustness, high efﬁciency and interpretability,

the GBSVM exhibits good performance in both efﬁciency and

robustness. Although existing GBSVM creates a non point

input model, the existing version has three disadvantages:

ﬁrstly, the existing GBSVM model has some minor errors;

secondly, the dual model of GBSVM and nonlinear GBSVM

model are not derived; thirdly, how to solute GBSVM is not

provided. The work in [28] is also developed based on the

wrong GBSVM, and there are some errors in its derived dual

model. The contributions of this paper are as follows:

1) The existing GBSVM model has an error that the

support vector is not contained in the constraint. We

have corrected it in the proposed model in this paper.

2) The dual model of GBSVM is derived. It has a com-

pletely consistent formulation with the SVM.

3) The granular-ball generation method in kernel space is

developed, so the nonlinear GBSVM model is designed.

4) A solution algorithm for the dual model using the par-

ticle swarm optimization (PSO) algorithm [29] and se-

quential minimal optimization (SMO) algorithm [30] are

designed. The experimental results on some benchmark

data sets demonstrate better performance of GBSVM in

processing classiﬁcation problems with label noise in

comparison with SVM.

The rest of this paper is organized as follows. We introduce

related works in Section II. The model and dual model of

GBSVM are presented in detail in Section III. Experimental

results and analysis are presented in Section IV. We present

our conclusion and future work in Section V.

II. RELATED WORK

A. Granular-ball Computing

In the original works about classiﬁcation and clustering

based on granular-ball computing, a granular-ball GB is

deﬁned as the following standard form: GBj={xi|i=

1,2, . . . , k}, and its center c=1

kPk

i=1 xi, where xiand

kdenote a sample in the granular-ball and the number of

samples in the granular-ball, respectively. The radius can be

obtained in many ways. Two main ways are the average

distance and maximum distance. The average distance is

r=1

kPk

i=1 ||xi−c||, i.e., the average distance between cto

the other samples in a granular-ball. The maximum distance

is r= max ||xi−c||, i.e., the maximum distance between

cto the other samples in the granular-ball. The granular-

balls generated with the average distance can ﬁt the data

distribution well and get a clearer decision boundary than that

with the maximum distance. The granular-balls generated with

the maximum distance can cover all samples in the sample

space than that with the average distance. The above deﬁnition

of a granular-ball apply to classiﬁcation and may differ in other

ﬁelds, such as optimization and graph representation [34], [33].

The granular-ball computing can be described as the following

model.

Fig. 3. Process of the granular-ball generation.

Given a dataset Dwith nsamples, xi∈D.GBj(j=

1,2, . . . , m)is the granular-ball generated on the dataset D,

where mdenotes the number of granular-balls [31]. The

optimization model is formulated as:

f(xi, ⃗α)−→ g(GBj,⃗

β),

s.t. min n

j=1 |GBj|+m+loss(GBj),

quality(GBj)≥T,

(1)

where | · | is the cardinality, i.e., the number of objects con-

tained in a set. The function fmeans the original traditional

learning methods that take points xas input, while function

gstands for the granular-ball learning methods that utilize

granular-balls GB as input. Overall, granular-ball computing

encompasses two aspects: the novel multi granularity repre-

sentations using granular-ball, and the novel computing modes

based on granular-ball representation. In the objective of the

constraints, the ﬁrst term indicates the sample coverage; the

higher the coverage, the better, and the less information loss.

The second term mrepresents the number of granular-balls.

The fewer the number of granular-balls, the better under the

constraint: the more efﬁcient and robust the calculation of

granular-balls. The third term loss(GBj)is used to optimize

the granular-ball quality in the cases where the point repre-

sentation is changed in the training process, such as in deep

neural networks; otherwise, in traditional learning tasks, such

as GBSVM, this term is not needed. In the constraints of the

constraints of (1), the quality of each granular-ball, i.e. purity,

should meet a threshold T. Only the parameter Tis introduced

in the constraints in the constraints of Model (1), and the

parameter can further be eliminated using also adaptive rules

[32]; in many other granular-ball methods, such as granular-

ball clustering, the parameter also does not exist [12]. So,

the optimization algorithm for granular-ball generation is very

adaptable. The granular-ball becomes ﬁner when the radius

rdecreases and coarser when rincreases. In classiﬁcation

problems, not all data points have to belong to a particular

granular-ball with guaranteed quality of each ball, which is

beneﬁcial for generating a clearer decision boundary in some

cases; in most other problems, such as granular-ball clustering,

the radius of a granular-ball is equal to the maximum distance

from the points inside it to its center so that granular-balls

can cover all data points [12]. In supervised tasks, such as

classiﬁcation, purity is used as one of the evaluation standards

to measure the quality of the granular-ball. The purity is equal

to the proportion of the majority of samples in a granular-ball

[8].

Fig. 3shows a heuristic solution strategy for (1). Taking

classiﬁcation as an example, the process of the granular-

ball generation is shown in Fig. 3. To simulate the “global

precedence” of human cognition, the whole dataset is regarded

as an initial granular-ball, whose purity is the worst and

can not describe the distribution of the dataset. When the

purity of a granular-ball is lower than the purity threshold,

the quality of this granular-ball does not meet the condition

and needs to continue being split from coarse to ﬁne until the

purities of its sub-granular-balls are no less than the purity

threshold. The higher the purity of the generated granular-

balls, the better the consistency with the data distribution of

the original dataset. Each granular-ball also has a label, which

is consistent with the label of the majority of samples in the

granular-ball. The process of the granular-ball generation is as

Fig. 3. As shown in Fig. 4(a), there are two classes, so the

initial granular-ball is split into two granular-balls using k-

means or k-division. As the purity of each granular-ball is not

high enough, the two granular-balls continue to be split. As

the splitting process continues, the purity of each granular-ball

increases, and the decision boundary becomes clear until the

purities of all granular-balls meet the stop condition as shown

in Fig. 4(c). Fig. 4(d) shows the ﬁnal granular-balls extracted

from Fig. 4(c). It is worth noting that the radius of each ball

in Fig. 4is the average of all points in the ball, so all sample

points are not fully covered.

In the granular-ball classiﬁer, the learning process includes

the granular generation and granular-ball computing learning.

Since the number of granular-balls can be considered almost

as a small constant, the time complexity of granular-ball

generation is equal to the time complexity of generating the

largest granular-ball among. 2-mean clustering or k-devision

[32] generally has a fast convergence rate, so it can be

considered an approximately linear algorithm. Since the size of

the data set containing the centers and radius of granular-balls

is very small, the regression process can be almost negligible.

Therefore, the time complexity of the granular-ball classiﬁer

is reduced to close to O(N), which is very low. It should

be noted that, the representation of granular-balls may not

necessarily use strict balls in some scenarios, but can be

approximated in some ways, such as using rectangles in the

granular-ball image processing [33] and using the boundary

points of balls in granular-ball evolutionary computation [34].

(a) (b)

Fig. 4. The splitting process of the granular-ball. (The purity threshold is

0.9, samples and granular-balls of two color represent two classes.) (a) The

granular-balls generated in the 2nd iteration. (b) The granular-balls generated

in the 3rd iteration. (c) The stable granular-balls. (d) The ﬁnal granular-balls

extracted from (c).

Although the theory of granular-ball computing has not

been proposed for a long time, a series of methods have been

developed to address problems such as efﬁciency, robustness,

and interpretability in various ﬁelds of artiﬁcial intelligence.

To address the low efﬁciency and hyper-parameter (i.e., the

neighborhood radius) optimization problem in neighborhood

rough set, The granular-ball neighborhood rough set (GBNRS)

is proposed by introducing granular-ball computing into the

neighborhood rough set [35]. GBNRS is the ﬁrst rough set

method that is parameter-free in processing continuous data.

Furthermore, a uniﬁed model called granular-ball rough set

(GBRS) is developed to address the conﬂicting problem in

equivalent class knowledge representation and continuous data

processing between Pawlak rough set and neighborhood rough

set [36]. GBRS exhibits a higher accuracy than both the

traditional neighborhood rough set and Pawlak rough set.

Granular-ball computing is also introduced into sampling

called granular-ball sampling (GBS), which is the ﬁrst sam-

pling method that can not only reduce the size of a data set but

also improve the data quality in noisy label classiﬁcation [37].

In short, granular-ball computing [12] has now been effectively

extended to various ﬁelds of artiﬁcial intelligence, developing

theoretical methods such as granular-ball clustering meth-

ods [38], granular-ball neural networks [33], and granular-

ball evolutionary computing [34], signiﬁcantly improving the

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

1GBSVM:Granular-ballSupportVectorMachineShuyinXia,XiaoyuLian,GuoyinWang*,XinboGao,JiancuChen*,XiaoliPengAbstract—GBSVM(Granular-ballSupportVectorMachine)isasignificantattempttoconstructaclassifierusingthecoarse-to-finegranularityofagranular-ballasinput,ratherthanasingledatapoint.Itisthefirstclassifi...

展开>> 收起<<

1 GBSVM Granular-ball Support Vector Machine Shuyin Xia Xiaoyu Lian Guoyin Wang Xinbo Gao Jiancu Chen Xiaoli Peng.pdf

共15页,预览3页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

1 GBSVM Granular-ball Support Vector Machine Shuyin Xia Xiaoyu Lian Guoyin Wang Xinbo Gao Jiancu Chen Xiaoli Peng

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: