朱俚治

（南京航空航天大學(xué)信息中心 南京 210016）

一種基于相似性計算與決策系統(tǒng)的最優(yōu)解算法?

朱俚治

（南京航空航天大學(xué)信息中心 南京 210016）

當(dāng)今有多種尋找最優(yōu)解的算法，k-近鄰算法、蟻群算法和退火算法都是較為經(jīng)典的智能算法。k-近鄰算法在尋找最優(yōu)解算法方面有很大的應(yīng)用價值，因此對k-近鄰算法和粗糙集中的決策系統(tǒng)研究之后，提出一種基于相似性計算算法的最優(yōu)解算法。論文的思路是首先使用k-近鄰算法計算兩個實例屬性之間的距離，其次使用相似性算法對k-近鄰算法求得的解進(jìn)行計算，然后使用決策系統(tǒng)對解的屬性作出決策，是一般性的解，還是較優(yōu)解或是更優(yōu)解，將相似性算法和決策系統(tǒng)在尋找最優(yōu)解之中進(jìn)行應(yīng)用是論文的創(chuàng)新點。

k-近鄰算法；相似性算法；決策系統(tǒng)

1 引言

分類是認(rèn)識客觀世界，形成抽象概念和進(jìn)行推理決策的基礎(chǔ)，所以分類建模是機(jī)器學(xué)習(xí)研究的核心問題之一［1～4］。k-近鄰算法通過計算兩個實例屬性之間的距離來實現(xiàn)實例之間的分類，在進(jìn)行分類的時候k-近鄰算法采用了歐氏距離對實例屬性的距離進(jìn)行了計算，從而達(dá)到了分類的目的。

將粗糙集應(yīng)用于實例的分類［1～4］，由 1982 年P(guān)awlak教授提出。后來經(jīng)過許多研究者不斷地完善粗糙集理論，為符號數(shù)據(jù)屬性簡約性、依賴性分析與分類規(guī)則學(xué)習(xí)提供了形式化框架［1～4］。事實上k-近鄰算法和粗糙集對實例尋找最優(yōu)解過程就是實例分類的過程，如果兩個實例成功實現(xiàn)了屬性上的匹配，那么該實例就找到了最優(yōu)解。

本文使用相似性算法對k-近鄰算法求出的解進(jìn)行計算，經(jīng)過相似性計算之后再使用粗糙集中的決策系統(tǒng)對計算的結(jié)果做出決策，該解是較優(yōu)解或還是更優(yōu)解，從而達(dá)到對解好與壞的度量目的，在本文的最后給出了算法分析。將k-近鄰算法，決策系統(tǒng)和相似性算法三種算法相互結(jié)合在一起形成一種新的尋找最優(yōu)解算法是本文的創(chuàng)新之處。

2 k-近鄰算法

基于實例的學(xué)習(xí)方法中的最基本的是k-近鄰算法。這個算法假定所有的實例對應(yīng)于n維空間中的點。一個實例的最近鄰是根據(jù)標(biāo)準(zhǔn)歐氏距離定義的，更精確地講把任意的實例x表示為下面的特征向量［1］。

其中，ar(x)表示實例x的第r個屬性值。那么兩個實例 xi和 xj間的距離定義為 d(xi，xj)，其中［1］：

3 k-近鄰算法的實現(xiàn)

1）k-近鄰算法距離公式

xi，xj分別表示兩個訓(xùn)練實例，兩個實例屬性之間的差值的大小可以使用距離公式來計算［1～3］。

y=d(xi，xj)公式表示實例 xi與 xj分類屬性之間的距離，為了找到與實例xi的屬性最為接近的實例xj，則這時需要使用距離公式計算出實例xi所有分類屬性與實例xj的屬性距離，如果找到了與xi最為接近的xj，這時實例xi與xj達(dá)到最鄰近值。

2）A代表要求分類的實例，該實例有n個屬性。am表示實例A進(jìn)行分類時的能夠起到分類作用的屬性，B表示儲存器中一個的實例，實例B具有的屬性bn。

d1表示a1與b1之間的距離，d2表示a1與b2之間的距離，d3表示a1與b3之間的距離，dn表示a1與bn之間的距離。

4 相似性計算法

4.1 相似性函數(shù)及其實例屬性間的距離

1）在以上的公式中有兩種距離：（1）k-近鄰算法求得的距離，（2）當(dāng)前已知的k-近鄰算法最小的距離。

2）以下對實例A與實例B之間的距離有下面的討論和分析：

（1）dn-1為實例A與實例B屬性之間的一種距離，該距離的大小為當(dāng)前已知的k-近鄰算法最小距離。

（2）dn為實例A與實例B屬性之間的另一中距離，該距離的大小為k-近鄰算法求得的距離。

（3）an與bn分別表示是實例 A，實例B的屬性。d1表示屬性a1與屬性b1之間的距離，d2表示屬性a1與屬性b2之間的距離，d3表示屬性a1與屬性b3之間的距離…dn表示屬性a1與屬性bn之間的距離。d1，d2，d3…dn的大小各不相同。

3）關(guān)于dn與dn-1的比較有以下的討論：

（1）dn-1表示屬性a1與屬性bn-1之間的距離，dn表示屬性a1與屬性bn之間的距離。

（2）如果dn＜dn-1，那么a1與bn之間的距離小于a1與bn-1之間的距離。

（3）如果 dn-1＜dn，那么 a1與bn-1之間的距離小于a1與bn之間的距離。

4.2 實例A與實例B屬性之間的分析和討論

1）當(dāng)實例 A與實例B屬性之間的距離為dn＜dn-1時：

（1）dn為實例A與實例B屬性之間的另一中距離，該距離的大小為k-近鄰算法求得的距離，dn-1為實例A與實例B屬性之間的一種距離，該距離的大小為當(dāng)前已知的k-近鄰算法最小距離。因此由 dn＜dn-1條件可得如下的結(jié)論：

（2）當(dāng)dn的值越小時，則表明實例A的屬性a1與實例B的某個屬性bn相似性就越強(qiáng)。如果表明此時實例A的屬性a1與實例B的某個屬性bn之間的距離更小，實例A與實例B的屬性更為接近，因此此時k-近鄰算法求得的距離比當(dāng)前已知的最小k-近鄰算法距離更好。

（3）因此當(dāng)dn＜dn-1之時，則在屬性相似度這一方面a1與bn的相似程度強(qiáng)于a1與bn-1的相似程度，因此這時應(yīng)該選擇bn作為a1目前最佳匹配屬性。

2）當(dāng)實例 A與實例 B屬性之間的距離為dn-1＜dn時：

（1）dn為實例A與實例B屬性之間的另一中距離，該距離的大小為k-近鄰算法求得的距離，dn-1為實例A與實例B屬性之間的一種距離，該距離的大小為當(dāng)前已知的k-近鄰算法最小距離，因此由 dn-1＜dn條件可以得如下的結(jié)論：

（2）當(dāng)dn的值越大之時，則表明實例A的屬性a1與實例B的某個屬性bn相似性就越差。如果

在本文中將r設(shè)定為函數(shù) y=f(x)的比值。r的含義是度量實例A與實例B相似性的一個相似性系數(shù)，體現(xiàn)了實例A與實例B之間的相似度。dn與dn-1表示實例A與實例B屬性之間的距離。如果相似系數(shù)r的值越小，那么則此時dn的值比dn-1來得更小，那么實例A的屬性a1與實例B的屬性bn就越相近，那么此時求就得的解就為更優(yōu)。如果相似系數(shù)r的值越大，那么則此時dn的值比dn-1來得更大，那么實例A的屬性a1與實例B的屬性bn就相差較遠(yuǎn)，屬性的偏離程度較大，那么此時求就得的解就較差。

2）對相似性系數(shù)r的討論：

相似系數(shù)r在［0，1］之間變化，如果相似系數(shù)r越小，那么實例A與實例B相似性也就越強(qiáng)，這時求得的解也就更優(yōu)。

（1）當(dāng)相似性系數(shù)r的值小于1時：

如果相似系數(shù)r越小或十分接近于0時，那么則實例屬性之間的相似性就越強(qiáng)，實例之間相似性解也就更優(yōu)。

（2）當(dāng)相似性系數(shù)r的值大于1時：

如果相似系數(shù)r的值越大時實例A與實例B的屬性偏離程度就越嚴(yán)重，實例A與實例B之間表明此時實例A的屬性a1與實例B的某個屬性bn之間的距離更加偏離，實例A與實例B的屬性偏離程度越嚴(yán)重，k-近鄰算法求得的距離比當(dāng)前已知的k-近鄰算法最小距離來得更差。

（3）因此當(dāng)dn-1＜dn之時，則在屬性相似度這一方面a1與bn的相似程度弱于a1與bn-1的相似程度，因此此時應(yīng)該選擇bn-1作為a1目前最佳匹配屬性。

4.3 相似性計算的相似系數(shù)

1）將相似性系數(shù)設(shè)為：的相似性也就越差，此時求得的解也就更差。

5 粗糙集的決策系統(tǒng)

在實際應(yīng)用中存在一大類任務(wù)：給定一組有特征描述的樣本和樣本的類別，需要通過一個學(xué)習(xí)算法從該組本文中學(xué)習(xí)一個分類函數(shù)，實現(xiàn)從特征到分類的映射，粗糙集理論中稱該數(shù)據(jù)集為信息系統(tǒng)［6-7］。

定義1 信息系統(tǒng)可形式化為如下的四元組：IS=U，A，V，f ，其中 U={x1，x2，x3，…，xn}為研究對象的有限集合，即論域；A={a1，a2，a3，…，an}為描述對象的全部屬性所組成的集合，即屬性集；為屬性集A的值域，其中Va為屬性a∈A值域；f：U×A→V為信息函數(shù)，表示對每一個x∈U，a∈A，f(x，a)∈Va。 當(dāng) 系 統(tǒng) 中 屬 性 集A=C∪D，C∩D=Φ 其中C為條件屬性集，D為決策屬性時，該信息系統(tǒng)也被稱為決策表［7～9］。

6 決策系統(tǒng)在尋找最優(yōu)解上的計算

由于決策條件屬性值的不同，因此能夠產(chǎn)生不同的決策屬性，事實上正是由于不同的決策的屬性值，產(chǎn)生了不同的決策結(jié)果，這些不同的決策結(jié)果能夠?qū)⒉煌瑢傩缘臉永M(jìn)行有效的分類［8～9］。條件屬性的屬性值決策規(guī)則的內(nèi)涵，是決策系統(tǒng)做出決策結(jié)果的重要決定因數(shù)［8～9］。

6.1 值域和屬性集

1）域：

U={x1，x2，x3，…，xn} ，其中分別表示等待求解的實例A。

2）屬性集：

A={a1，a2，a3}，其中 a1表示當(dāng)前 k-近鄰算法求得的距離，a2表示相似性系數(shù)r，a3表示決策系統(tǒng)的決策值。

3）值域：V={Y，N}

6.2 實例A解的屬性決策表

如果在一個決策系統(tǒng)中把每一條樣例的條件屬性值部分作為規(guī)則的前件，把決策屬性值部分作為規(guī)則的后件，那么每一條樣例都可以看成一條規(guī)則［8～9］。在決策系統(tǒng)中每一條樣例都對應(yīng)著一條具體的決策規(guī)則。信息系統(tǒng)中的屬性集合可以分成兩部分，一部分為條件屬性集合，另一部分為決策屬性，這種信息系統(tǒng)通常稱為決策系統(tǒng)或決策表［8～9］。在以下的決策表中可將決策屬性分為條件屬性和決策屬性［8～9］。

在以下的系統(tǒng)決策表中，條件屬性是：k-近鄰算法求得的距離，相似性系數(shù)r。決策屬性是：實例A與實例B的相似程度。

說明：1）如果k-近鄰算法求得的距離，決策屬性值為Y。

2）當(dāng)相似性系數(shù)r越小時，決策屬性值為Y，否則決策屬性值為N。

3）當(dāng)1）與2）的屬性值都取Y時：決策屬性值為Y，否則決策屬性值為N。

4）當(dāng)1）與2）的屬性值都取Y時：決策系統(tǒng)的決策結(jié)果為求得實例A的解為更優(yōu)。

決策規(guī)則：

（k-近鄰算法求得的距離，Y）Λ（相似性系數(shù)r越小時，Y）?（求得實例的解為更優(yōu)，Y）

（k-近鄰算法求得的距離，Y）Λ（相似性系數(shù)r越小時，N）?（求得實例的解為更優(yōu)，N）

7 相似性算法的算法分析

現(xiàn)在某個實例A有個n屬性，實例B有m個屬性，實例A的屬性用符號an表示，實例B的屬性bm表示。實例A的某個屬性a1都要與實例的B每個b1，b2，b3，bm進(jìn)行距離上的計算。d1表示a1與b1之間的距離，d2表示a1與b2之間的距離，d3表示a1與b3之間的距離……dn表示a1與bn之間的距離。

1）在k-近鄰算法中采用蠻力算法尋找最優(yōu)解總的次數(shù)

如果實例A與實例B之間存在比當(dāng)前的距離更小的距離，那么當(dāng)前的距離不是最小距離，因此要在n個距離中要找到最小距離，必須與全部的距離比較之后實例A才能夠確定該距離是否是最小距離，然而要確定該距離是否為最小距離需要比較的次數(shù)是次n-1。

如果實例A共有個n屬性值，為了在這n個距離值中找到最小距離，則需要拿d1與個n-1距離進(jìn)行比較，因此每一個屬性必須經(jīng)過n-1次比較之后才能找到該屬性的最小距離。

根據(jù)上述分析有以下的結(jié)論：

實例A有個n屬性值，然而實例A每個屬性比較的次數(shù)都是n-1，因此n個屬性總共需要比較的次數(shù)是n×(n-1)次。

2）采用本文提出的算法尋找k-近鄰算法的最優(yōu)解總的次數(shù)

由于實例A與實例B之間尋找的是最小距離，然而由于本文提出的算法是實例A的目前距離始終是最小距離，然而事實上d1不一定是最小距離。如果實例A尋找到比d1更小的距離之時d2，那么d2為實例 A目前的最小距離，假如d2為實例A目前的最小距離，但本文提出的算法是需要在n-2個距離的比較中尋找最小距離，那么此時需要比較的最大次數(shù)為n-2次。根據(jù)以上的分析有如下的結(jié)論：

（1）如果d3為實例A目前的最小距離，實例A需要在n-3個距離的比較中尋找最小距離之時，那么此時需要比較的最大次數(shù)為n-3次。如果dn為實例A目前的最小距離，dn需要在n-m個距離的比較中尋找最小距離，那么此時需要比較的最大次數(shù)為n-m次。

（2）因此本文提出的算法實例A要在n個屬性中找到每一個屬性的最小距離一般情況下需要比較的次數(shù)是：

說明：(n-1)+(n-2)+(n-3)+…+(n-m)，這里一共有 n個(n-1)，(n-2)，(n-3)，…(n-m)。

通過計算的公式：

3）蠻力尋找最優(yōu)解的算法和本文提出的尋找最優(yōu)算法的比較

（1）兩種算法運(yùn)行時所需的次數(shù)：

蠻力算法的運(yùn)行次數(shù)：（n-1)n。本文提出的算法運(yùn)行的次數(shù)：

（2）分析和討論：

當(dāng)n=6

蠻力算法的運(yùn)行次數(shù)：30次，本文提出的算法運(yùn)行的次數(shù)：6次。

當(dāng)n=14

蠻力算法的運(yùn)行次數(shù)：128次，本文提出的算法運(yùn)行的次數(shù)：14次。

當(dāng)n=24

蠻力算法的運(yùn)行次數(shù)552次，本文提出的算法運(yùn)行的次數(shù)：24次。

當(dāng)n=36

蠻力算法的運(yùn)行次數(shù)：1260次，本文提出的算法運(yùn)行的次數(shù)：36次。

當(dāng)n=58

蠻力算法的運(yùn)行次數(shù)：3306次，本文提出的算法運(yùn)行的次數(shù)：58次。

（3）根據(jù)以上的計算和分析有以下的結(jié)論：

蠻力算法的運(yùn)行次數(shù)：（n-1)n，本文提出的算法運(yùn)行的次數(shù)相比較之后可以知道：(n-1)n要大于，然而本文提出的算法運(yùn)行的次數(shù)要少于蠻力算法的運(yùn)行次數(shù)，算法要明顯優(yōu)于蠻力算法。

當(dāng)n的值越大，本文提出的算法運(yùn)行比較次數(shù)將越明顯小于一般性算法的運(yùn)行比較次數(shù)，因此本文提出的算法優(yōu)于一般性算法的程度更為明顯。

4）蠻力尋找最優(yōu)解的算法和特殊情況下本文提出的尋找最優(yōu)算法的比較

（1）如果需要判斷某個距離是否為實例A目前的最小距離，那么這個距離至少與1個距離或幾個距離比較過后才能確定。例如當(dāng)d2是實例A目前最小的距離，那么d2必須d1比較之后，才能夠確定d2是實例A目前的最小距離。

假設(shè)實例A的一個屬性或多個屬性都是以d2為目前的最小距離，那么實例A需要在n-2個距離中找到最小距離，這時實例A的每個屬性需要比較的次數(shù)都為n-2次，因此實例A的n個屬性總的比較次數(shù)是n(n-2)次。

（2）有以上的分析和討論可以有以下的結(jié)論：

如果采用蠻力算法在尋找最小距離時，即最優(yōu)解時需要比較總的次數(shù)為n(n-1)，而本文提出的算法，在某特殊情況下最大運(yùn)行次數(shù)為n(n-2)。將這兩種算法比較之后有以下的結(jié)論：n(n-1)-n(n-2)=n2-n-n2+2n=n＞0 ，n(n-1)＞n(n-2)，因此可以知道蠻力算法運(yùn)行的最大比較次數(shù)大于由本文提出的算法運(yùn)行時所需要的的最大比較次數(shù)，由此可知本文提出的算法優(yōu)于一般性的蠻力算法。

8 尋找最優(yōu)解的算法

1）使用k-近鄰算法計算實例A與實例B屬性之間的距離。

2）使用相似性算法對k-近鄰算法的解進(jìn)行計算，尋找較優(yōu)解或更優(yōu)解。

3）使用粗糙集中的決策系統(tǒng)對相似性算法的計算結(jié)果。

9 結(jié)語

本文參考了已有的智能算法之后將相似性計算算法，決策系統(tǒng)和k-近鄰算法這三種不同的算法融合到了一起，形成了一種新的尋找最優(yōu)解算法。該算法首次將相似性計算算法和決策系統(tǒng)這兩種算法在尋找最優(yōu)解的算法中進(jìn)行應(yīng)用，這是本文不同于其它算法的地方，也是本文的創(chuàng)新之處。本文提出的算法能夠與現(xiàn)有的智能性算法共同使用，起到相互補(bǔ)充的作用，但實際的效果需要在實際的應(yīng)用中進(jìn)行檢驗。

［1］TomM.Mitchell著.機(jī)器學(xué)習(xí)［M］.北京：機(jī)械工業(yè)出版社，2013.TomM.Mitchell.Machine learning［M］.Beijing：Mechanical Industry Press，2013.

［2］林關(guān)成.基于改進(jìn)K近鄰算法支持向量分類研究［J］.渭南師范學(xué)院學(xué)報，2012（2）：83-86.LIN Guancheng.Support Vector Classification Based on Improved K Nearest Neighbor Algorithm［J］.Journal of Weinan Teachers College，2012（2）：83-86.

［3］陸微微，劉晶.一種提高K-近鄰算法效率的新算法［J］.計算機(jī)工程與應(yīng)用，2008（4）：163-178.LU Weiwei，LIU Jing.A New Algorithm to Improve the Efficiency of K-Nearest Neighbor Algorithm［J］.Computer Engineering and Applications，2008（4）：163-178.

［4］桑應(yīng)賓，劉瓊蓀.改進(jìn)K-nn快速分類算法［J］.計算機(jī)工程與應(yīng)用，2009（11）：145-146.SANG Yingbin，LIU Qiongsun.An Improved K-nn Fast Classification Algorithm［J］.Computer Engineering and Applications，2009（11）：145-146.

［5］邵峰晶，于忠清，王金龍，等.數(shù)據(jù)挖掘原理與算法［M］.北京：科學(xué)出版社，2009.SHAO Fengjing，YU Zhongqing，WANG Jinlong，et al.Principles and algorithms of data mining［M］.Beijing：Science Press，2009.

［6］羅森林，馬駿，潘麗敏.數(shù)據(jù)挖掘理論與技術(shù)［M］.北京：電子工業(yè)出版時，2013.LUO Senlin，MA Jun，PAN Limin.Data Mining Theory and Technology［M］.Beijing：Electronic Industry Publishing，2013.

［8］胡清華，于達(dá)仁.應(yīng)用粗糙集計算［M］.北京：科學(xué)出版社，2012年6月.HU Qinghua，YU Daren.Application of Rough Set Computation［M］.Beijing：Science Press，June 2012.

［9］陳德剛.模糊粗糙集理論與方法［M］.北京：科學(xué)出版社，2013.CHEN Degang.Theory and Method of Fuzzy Rough Sets［M］.Beijing：Science Press，2013.

［10］朱梧槚，肖奚安.數(shù)學(xué)基礎(chǔ)與模糊數(shù)學(xué)基礎(chǔ)［J］.自然雜志，7（1980）：723-726.ZHU Wujia，XIAO Xi'an.Mathematical Foundation and Fuzzy Mathematics Foundation［J］.Natural J.，7（1980）：723-726.

［11］洪龍，肖奚安，朱梧槚.中介真值程度的度量及其應(yīng)用（I）［J］.計算機(jī)學(xué)報，2006（12）：2186-2193.HONG Long，XIAO Xi'an，ZHU Wujia.Mediation degree of truth value measurement and its application（I）［J］.Journal of computer，2006（12）：2186-2193.

［12］茹強(qiáng)喜，劉永.一種提高K近鄰分類的新方法［J］.電腦知識與技術(shù)，20106（8）：1989-1991.RU Qiangxi，LIU Yong.A New Method for Improving K-Nearest Neighbor Classification［J］.Computer Knowledge and Technology，20106（8）：1989-1991

［13］余小鵬，周翼德.一種自適應(yīng)K最近鄰算法的研究［J］.計算機(jī)應(yīng)用研究，2006（2）：70-72.YU Xiaopeng，ZHOU Yide.An Adaptive K-Nearest Neighbor Algorithm［J］.Application Research of Computers，2006（2）：70-72.

A Similarity Computing and Decision System Based on the Optimal Solution Algorithm

ZHU Lizhi
（Information Center，Nanjing University of Aeronautics，Astronautics，Nanjing 210016）

There is a variety of search for the optimal solution algorithm，k-nearest neighbor algorithm，ant colony algorithm and annealing algorithm is a classical intelligent algorithms，k-nearest neighbor algorithm in the search for the optimal solution algorithm has great application value，so the author of the k-nearest neighbor algorithm and rough set decision-making system research，an algorithm based on similarity computing algorithm of the optimal solution is put forward.The idea of this paper is the first to use k-neighbor algorithm to calculate the distance between the two instance attributes，followed by using similarity algorithm of k-nearest neighbor algorithm，finding the solution to calculate the property of solution and then use the decision-making system decision-making，is a general solution，or the optimal solution or more optimal solution，the similarity algorithm and decision system in the search for the optimal solution for application is the innovation of this article.

k-nearest neighbour algorithm，similarity algorithms，decision support systems

TP301

10.3969/j.issn.1672-9722.2017.11.016

Class Number TP301

2017年5月10日，

2017年6月30日

朱俚治，男，工程師，研究方向：計算機(jī)技術(shù)與信息安全。