朱俚治

（南京航空航天大學信息中心 南京 210016）

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

朱俚治

（南京航空航天大學信息中心 南京 210016）

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

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

1 引言

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

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

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

2 k-近鄰算法

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

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

3 k-近鄰算法的實現

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

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

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

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

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

4 相似性計算法

4.1 相似性函數及其實例屬性間的距離

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

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

（1）dn-1為實例A與實例B屬性之間的一種距離，該距離的大小為當前已知的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）關于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）當實例 A與實例B屬性之間的距離為dn＜dn-1時：

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

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

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

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

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

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

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

2）對相似性系數r的討論：

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

（1）當相似性系數r的值小于1時：

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

（2）當相似性系數r的值大于1時：

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

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

4.3 相似性計算的相似系數

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

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

在實際應用中存在一大類任務：給定一組有特征描述的樣本和樣本的類別，需要通過一個學習算法從該組本文中學習一個分類函數，實現從特征到分類的映射，粗糙集理論中稱該數據集為信息系統(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為信息函數，表示對每一個x∈U，a∈A，f(x，a)∈Va。 當 系 統(tǒng) 中 屬 性 集A=C∪D，C∩D=Φ 其中C為條件屬性集，D為決策屬性時，該信息系統(tǒng)也被稱為決策表［7～9］。

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

由于決策條件屬性值的不同，因此能夠產生不同的決策屬性，事實上正是由于不同的決策的屬性值，產生了不同的決策結果，這些不同的決策結果能夠將不同屬性的樣例進行有效的分類［8～9］。條件屬性的屬性值決策規(guī)則的內涵，是決策系統(tǒng)做出決策結果的重要決定因數［8～9］。

6.1 值域和屬性集

1）域：

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

2）屬性集：

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

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

6.2 實例A解的屬性決策表

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

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

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

2）當相似性系數r越小時，決策屬性值為Y，否則決策屬性值為N。

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

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

決策規(guī)則：

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

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

7 相似性算法的算法分析

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

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

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

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

根據上述分析有以下的結論：

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

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

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

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

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

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

通過計算的公式：

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

（1）兩種算法運行時所需的次數：

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

（2）分析和討論：

當n=6

蠻力算法的運行次數：30次，本文提出的算法運行的次數：6次。

當n=14

蠻力算法的運行次數：128次，本文提出的算法運行的次數：14次。

當n=24

蠻力算法的運行次數552次，本文提出的算法運行的次數：24次。

當n=36

蠻力算法的運行次數：1260次，本文提出的算法運行的次數：36次。

當n=58

蠻力算法的運行次數：3306次，本文提出的算法運行的次數：58次。

（3）根據以上的計算和分析有以下的結論：

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

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

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

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

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

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

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

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

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

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

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

9 結語

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

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

［2］林關成.基于改進K近鄰算法支持向量分類研究［J］.渭南師范學院學報，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］.計算機工程與應用，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］桑應賓，劉瓊蓀.改進K-nn快速分類算法［J］.計算機工程與應用，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］邵峰晶，于忠清，王金龍，等.數據挖掘原理與算法［M］.北京：科學出版社，2009.SHAO Fengjing，YU Zhongqing，WANG Jinlong，et al.Principles and algorithms of data mining［M］.Beijing：Science Press，2009.

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

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

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

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

［11］洪龍，肖奚安，朱梧槚.中介真值程度的度量及其應用（I）［J］.計算機學報，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］茹強喜，劉永.一種提高K近鄰分類的新方法［J］.電腦知識與技術，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］余小鵬，周翼德.一種自適應K最近鄰算法的研究［J］.計算機應用研究，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日

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