KNN分类器andNEC分类器资源-CSDN文库

共3个文件

m：2个

pdf：1个

neighborhood

5星 · 超过95%的资源需积分: 10 56 浏览量 2010-05-04 22:10:52 上传评论 2 收藏 230KB RAR 举报

资源推荐

资源详情

资源评论

收起资源包目录

KNN and neighborhood classifier.rar （3个子文件）

neighborhood classifier

neighborhood classifiers.pdf 279KB

KNN.m 2KB

NEC.m 2KB

UNCORRECTED

PROOF

Neighborhood classiﬁers

Qinghua Hu

, Daren Yu, Zongxia Xie

Harbin Institute of Technology, Harbin 150001, People’s Republic of China

Abstract

K nearest neighbor classiﬁer (K-NN) is widely discussed and applied in pattern recognition and machine learning, however, as a

similar lazy classiﬁer using local information for recognizing a new test, neighborhood classiﬁer, few literatures are reported on. In this

paper, we introduce neighborhood rough set model as a uniform framework to understand and implement neighborhood classiﬁers. This

algorithm integrates attribute reduction technique with classiﬁcation learning. We study the inﬂuence of the three norms on attribute

reduction and classiﬁcation, and compare neighborhood classiﬁer with KNN, CART and SVM. The experimental results show that

neighborhood-based feature selection algorithm is able to delete most of the redundant and irrelevant features. The classiﬁcation accu-

racies based on neighborhood classiﬁer is superior to K-NN, CART in original feature spaces and reduced feature subspaces, and a little

weaker than SVM.

Keywords: Metric space; Neighborhood; Rough set; Reduction; Classiﬁer; Norm

18 1. Introduction

19 Giving a set of samples U, described with some input

20 variables C (also called condition attributes, feature) and

21 an output D (decision), the task of classiﬁcation learning

22 is to construct a mapping from the condition to the deci-

23 sion labels based on the set of training samples. One of

24 the most popular learni ng and classiﬁcation techniques is

25 the nearest neighbor search, introduced by Fix and Hodges

26 (1951). It has been proven to be a simple and yet powerful

27 recognition algorithm. In 1967, Cover and Hart (1967)

28 showed, under some con tinuity assumptions on the under-

29 lying distributions, that the asymptotic error rate of the 1-

30 NN rule is bounded from above by twice the Bayes error

31 (the error of the best possible rule). What is more, a key

32 feature of this decision rule is that it performs remarkably

33 well considering that no explicit knowledge of the underly-

34 ing distributions of the data is used. Furthermore, a simple

35generalization of this method, called K-NN-rule, in which a

36new pattern is classiﬁed into the class with the most mem-

37bers present among the K nearest neighbors, can be used to

38obtain good estimates of the Bayes error and its probability

39of error asymptotically approaches the Bayes error (Duda

40& Hart, 1973). However, K-NN classiﬁers require comput-

41ing all the distances between the training set and test sam-

42ples, it is time-consuming if the available samples are of

43very great size. Besides, when the number of prototypes

44in the training set is not large enough, the K-NN rule is

45no longer optimal. This problem becomes more relevant

46when having few prototypes compared to the intrinsic

47dimensionality of the feature space. After half century, a

48wide variety of algorithms have been developed to deal

49with these problems (Anil, 2006; Fu, Chan, & Cheung,

502000; Fukunaga & Narendra, 1975; Hart, 1968; Kuncheva

51& Lakhmi, 1999; Kushilevitz, Ostrovsky, & Rabani, 2000;

52Lindenbaum, Markovitch, & Rusakov, 2004; Short &

53Fukunaga, 1981; Vidal, 1986; Wilson & Martinez, 2000;

54Zhang, Yan, & Chen, 2004; Zhou, Yan, & Chen, 2006).

55From another viewpoint, some classiﬁcation algorithms

56based on neighborhood were propo sed, where a ne w sam-

57ple is associated wi th a neighborhood, rather than some

doi:10.1016/j.eswa.2006.10.043

Corresponding author. Tel.: +86 451 86413241 252; fax: +86 451

86413241 221.

E-mail address: huqinghua@hcms.hit.edu.cn (Q. Hu).

www.elsevier.com/locate/eswa

Expert Systems with Applications xxx (2006) xxx–xxx

Expert Systems

with Applications

ESWA 1881 No. of Pages 11, Model 5+

1 December 2006 Disk Used

ARTICLE IN PRESS

Please cite this article in press as: Hu, Q. et al., Neighborhood classiﬁers, Expert Systems with Applications (2006), doi:10.1016/

j.eswa.2006.10.043

UNCORRECTED PROOF

58 nearest neighbors. Owen developed a classiﬁer which uses

59 information from all data points in a neighborhood to clas-

60 sify the point at the center of the neighborhood (Owen,

61 1984). The neighborhood-based classiﬁer is shown to out-

62 perform linear discriminant analysis on some LANDSAT

63 data. Salzberg (1991) proposed a family of learning algo-

64 rithms based on nested generalized exemplars (NGE),

65 where an exemplar is a single training ex ample, and gener-

66 alized exemplars is an axis-parallel hyperrectangle that may

67 cover several training examples. Once the generalized

68 exemplars are learned, a test example can be classiﬁed by

69 computing the Euclidean distance between the example

70 and each of the generalized exemplars. If an example is

71 contained in a generalized exemplar, the distance to that

72 generalized exemplar is zero. The class of the nearest gen-

73 eralized exemplar is output as the predicted class of the test

74 example. Wettschereck and Dieterich (1995) compared

75 NGE with K-NN algorithms, and found that in most cases,

76 K-NN outperforms NGE. Then some improved version of

77 NGE, called NONGE, BNGE and OBNGE, was devel-

78 oped, where NONGE disallows overlapping rectangles

79 while retaining nested rectangles and the same search pro-

80 cedure is uniformly superior to NGE, while OBNGE is a

81 batch algorithm that incorporates an improved search

82 algorithm and disallows nested rectangles (but still permits

83 overlapping rectangles) and is only superior to NGE in one

84 domain and worse in two; BNGE is a batch version of

85 NONGE that is very eﬃcient and requires no user tuning

86 of parameters. They also pointed out that further research

87 is needed to develop an NGE-like algorithm that can be

88 robust in situations where axis-parallel hyperrectangles

89 are inappropriate. Intuitively, the concept of neighborhood

90 should be such that the neighbors are as close to a sample

91 as possible but also, the neighbors should lie as homoge-

92 neously around that sample as possible. Sanchez, Pla,

93 and Ferri (1997) showed that the geometrical placement

94 can become much more impor tant than the actual dis-

95 tances to appropriately characterize a sample by its neigh-

96 borhood. As the nearest neighborhood takes into account

97 the ﬁrst property only, the nearest neighbors may not be

98 placed symmetrically around the sample if the neighbor-

99 hood in the training set is not spatially homogeneous. In

100 fact, it has been shown that the use of local distance mea-

101 sures can signiﬁcantly improve the behavior of the classiﬁer

102 in the case of a ﬁnite sample size. They proposed to make

103 use of some alternative neighborhood deﬁnitions, obtain-

104 ing the surrounding neighborhood (SN) samples, the

105 neighbors of a sample will be considered not only in terms

106 of proximity but also in terms of their spatial dist ribution

107 with respect to that sample. More recently, Wang (2006)

108 showed a nonparametric technique for pattern recognition,

109 named neighborhood counting (NC), where he used neigh-

110 borhoods of data points measure the similarity between

111 two data points. Considering all neighborhoods that cover

112 both data points, he proposed using the number of such

113 neighborhoods as a generic measure of similarity. How-

114 ever, most of the work is focused on 2-norm neighborhood,

115few researches compare the inﬂuence bringing by diﬀerent

116norms, such as 1-norm and inﬁnite-norm. What is more,

117there is no uniform framework to understand, analyze

118and compare these algorithms.

119In fact, neighborhoods an d neighborhood relations are

120a class of important concepts in topology. Lin (1988,

1211997) pointed out that neighborhood spaces are more gen-

122eral topological spaces than equivalence spaces a nd intro-

123duced neighborhood relation into rough set methodology,

124which has shown to be a powerful tool to attribute reduc-

125tion, feature selection, rule extraction and reasoni ng with

126uncertainty (Hu, Yu, & Xie, 2006; Hu, Yu, Xie, & Liu,

1272006; Jensen & Shen, 2004; Swiniarski & Skowron, 2003).

128Yao (1998) and Wu and Zhang (2002) discussed the prop-

129erties of neighborhood approximation spaces. However,

130few applications of the model were reported these years.

131In this paper, we wi ll review the basic concepts on neigh-

132borhood and neighborhood rough sets an d show some

133properties of the model. And then we will use the model

134to build a uniform theoretic framework for neighbor-

135hood-based classiﬁers. This framework integrates feature

136selection with classiﬁer construction, and class iﬁes a test

137sample in the selected subspaces based on the majority

138class in the neighborhood of the test sample. The proposed

139technique combines the advantages of feature subset selec-

140tion and neighborhood-based classiﬁcation. It is conceptu-

141ally simple and is straightforward to implement. Some

142experimental analysis is conducted on UCI data sets. Three

143kinds of norms, 1-norm, 2-norm and inﬁnite-norm, are

144tried. The results show that the proposed classiﬁcation sys-

145tems outperform the popular CART Learning algorithm

146and K-NN classiﬁer, and a little weaker than SVM for

147the three norms.

148The remainder of the paper is organized as follows. The

149basic concepts on neighborhood rough set models are

150shown in Section 2. The neighborhood classiﬁer algorithm

151is introduc ed in Section 3 . Section 4 presents the experi-

152mental analysis. Then the conclusion is given in Se ction 5 .

1532. Neighborhood-based rough set model

154Formally, the structural data for classiﬁcation learning

155

can be written as a turple IS = hU ,A,V,fi, where U is the

156nonempty set of samples {x

,...,x

}, called a universe

157or sample space, A is the nonempty set of variables (also

158called as features, inputs, attributes) {a

,...,a

} to char-

159acterize the samples, V

is the value domain of attribute a;

160and f is an information function, f: U · A ! V. More spe-

161cially, hU,A,V,fi is also called a decision table if

162A = C [ D, where C is the set of condition attributes, D

163

is the output, also called decision.

164Deﬁnition 1. Given arbitrary x

2 U and B  C, the neigh-

165borhood d

)ofx

in the subspace B is deﬁned as

ðx

Þ¼fx

2 U ; D

ðx

; x

Þ 6 dg;

167167

2 Q. Hu et al. / Expert Systems with Applications xxx (2006) xxx–xxx

ESWA 1881 No. of Pages 11, Model 5+

1 December 2006 Disk Used

ARTICLE IN PRESS

Please cite this article in press as: Hu, Q. et al., Neighborhood classiﬁers, Expert Systems with Applications (2006), doi:10.1016/

j.eswa.2006.10.043

UNCORRECTED

PROOF

168 where D is a metric function. " x

2 U, it satisﬁes

169 (1) D(x

) P 0;

170 (2) D(x

) = 0, if and only if x

= x

;

171 (3) D(x

)=D(x

);

172 (4) D(x

) 6 D(x

)+D(x

173

174 There are three metric functions that are widely used.

175 Consider that x

and x

are two objects in N-dimensional

176 space A ={a

,...,a

}, f(x,a

) denotes the value of

177 sample x in the ith dimension a

, then a general metric,

178 named Minkowsky distance, is deﬁned as

ðx

; x

Þ¼

i¼1

f ðx

; a

Þf ðx

; a

1=P

180180

181 where (1) it is called Manhattan distance D

if P = 1; (2)

182 Euclidean distance D

,ifP = 2; (3) Chebychev distance if

183 P = 1. The inﬁnite-norm based distance also can be writ-

184 ten as

ðx

; x

Þ¼max

i¼1

jf ðx

; a

Þf ðx

; a

ÞjðÞ

186186

187 The above metrics equivalentl y deal with the N attributes.

188 However, the features have different inﬂuences on the clas-

189 siﬁcation in some cases, they should be dist inctively pro-

190 cessed. More generally, the weighted distance functions

191 can be deﬁned as

ðx

; x

Þ¼

i¼1

jf ðx

; a

Þf ðx

; a

Þj

1=P

193193

194 where 0 6 w

6 1. A detailed survey on distance function

195 can be seen in Wilson and Martinez (1997).

196 d

) is the information granule centered with sample

197 x

. The size of the neighborhood depends on the threshold

198 d. The greater d is, the more samples will fall into the

199 neighborhood, and the shape of the neighborhoods

200 depends on the norm used. In 2-dimension real space,

201 neighborhoods of x

in terms of the above three metrics

202 and weighted metrics are shown as Fig. 1 . 1-norm based

203 neighborhood is a rhombus region around the center

204 sample x

; 2-norm based neighborhood is a ball region;

205while inﬁnite-norm based neighborhood is rectangle or

206square.

207Given a metric space hU, Di, the fami ly of neighborhood

208granules {d(x

)jx

2 U} forms an elemental granule system,

209which covers the universe, rather than partitioning it. We

210have

211(1) " x

2 U: d(x) 5 B;

212(2) [

x2U

d(x)=U.

213

214A neighborhood relation N over the universe can be

215written as a relation matrix M (N) = (r

)

n·n

where

1; Dðx

; x

Þ 6 d

0; otherwise



217217

218It is easy to show that N satisﬁes the following properties:

219(1) reﬂexivity: r

=1;

220(2) symmetry: r

= r

221

222Obviously, neighborhood relations are one class of

223similarity relations, which satisfy reﬂexivity and symmetry.

224Neighborhood relations draw the objects together for

225similarity or indistinguishability in terms of distances.

226Note 1. d(x) is an equivalent class and N is an equivalence

227relation if d = 0, this case is applicable to discrete data.

228Note 2. dcan take a uniform value for all of the objects or

229distinct values for different objects.

230Note 3. With the same threshold d, the sizes of neighbor-

231hoods with different norms are different, and we have

232d

(x)  d

(x). It is easy to ﬁnd with Fig. 1.

233Deﬁnition 2. Giving a set of samples U, N is a neighbor-

234hood relation on U,{d(x

)jx

2 U} is the family of neigh-

235borhood granules. Then we call hU,Ni a neighborhood

236approximation space.

237Deﬁnition 3. Given hU,Ni, for arbitrary X  U, two sub-

238sets of objects, called lower and upper approximations of

239X in terms of relation N, are deﬁned as

NX ¼fx

jdðx

ÞX ; x

2 U g;

NX ¼fx

jdðx

Þ\X 6¼;; x

2 U g:

241241

242The boundary region of X in the approximation space is

243formulated as

BNX ¼

NX  NX

245245

246The size of the boundary region reﬂects the degree of

247roughness of the set X in the approximation space. Assum-

248ing that X is the sample subset with a decision label, usually

249we hope that the boundary region of the decision is as little

250as possible for decreasing uncertainty in decision. The sizes

∞

Fig. 1. Neighborhoods of x

in terms of three metrics and weighted

metrics: (a) three metrics; (b) three weighted metrics.

Q. Hu et al. / Expert Systems with Applications xxx (2006) xxx–xxx 3

ESWA 1881 No. of Pages 11, Model 5+

1 December 2006 Disk Used

ARTICLE IN PRESS

Please cite this article in press as: Hu, Q. et al., Neighborhood classiﬁers, Expert Systems with Applications (2006), doi:10.1016/

j.eswa.2006.10.043

UNCORRECTED PROOF

251 of the boundary regions depend on X, attributes B to de-

252 scribe U, and the threshold d.

253 Theorem 1. Given hU, Ni and two nonnegative d

and d

,if

254 d

P d

, we have

255 (1) " x

2 U:N

 N

, d

)  d

);

256 (2) " X  U:

X  N

X ; N

X  N

X ,

257 where N

and N

are the neighborhood relations induced with

258 d

and d

, respectively.

259 Proof. d

P d

, we have d

)  d

). Assuming

260 d

)  X,wehaved

)  X. Therefore, we must have

261 x

2 N

X if x

2 N

X. However, x

is not sure in N

X if

262 we have x

2 N

X. Hence N

X  N

X. Similarly, we can

263 get N

X  N

X . h

264 An information system is called a neighborhood system

265 if the attributes generate neighborhood relation over the

266 universe, denoted by NIS = hU,A,V,fi, where A is the

267 real-valued attribute set, f is an informat ion function, f:

268 U · A ! R. More specially, a neighborhood information

269

system is also called a neighborhood decision system if

270 there are two kinds of attributes in the system: condition

271 and decision. And then it is denoted as NDT =

272 hU,C [ D, V, fi.

273 Deﬁnition 4. Given a neighborhood decision table

274 NDT = hU, C [ D,V,fi, X

,...,X

are the object sub-

275 sets with decisions 1 to N, d

) is the neighborhood

276 information granules including x

and generated by attri-

277 butes B  C, Then the lower and upper approximations of

278 the decision D with respect to attributes B are deﬁned as

D ¼[

i¼1

;

D ¼[

i¼1

;

280280

281 where

X ¼fx

ðx

ÞX ; x

2 U g;

X ¼fx

ðx

Þ\X 6¼;; x

2 U g:

283283

284 The decision boundary region of D with respect to attri-

285 butes B is deﬁned as

BNðDÞ¼

D  N

287287

288

Decision boundary is the object subset whose neighbor-

289 hoods come from more than one decision class. On the

290 other hand, the lower approximation of the decision, also

291 called positive region of decision, denoted by POS

(D), is

292 the subset of objects whose neighborhoods consistently

293 belong to one of the decision classes.

294 It is easy to show

D ¼ U, POS

(D) \ BN(D)=B,

295 POS

(D) [ BN( D)=U. Therefore, the neighborhood

296

model divides the samples into two groups: positive region

297 and boundary. Positive region is the sample set which can

298 be classiﬁed into one of the classes without uncertainty

299with the existing attributes, while boundary is the set of

300samples which cannot be determinately classiﬁed.

301Example 1. Fig. 2 shows an exampl e of binary classiﬁca-

302tion in 2-D space, where d

is labeled with ‘‘plus’’ and d

303is labeled with ‘‘point’’. Consider samples x

, x

,andx

304we assign circle neighborh oods to these samples. We can

305ﬁnd d(x

)  d

and d(x

)  d

, while d(x

) \ d

5 B,

306d(x

) \ d

5 B. According to the above deﬁnitions:

307x

2 Nd

, x

2 Nd

and x

2 BN(D).

308The samples in diﬀerent feature subspaces will have dif-

309ferent boundary regions. The size of the boundary region

310reﬂects the discriminability of the classiﬁcation problem

311in the corresponding subspaces. It also reﬂects the recogni-

312tion power or characterizing power of the condition attri-

313butes. The greater the boundary region is, the weaker the

314characterizing power of the condition attributes will be.

315It can be formulated as follows.

316Deﬁnition 5. The dependency degree of D to B is deﬁned as

317the ratio of consistent objects:

ðDÞ¼

jPOS

ðDÞj

jUj

319319

320Where c

(D) reﬂects the ability of B to approximate D.

321Obviously, 0 6 c

(D) 6 1. We say that D completely de-

322pends on B if c

(D) = 1, denoted by B ) D; otherwise

323we say that Dc – depends on B, denoted by B )

324Theorem 2. hU, C [ D, V, fi is a neighborhood decision sys-

325tem; B

 C, B

 B

, then we have

326(1) N

 N

;

327(2) " X  U,

X  N

X , N

X  N

X ;

328(3) POS

ðDÞ 6 POS

ðDÞ, c

ðDÞ 6 c

ðDÞ.

329

330Proof. " x 2 U, we have d

ðxÞd

ðxÞ if B

 B

. Assume

331that d

ðxÞN

X , where X is one of the decision classes,

332then we have d

ðxÞN

X . At the same time, there may

333be x

, d

ðx

Þ 6 N

X and d

ðx

ÞN

X . Therefore,

334POS

ðDÞPOS

ðDÞ. Accordingly, we have c

ðDÞ 6

335c

ðDÞ. h

Fig. 2. An example with two classes.

4 Q. Hu et al. / Expert Systems with Applications xxx (2006) xxx–xxx

ESWA 1881 No. of Pages 11, Model 5+

1 December 2006 Disk Used

ARTICLE IN PRESS

Please cite this article in press as: Hu, Q. et al., Neighborhood classiﬁers, Expert Systems with Applications (2006), doi:10.1016/

j.eswa.2006.10.043

评论收藏

内容反馈

sjmp525

2013-06-13

非常不错，值得参考一下

我爱计算机视觉

粉丝: 3787
资源: 77

KNN分类器 and NEC分类器

最新资源

KNN分类器 and NEC分类器

KNN算法 文本分类器

KNNc++_KNN分类器_

KNN classification 分类器 C++

KNN分类器算法实现

matlab-KNN分类器

kNN分类器和两个实例-Python

KNN分类器完整的matlab代码

KNN分类器实验报告 代码全KNN分类器实验报告 代码全

KNN分类器 人脸识别

模式识别KNN分类器

KNN分类器MATLAB程序

KNN简单邮件分类器

KNN分类器实验报告 代码全

MNIST手写数字分类图像分类KNN分类器 MATLAB代码实现

采用KNN分类器进行分类

KNN_KNN分类器_可输出概率_KNN分类_matlabknn_

knn分类器网页分类器

matlab KNN分类器代码

小白入门KNN分类器.zip

Classifier_min_Local_Mean_f.rar_KNN分类器_knn距离_matlab KNN分类器_最小距离分

利用欧几里得距离实现的KNN分类器

Qt 5实现串口调试助手 （源工程文件、0积分下载）

【SystemVerilog】路科验证V2学习笔记（全600页）.pdf

AutoSAR标准协议4.2.2

最新资源

KNN算法文本分类器

KNN分类器实验报告代码全KNN分类器实验报告代码全

KNN分类器人脸识别

KNN分类器实验报告代码全

Qt 5实现串口调试助手（源工程文件、0积分下载）