%
介绍
现代计算和信息技术的发展， 使得工程领域收集了大量的
类时才建立分类， 因此会招致很高的计算开销， 当有大量的训 练资料时， 严重影响它的可伸缩性。
资料。 数据挖掘技术可以用来从大量的资料中发现模式和有用 的信息。 数据挖掘包括各种不同的技术用来对原始资料进行预 处理以便抽取特征和移除噪声信息，然后找到有趣的模式、 模 型和其它有用的信息， 进行新的资料的分类或者预测将来的事 件等等。分类是资料挖掘中一种非常重要的领域。可以这样描 （! %， …， ， 其中 述分类： 给定一个数据记 录 集 合 !" ! !， ! &， ! #， $） （ …， 称作预测变量， 那么分类问题 ! !， #） $ 称作目标变量， % %’% ， # 使得分类的误差 ! 最小。目标 就是要找到一个函数： &： ! !$ ， 变量 $ 和决策变量 ! % 的值可以是离散的也可以是连续的。 有很多技术可以用于数据挖掘中的分类问题， 决策树 神经网络 (#*， 基于实例的分类 (#*等等。
（!""# ） 文章编号 %""!=A&&%= %&="""E="!
!"#"$%&’ () $ *+$##,),&$-,(. /"-’(0
1, 23")".4 1,3 13 5’$.4 5’$(
（I9722: 2J B9232519; K L.3.465630 ， M61N134 O31@6/;10< 2J F6/23.?019; M61N134 %"""A&） .38 F;0/23.?019;，
从表 & ， 可以得到最终的聚类为 ,& 、 ,# 、 ,’ 。给定一个没有 类标号的测试资料， 根据生成的聚类结构就可以预测它的目标 （)$’ ， ？） ， 作如下计算： 变量的值。比如给定资料 . *， （! ， （! ， （! ， / ,& ） 1%$+*! ， / ,# ） 1"$’)& ， / ,’ ） 1"$%%( ， ! 更加 接近 ,’ ， 因此 " 的值为 " 。 上述的训练资料都是数值型的， 实际上该算法也适合于符 号资料的处理。但是在处理以前必须对符号数据进行数值化， 也就是把一个离散的符号函数转化成数值函数， 这种转化非常 直观， 也很简单， 在文献 :+;中有详细的描述。
(%)&*
!$!
聚类分析
在 # 维空间上给定一个具有 ( 个 资 料 记 录 的 集 合 ) ， 把)
分成 * 个集合， …， 那么 + （ …， 就是一个聚类。 +%， +!， +’， !， ’） % %’%， 主要的聚类方法有以下几类 (#*。 、 层次的方法 （716/./9719.: 划分方法 （-./010123134 560728 ） 、 基于密度的方法 （863;10<=>.;68 560728 ） 、 基于 网 格 的 560728 ） 、 基 于 模 型 的 方 法 （5286:=>.;68 方 法 （4/18=>.;68 560728 ） 。 560728 ） 聚类分析传统地不被用来进行分类。 因为聚类是无指导学 ， 所以聚类不依赖预先定义的类和带 习 （?3;?-6/@1;68 :6./3134 ） 类标号的训练资料。如果给每一个聚类分配一个类标号， 即进 ， 那么就可以用学习过的 行有指导的学习 （;?-6/@1;68 :6./3134 ） 聚类结构对新的资料进行分类。 这样就可以使得 + 最近邻分类 法获得很好的伸缩性，因为不用计算每个训练资料之间的距 离， 而只要计算给定的资料与聚类中心之间的距离即可。
本线性可分性较差时，则非线性内核 RSB 的性能要优于线性 内核 RSB。
表! 基于线性内核和径向基函数内核的 RSB 的签名鉴别结果
线性内核 RSB 错误拒绝率 错误接受率 径向基函数内核函数内核 RSB 错误拒绝率 错误接受率
RSB 分类器的过程就是解一个如下形式二次规划问题： " # W/*X（!!$ Y % ! ! $ W %
、
! + 最近邻分类和聚类 !$% + 最近邻分类
’ 最近邻分类是一种非常直接的方法，它基于 模 拟 学 习 。 训练数据用 #,% 维 属 性 描 述 。 每 个 资 料 记 录 代 表 #,% 维 空 间 中的一个 数 据 点 ， 这样， 所 有 的 训 练 资 料 都 存 放 在 #,% 维 模 式
"$")( "$%%# "$(!%
789 平方距离：
*
（! ， . -） 1%
& ) %
（! & (- & ）
% "
"$""& "$%’’
" "$%"%
-&
%&"
!
（& ）
’
"$%"%
其中， !& 和 -& 分 别 是 在 第 & 维 ! 的 坐 标 和 聚 类 - 的 中 心 坐标。 下面给出算法说明， 如图 % 所示。
!
! "% % %$’ %$’ !$()
! "! % %$’ %$’ !$()
! %% " " &$" &$"
! %! " " &$" &$"
! （#(% ） （ ） （ ） ! " #3% 4! " # ! （ ） ； ! " # ) #
%$’* %$’* #$"’ #$"’
! ! （#(% ） （ ） （ ） ! & #3% 4! & # ） ， …， …， !（ # 1! ， &， ’； & 1% ， !， * 。 %%"（#） & # ) #
当 #)% 时， $&& 1" ， $&" 1" ， $22 1" 。 设目标变量 " 的取值范围为 " !5" ， …， 定义每个目 %， +6， 标类的平均向量：
’, ! ! !
"$"&* "$"&*
（# ） %!"
!
聚类 ,% 中心坐标 （!$()， ， 分配类标号为 !， 记作 ,% （!$()， !$()） !$()-!） 聚类 ,! 中心坐标 （&$"， ， 分配类标号为 !， 记作 ,% （&$"， &$"） &$"-!）
基金项目： 国家自然科学基金项目 （编号： 资助 SEAS"""E ）
& 有监督的聚类方法 &$% 算法描述
为了说明这种聚类方法， 首先定义一些内容。 设 !" （! %， ! !， ! &，…， ! ,， $ ）为定义在 ,-% 维 空 间 中 的 向 训练数据集的大小为 .， 量， 其中 ! % 为预测变量， $ 为目标变量， 定义预测变量 ! % 与目标变量的 $ 之间的相关系数的平方 (A*：
作者简介： 李雪峰， 博士研究生， 主要从事数据挖掘、 决策支持系统方面的研究。刘鲁， 博士生导师， 研究方向为电子商务、 供应链管理和信息系统。 博士研究生， 研究方向为电子商务、 信息系统。 "! ，
计算机工程与应用
!""#$%&
E
（’ ） %&" 1 其中：
!
#"
（’ ） $&"
! !
!
（’ ） $&& "$22（’）
第二步， 根据公式 （& ） 计算每个训练资料与两个初始聚类 的距离，并且得到最终的聚类结构和数目，计算结果如表 & （! ） 所示。
表&
! !% !! " % ! % ! " "
（. ， （. ， / ,%）/ ,!）
%! &，# ， …， …， ! ,& ) # ) % , 1" ， %， +； &)% ， !， * ’,
一种分类方法的研究
张 ! （北京航空航天大学经济管理学院， 北京 %"""A&）
B=5.1:： ;?-6/C92-D;13.$925
摘 要 介绍了一种基于聚类的分类方法。传统的聚类是无监督学习， 也就是说不需要先验知识。基于聚类的分类方法
李雪峰
刘
鲁
利用样本的类标号信息进行学习， 形成非层次结构的聚类， 每个聚类都有类标号， 用来对新的数据进行分类。 对于大量的 学习样本， 具有很好的伸缩性。 关键词 数据挖掘 分类 聚类 文献标识码 F 中图分类号 GH&%%
标变量只取 " ， % 两个值。训练资料集如表 % 所示。经过第一步 计算得到的结果如表 ! 所示。
（下转 *( 页）
%"
!""#$%&
计算机工程与应用
%$$$!V， RSB 的 主 要 目 标 就 是 通 过 一 个 内 核 函 数 把 训 练 样 本 映
射到高维空间， 使得两类样本线性可分， 然后在该空间里寻找 最优分类超平面。不同的 内 核 函 数 就 对 应 不 同 的 RSB。 训 练
空间中。给定一个未知样本， 找 ’ 最近邻分类法搜索模式空间， 这 ’ 个资料记录是未知样 出最接近未知样本的 ’ 个资料记录。 本的 ’ 个 “近邻” 。 ’ 最近邻分类法在实践中取得 了 很 大 的 成 功， 但是它的分类性能容易受噪声资料和异常值的影响。不象 决策树这样的学习方法， ’ 最近邻分类法直到新的 样 本 需 要 分