30542010,31(13)
计算机工程与设计Computer Engineering and and Design 计算机工程与设计Computer Engineering Design
动态聚类法的粗糙集规则提取
宋云雪1,2，于宏超1，史永胜1
(1. 中国民航大学航空工程学院，天津300300；2. 中国民航大学科技处，天津300300)
摘
要：针对航空发动机的故障样本，提出了一种基于动态聚类的粗糙集规则提取算法。给出了该算法的模型，描述了动态聚类方法和广义欧氏距离，举例说明了这种算法，用神经网络对样本进行训练并验证约简是否正确。结果表明，动态聚类法可以改善分类，使最终的核与约简更精准，去除了干扰信息的影响，在保证诊断精度的同时。提高了故障识别的正确率。关键词：动态聚类法; 广义重要度; 广义欧氏距离; 粗糙集; 属性约简中图法分类号：TP391
文献标识码：A
文章编号：1000-7024(2010) 13-3054-03
Rough set rule extraction algorithm of dynamic clustering method
SONG Yun-xue 1,2,
YU Hong-chao 1,
SHI Yong-sheng 1
(1. College of Aeronautical Engineering, Civil Aviation University of China, Tianjin 300300, China;
2. Science and Technology Agency, Civil Aviation University of China, Tianjin 300300, China )
Abstract ：Considering the fault samples of aero-engine, the rule extraction algorithm of rough set based on dynamic clustering method is proposed. Firstly the model of the algorithm is obtained, where the dynamic clustering method and general Euclidean distance are de-fined, and then a given example illustrates this extraction algorithm, at last a Neural-network is used to train the fault samples, and validates whether the reduction is correct. The result we get shows that the dynamic clustering method can improve the classification, and the ultimate nuclear and reduction are more accurate. With removing the impact of interference information, the proposed method improves the accuracy of fault identification as well as ensuring the precision of diagnosis.
Key words ：dynamic clustering method; general important degree; general Euclidean distance; rough set; attribute reduction
0引言
广义重要度考虑每个属性的特征特点的同时，也考虑到了它对分类决策的影响，使分类具有更好的相似性，从而具有更高的准确率[1-2]。
本文先用动态聚类法获得属性分类，然后用变精度粗糙集进行规则提取，最后用实例来说明验证算法。
目前常用的聚类方法分为无监督聚类和有监督聚类。神经网络方法中的聚类中心就是采用无监督方法求得的，其收敛速度快分类能力好。与有监督聚类相比，无监督聚类存在着更大的不确定性。这是因为在无监督问题中没有了已知的样本集，甚至可能不知道样本的类别数，可以利用的信息量大大减少。为了解决这种不确定性，专家们利用了很多其他理论进行辅助，例如模糊集理论、粗糙集理论。加入的这些方法使分类有了很多改进之处，但也有不足，例如模糊K-means 方法对聚类中心的初值十分敏感，而粗糙K-means 方法中有过多的参数要选择，降低了应用的方便性。
动态聚类法可以消除有监督聚类和无监督聚类方法中分类的不确定性，从而改善分类质量，它对聚类中心的初值不敏感，增加了其应用的方便性。本文中动态聚类算法中涉及到的距离计算全部采用广义欧氏距离，广义欧氏距离是一种空间的广义重要度距离，其中涉及到属性广义重要度的概念。
1
1.1
理论基础
属性的广义重要度和空间的属性广义重要度欧氏距离[3]
针对所有决策属性，定义一种广义属性重要度。定义1
给定决策系统S ={U ，C ∪{D }，V }，U /d ={
=
2
｛
1
2
,
,
=
——从个数中取2的组合，
，表示
——
表示属
收稿日期：2009-08-27；修订日期：2010-01-11。
基金项目：国家自然科学基金委员会与中国民用航空局联合项目(60879017) ；天津市自然科学基金项目(08JCYBJC11600) 。
作者简介：宋云雪(1968－) ，女，硕士，高级工程师，硕士生导师，研究方向为结构智能化设计、故障诊断与结构修理；于宏超(1984－) ，女，硕士研究生，研究方向为故障诊断、状态监控；史永胜(1965－) ，男，博士后，教授，硕士生导师，研究方向为结构智能化设计、故障诊断与结构修理、专家系统、知识表示。E-mail ：[email protected]
宋云雪，于宏超，史永胜：动态聚类法的粗糙集规则提取
2010,31(13) 3055
性
1
, ¸ö·½Ïò£¬Ô
ò
µÄÊôÐÔ¹ãÒåÖØÒª¶ÈÅ·ÊϾàÀëΪ
)
——在各个方向上的分量。
1.2动态聚类算法描述
聚类实际就是想找到一种最优分类。迭代法的基础思想
是：先找一个初始划分，然后通过不断调整聚类中心进行重新聚类，直到满足要求为止。迭代最优化过程是从不合理的划分到划分，是一个动态的迭代过程，因此也称为动态聚类法。
初始聚类中心的选择往往会影响迭代结果，所以本文在选择初始划分时，把全部样本看作一类，然后用均值法找其类心，用广义重要度欧式距离衡量所有样本与类心的距离。动态聚类法允许模式样本从一个聚合类转移到另一个聚合类，使初始的不准确的划分逐步得到改进。
动态聚类方法，算法简单，计算存储量小，算法中的距离计算采用广义欧氏距离，可以在一定程度上消除样本分类的不确定性，改善分类质量。下面介绍该算法的计算步骤：
设
1
,
=
1
*,
2
, ,
¡ª¡ªÊä³öÖµ£¬¸ÃÖµÏÔʾ·¢¶¯»ú״̬£»
1
——低压转子转速；
——尾喷口
指示值；——发动机机匣振动值。数据样
本中2组正常数据和7组故障数据，采用归一化方法对数据进行标准化，处理后的数据表如表1
所示。
，计算所有样本与样本中心的距离，距离中心
1
1
最远的样本点暂定为新的聚类中心，按最小距离原则把样本分成两类，
然后计算样本重新聚类后的类心
个类心。根据最小距离原则重新聚类迭代类心
后的样本，
并计算此时所有样本点与聚类中心的距离平方和
1
，
3
，
5
，
7
，
8
}，
且
1
，
3
，5
，7
}、{9
}
，
N
1
“最佳”
3056
{
1
2010,31(13)
4
计算机工程与设计Computer Engineering and Design
9
7
，
4
7
}、{
}、{
}，
91
，
5
}、{，}，
5
，}、{
4
，
7
}、{
91
}
。采用变精度粗糙集约简算法对样本进行约简，论域，=
{
3
，=
5
，
7
，
9
}，
条件属性
£¬
=
=
{
，，，=
==
{
={
=
2
}
，
=
{=0.7，
在计算
*0.7
1中所有项对应的样本区间所
={
占的比例值，经计算，
所有比例值的均值为}∨{
}，因此得到两个约简{
£¬
核为{，}，
}。
2111
3333
, , ,
5555
, , ,
, ,
,
1,
1
, 3,
3
, 5,
5
, , ,
2.3算法的对比验证
用传统粗糙集方法处理表1的数据[6]，先采用模糊集聚类，
£¬
之后也采用单纯的粗糙集约简算法[7-9]，得到的约简为{，，
，，
，
，{
，}，
£¬
(上接第3002页) [2]
Phil Kerly.Cache blocking technique on hyper-threading tech-nology enabled processors [EB/OL]. http://software.intel.com/en-us/articles/cache-blocking-technique-on-hyper-threading-technology-enabled-processors,2007. [3]
David A Bader,Varun Kanade,Kamesh Madduri.SWARM:A parallel programming framework for multicore processors [C ]. Parallel and Distributed Processing Symposium, 2007:1-8. [4]
Cerin Christophe, Michel Koskas.Work stealing technique and scheduling on the critical path [C ].The 3rd International Confe-rence on Grid and Pervasive Computing,2008. [5]
Guy E Belloch, Phillip B Gibbons.Effectively sharing a cache
[9][8][7][6]
among threads [C ].Proceedings of the 16th ACM Symposium on Parallelism in Algorithms and Architectures,2004.
Christophe Cerin,Michel Koskas.Work stealing technique and scheduling on the critical path [C ].The 3rd International Confe-rence on Grid and Pervasive Computing,2008:227-232.Acar U A,Blelloch G E,Blumofe R D.The data locality of work stealing [C ].Theory of Computing Systems,2002:321-347.Frigo M, Strumpen V . The cache complexity of multithreaded cache oblivious algorithms [C ].ACM Symposium on Parallelism in Algorithms and Architectures,2006:271-280.
Intel Corporation. IntelVTune TM performance analyzer [EB/OL ].http://software.intel.com/en-us/intel-vtune.
30542010,31(13)
计算机工程与设计Computer Engineering and and Design 计算机工程与设计Computer Engineering Design
动态聚类法的粗糙集规则提取
宋云雪1,2，于宏超1，史永胜1
(1. 中国民航大学航空工程学院，天津300300；2. 中国民航大学科技处，天津300300)
摘
要：针对航空发动机的故障样本，提出了一种基于动态聚类的粗糙集规则提取算法。给出了该算法的模型，描述了动态聚类方法和广义欧氏距离，举例说明了这种算法，用神经网络对样本进行训练并验证约简是否正确。结果表明，动态聚类法可以改善分类，使最终的核与约简更精准，去除了干扰信息的影响，在保证诊断精度的同时。提高了故障识别的正确率。关键词：动态聚类法; 广义重要度; 广义欧氏距离; 粗糙集; 属性约简中图法分类号：TP391
文献标识码：A
文章编号：1000-7024(2010) 13-3054-03
Rough set rule extraction algorithm of dynamic clustering method
SONG Yun-xue 1,2,
YU Hong-chao 1,
SHI Yong-sheng 1
(1. College of Aeronautical Engineering, Civil Aviation University of China, Tianjin 300300, China;
2. Science and Technology Agency, Civil Aviation University of China, Tianjin 300300, China )
Abstract ：Considering the fault samples of aero-engine, the rule extraction algorithm of rough set based on dynamic clustering method is proposed. Firstly the model of the algorithm is obtained, where the dynamic clustering method and general Euclidean distance are de-fined, and then a given example illustrates this extraction algorithm, at last a Neural-network is used to train the fault samples, and validates whether the reduction is correct. The result we get shows that the dynamic clustering method can improve the classification, and the ultimate nuclear and reduction are more accurate. With removing the impact of interference information, the proposed method improves the accuracy of fault identification as well as ensuring the precision of diagnosis.
Key words ：dynamic clustering method; general important degree; general Euclidean distance; rough set; attribute reduction
0引言
广义重要度考虑每个属性的特征特点的同时，也考虑到了它对分类决策的影响，使分类具有更好的相似性，从而具有更高的准确率[1-2]。
本文先用动态聚类法获得属性分类，然后用变精度粗糙集进行规则提取，最后用实例来说明验证算法。
目前常用的聚类方法分为无监督聚类和有监督聚类。神经网络方法中的聚类中心就是采用无监督方法求得的，其收敛速度快分类能力好。与有监督聚类相比，无监督聚类存在着更大的不确定性。这是因为在无监督问题中没有了已知的样本集，甚至可能不知道样本的类别数，可以利用的信息量大大减少。为了解决这种不确定性，专家们利用了很多其他理论进行辅助，例如模糊集理论、粗糙集理论。加入的这些方法使分类有了很多改进之处，但也有不足，例如模糊K-means 方法对聚类中心的初值十分敏感，而粗糙K-means 方法中有过多的参数要选择，降低了应用的方便性。
动态聚类法可以消除有监督聚类和无监督聚类方法中分类的不确定性，从而改善分类质量，它对聚类中心的初值不敏感，增加了其应用的方便性。本文中动态聚类算法中涉及到的距离计算全部采用广义欧氏距离，广义欧氏距离是一种空间的广义重要度距离，其中涉及到属性广义重要度的概念。
1
1.1
理论基础
属性的广义重要度和空间的属性广义重要度欧氏距离[3]
针对所有决策属性，定义一种广义属性重要度。定义1
给定决策系统S ={U ，C ∪{D }，V }，U /d ={
=
2
｛
1
2
,
,
=
——从个数中取2的组合，
，表示
——
表示属
收稿日期：2009-08-27；修订日期：2010-01-11。
基金项目：国家自然科学基金委员会与中国民用航空局联合项目(60879017) ；天津市自然科学基金项目(08JCYBJC11600) 。
作者简介：宋云雪(1968－) ，女，硕士，高级工程师，硕士生导师，研究方向为结构智能化设计、故障诊断与结构修理；于宏超(1984－) ，女，硕士研究生，研究方向为故障诊断、状态监控；史永胜(1965－) ，男，博士后，教授，硕士生导师，研究方向为结构智能化设计、故障诊断与结构修理、专家系统、知识表示。E-mail ：[email protected]
宋云雪，于宏超，史永胜：动态聚类法的粗糙集规则提取
2010,31(13) 3055
性
1
, ¸ö·½Ïò£¬Ô
ò
µÄÊôÐÔ¹ãÒåÖØÒª¶ÈÅ·ÊϾàÀëΪ
)
——在各个方向上的分量。
1.2动态聚类算法描述
聚类实际就是想找到一种最优分类。迭代法的基础思想
是：先找一个初始划分，然后通过不断调整聚类中心进行重新聚类，直到满足要求为止。迭代最优化过程是从不合理的划分到划分，是一个动态的迭代过程，因此也称为动态聚类法。
初始聚类中心的选择往往会影响迭代结果，所以本文在选择初始划分时，把全部样本看作一类，然后用均值法找其类心，用广义重要度欧式距离衡量所有样本与类心的距离。动态聚类法允许模式样本从一个聚合类转移到另一个聚合类，使初始的不准确的划分逐步得到改进。
动态聚类方法，算法简单，计算存储量小，算法中的距离计算采用广义欧氏距离，可以在一定程度上消除样本分类的不确定性，改善分类质量。下面介绍该算法的计算步骤：
设
1
,
=
1
*,
2
, ,
¡ª¡ªÊä³öÖµ£¬¸ÃÖµÏÔʾ·¢¶¯»ú״̬£»
1
——低压转子转速；
——尾喷口
指示值；——发动机机匣振动值。数据样
本中2组正常数据和7组故障数据，采用归一化方法对数据进行标准化，处理后的数据表如表1
所示。
，计算所有样本与样本中心的距离，距离中心
1
1
最远的样本点暂定为新的聚类中心，按最小距离原则把样本分成两类，
然后计算样本重新聚类后的类心
个类心。根据最小距离原则重新聚类迭代类心
后的样本，
并计算此时所有样本点与聚类中心的距离平方和
1
，
3
，
5
，
7
，
8
}，
且
1
，
3
，5
，7
}、{9
}
，
N
1
“最佳”
3056
{
1
2010,31(13)
4
计算机工程与设计Computer Engineering and Design
9
7
，
4
7
}、{
}、{
}，
91
，
5
}、{，}，
5
，}、{
4
，
7
}、{
91
}
。采用变精度粗糙集约简算法对样本进行约简，论域，=
{
3
，=
5
，
7
，
9
}，
条件属性
£¬
=
=
{
，，，=
==
{
={
=
2
}
，
=
{=0.7，
在计算
*0.7
1中所有项对应的样本区间所
={
占的比例值，经计算，
所有比例值的均值为}∨{
}，因此得到两个约简{
£¬
核为{，}，
}。
2111
3333
, , ,
5555
, , ,
, ,
,
1,
1
, 3,
3
, 5,
5
, , ,
2.3算法的对比验证
用传统粗糙集方法处理表1的数据[6]，先采用模糊集聚类，
£¬
之后也采用单纯的粗糙集约简算法[7-9]，得到的约简为{，，
，，
，
，{
，}，
£¬
(上接第3002页) [2]
Phil Kerly.Cache blocking technique on hyper-threading tech-nology enabled processors [EB/OL]. http://software.intel.com/en-us/articles/cache-blocking-technique-on-hyper-threading-technology-enabled-processors,2007. [3]
David A Bader,Varun Kanade,Kamesh Madduri.SWARM:A parallel programming framework for multicore processors [C ]. Parallel and Distributed Processing Symposium, 2007:1-8. [4]
Cerin Christophe, Michel Koskas.Work stealing technique and scheduling on the critical path [C ].The 3rd International Confe-rence on Grid and Pervasive Computing,2008. [5]
Guy E Belloch, Phillip B Gibbons.Effectively sharing a cache
[9][8][7][6]
among threads [C ].Proceedings of the 16th ACM Symposium on Parallelism in Algorithms and Architectures,2004.
Christophe Cerin,Michel Koskas.Work stealing technique and scheduling on the critical path [C ].The 3rd International Confe-rence on Grid and Pervasive Computing,2008:227-232.Acar U A,Blelloch G E,Blumofe R D.The data locality of work stealing [C ].Theory of Computing Systems,2002:321-347.Frigo M, Strumpen V . The cache complexity of multithreaded cache oblivious algorithms [C ].ACM Symposium on Parallelism in Algorithms and Architectures,2006:271-280.
Intel Corporation. IntelVTune TM performance analyzer [EB/OL ].http://software.intel.com/en-us/intel-vtune.