基于Dempster-Shafer理论的k-Nearest Neighbor分类规则
需积分: 14 120 浏览量
更新于2024-09-09
1
收藏 973KB PDF 举报
k-Nearest Neighbor Classification
k-Nearest Neighbor（k-NN）分类是机器学习领域中的一种常用分类算法。该算法的基本思想是在训练数据集中找到与待分类样本最相似的k个邻居，然后根据这些邻居的类别信息来确定待分类样本的类别。
在传统的k-NN算法中，通常使用投票机制或距离加权机制来确定待分类样本的类别。然而，这些方法存在一些缺陷，例如不能处理不确定性和距离拒绝问题。为了解决这些问题，本文提出了一种基于Dempster-Shafer理论的k-NN分类方法。
在该方法中，每个邻居被视为一个证据，支持某些关于待分类样本类别的假设。证据的度量是根据两个向量之间的距离定义的。然后，使用Dempster的组合规则将k个邻居的证据组合起来，从而确定待分类样本的类别。
该方法提供了一个全局的解决方案来处理不确定性和距离拒绝问题，使得分类结果更加可靠。此外，该方法也可以处理不完美的训练数据问题，例如训练数据中的类别信息不确定或不完整。
在实验中，该方法与传统的投票和距离加权k-NN方法进行了比较，结果表明该方法在多个模拟和实际数据集上的分类准确率都优于传统方法。
Dempster-Shafer理论是处理不确定性和不完美信息的一种数学工具。该理论基于证据理论，提供了一种组合证据的方法，以便处理不确定性和不完美信息。在机器学习领域中，Dempster-Shafer理论被广泛应用于处理不确定性和不完美信息的问题。
在k-NN分类中，Dempster-Shafer理论可以用来处理不确定性和不完美信息。例如，在训练数据集中，某些样本的类别信息可能不确定或不完整，可以使用Dempster-Shafer理论来处理这些不确定性。
此外，Dempster-Shafer理论也可以用来处理距离拒绝问题。在传统的k-NN算法中，距离拒绝问题是指待分类样本与训练数据集中某些样本的距离太大，无法确定其类别。使用Dempster-Shafer理论，可以将这些距离拒绝样本视为不确定性，然后使用组合规则来确定其类别。
本文提出了一种基于Dempster-Shafer理论的k-NN分类方法，该方法可以处理不确定性和距离拒绝问题，提高分类准确率。该方法在机器学习领域中具有广泛的应用前景。
804
IEEE
TRANSACTIONS
ON
SYST6MS. MAN, AND CYBERNETICS,
VOL
25. NO.
5,
MAY
1995
A
k-Nearest Neighbor Classification
Rule Based
on
Dempster-Shafer Theory
Thierry
Denceux
Abstract-In
this paper, the problem of classifying an unseen
pattern on the basis of its nearest neighbors in a recorded data set
is addressed from the point of view
of
Dempster-Shafer theory.
Each neighbor
of
a sample
to
be classified is considered as an item
of
evidence that supports certain hypotheses regarding the class
membership
of
that pattern. The degree
of
support is defined as
a function of the distance between the two vectors. The evidence
of the
k
nearest neighbors is then pooled by means of Dempster's
rule of combination. This approach provides a global treatment
of
such issues as ambiguity and distance rejection, and imperfect
knowledge regarding the class membership
of
training patterns.
The effectiveness of this classification scheme as compared to the
voting and distance-weighted
k-NN
procedures is demonstrated
using several sets of simulated and real-world data.
I.
INTRODUCTION
N
classification problems, complete statistical knowledge
I regarding the conditional density functions of each class is
rarely available, which precludes application of the optimal
Bayes classification procedure. When no evidence supports
one form of the density functions rather than another,
a
good
solution is often
to
build up a collection of correctly classified
samples, called the
training set,
and to classify each new
pattern using the evidence of nearby sample observation. One
such non-parametric procedure has been introduced by Fix
and Hodges [ll], and has since become well-known in the
Pattem Recognition literature as the voting k-nearest neighbor
(k-NN)
rule. According to this rule, an unclassified sample
is assigned to the class represented by
a
majority of its
k
nearest neighbors in the training set. Cover and Hart
[4]
have
provided a statistical justification of this procedure by showing
that, as the number
N
of samples and
k
both tend to infinity
in
such a manner that
k/N
i
0.
the error rate of the
IC-
NN
rule approaches the optimal Bayes error rate. Beyond
this remarkable property, the
k-NN
rule owes much of its
popularity in the Pattem Recognition community to its good
performance in practical applications. However, in the finite
sample case, the voting
k-NN
rule is not guaranteed to be
the optimal way of using the information contained in the
neighborhood of unclassified patterns. This is the reason why
the improvement of this rule has remained an active research
topic in the past
40
years.
The main drawback of the voting
k:-NN
rule is that it
implicitly assumes the
k
nearest neighbors of
a
data point
:c
Manuscript received September 23, 1993; revised July
17,
1994. This
work
was
partially supported by EEC funded Esprit Project 6757 EMS
(Environmental Monitoring System).
The author
is
at the Universitk de Technologie de Compibgne,
U.R.A.
CNRS
817
Heudiasyc,
BP
649 F-60206 Compibgne cedex, France.
IEEE Log
Number
9409222.
to be contained in
a
region of relatively small volume,
so
that
sufficiently good resolution in the estimates of the different
conditional densities can be obtained. In practice, however,
the distance between
II:
and one of its closest neighbors is not
always negligible, and can even become very large outside
the regions of high density. This has several consequences.
First, it can be questioned whether
it
is still reasonable in
that case to give all the neighbors an equal weight in the
decision, regardless of their distances to the point
IC
to be
classified. In fact, given the
k
nearest neighbors
~('1.
.
.
. .
:I;(')
of
:I:.
and
d').
. . . .
d'")
the corresponding distances arranged
in increasing order, it is intuitively appealing to give the label
of
x(~) a greater importance than to the label of
z(J)
whenever
d'j
<
d(3).
Dudani
[
101
has proposed
to
assign to the ith
nearest neighbor
x:(~)
a weight
w(')
defined as:
The unknown pattem
IC
is then assigned
to
the class for
which the weights of the representatives among the
k
nearest
neighbors sum to the greatest value. This rule was shown by
Dudani to be admissible, Le. to yield lower error rates than
those obtained using the voting
k-NN
procedure for at least
one particular data set. However, several researchers, repeating
Dudani's experiments, reached less optimistic conclusions
[
11,
[16], [6]. In particular, Baily and Jain [l] showed that the
distance-weighted
k-NN
rule
is
not necessarily better than
the majority rule for small sample size if ties are broken in
a
judicious manner. These authors also showed that,
in
the
infinite sample case
(N
+
s),
the error rate of the traditional
unweighted
k-NN
rule is better than that of any weighted
k-
NN
rule. However, Macleod et al. [15] presented arguments
showing that this conclusion may not apply if the training set
is finite. They
also
proposed a simple extension of Dudani's
rule allowing for
a
more effective use of the kth neighbor in
the classification.
Apart from this discussion, it can also be argued that, be-
cause the weights are constrained to span the interval
[O,
l], the
distance-weighted
k-NN
procedure can still give considerable
importance to observations that are very dissimilar to the
pattem to be classified. This represents
a
serious drawback
when all the classes cannot be assumed to be represented
in the training set,
as
is often the case in some application
areas as target recognition in noncooperative environments
[5] or diagnostic problems [9]. In such situations, it may
be wise to consider that
a
point that is far away from any
0018-9472/95$04.00
0
1995
IEEE
下载后可阅读完整内容，剩余9页未读，立即下载
2016-03-06 上传
2019-10-18 上传
2021-02-21 上传
2021-05-29 上传
2021-02-10 上传
2022-09-21 上传
2022-07-13 上传
2021-02-15 上传
greatzy3214
- 粉丝: 0
- 资源: 19
我的内容管理
展开
最新资源
- JHU荣誉单变量微积分课程教案介绍
- Naruto爱好者必备CLI测试应用
- Android应用显示Ignaz-Taschner-Gymnasium取消课程概览
- ASP学生信息档案管理系统毕业设计及完整源码
- Java商城源码解析：酒店管理系统快速开发指南
- 构建可解析文本框：.NET 3.5中实现文本解析与验证
- Java语言打造任天堂红白机模拟器—nes4j解析
- 基于Hadoop和Hive的网络流量分析工具介绍
- Unity实现帝国象棋：从游戏到复刻
- WordPress文档嵌入插件：无需浏览器插件即可上传和显示文档
- Android开源项目精选：优秀项目篇
- 黑色设计商务酷站模板 - 网站构建新选择
- Rollup插件去除JS文件横幅：横扫许可证头
- AngularDart中Hammock服务的使用与REST API集成
- 开源AVR编程器：高效、低成本的微控制器编程解决方案
- Anya Keller 图片组合的开发部署记录
