模糊曼哈頓距離加權最優粒度選擇算法

李璐,李寶霖,李麗紅

(1. 華北理工大學 理學院,河北 唐山 063210;2. 河北省數據科學與應用重點實驗室,河北 唐山 063210;3. 唐山市數據科學重點實驗室,河北 唐山 063210)

引言

粒計算理論起源于信息粒概念,1979年由Zadeh[1]提出,簡化處理抽象復雜問題,一經提出便成為熱點。粒計算的確切概念是在1996年由Lin[2]提出,該理論的面世標志了一種多角度分析處理問題的方法產生,有助于更好地給出解決問題方案。Lin[3]隨后完善了該理論,并討論了其發展前景與方向,其中指出粒計算理論中,如何劃分粒層以及粒層的選擇問題是重中之重,國內外專家學者也對此進行了深入的討論。吳偉志等[4]討論了在不完備多粒度決策系統中如何找尋最優粒度。劉鳳玲[5]提出了在現實背景下的多粒度信息系統如何找尋最優粒度。李金海[6]將信息熵融合作為找尋最優粒度標準。

三支決策思想與中國傳統中庸思想有著不可分割的聯系,"中"被理解為"適當",決策思維符合人類思維方式,三支決策后樣本被分到3個域中,對不同的部分采用不同的處理策略,分別采取接受、延遲和拒絕行為。三支決策與粒計算融合發展是必然的,研究目標是將問題分解為多個角度、多個層次進行思考,三支決策模型的拓展模型之一是序貫三支決策模型。序貫三支決策[7,8]從粒計算角度出發,由粗粒度轉化為細粒度解決問題,延遲域中對象進一步被決策,在醫學、圖像、工程、屬性約簡、管理等方面已有廣泛應用[9,10]。顧沈明等[11]在多尺度信息系統中利用屬性及局部最優得到廣義決策最優粒度。Yang等[12]通過優化得到基于代價敏感的序貫最優粒度。Cheng等[13]基于序貫三支決策快速獲取最優尺度組合,李敏等[14]基于代價變化,引入可拓集方法,結合三支決策思想提出最優粒度選擇模型,張清華等[15]提出基于懲罰函數并結合序貫三支決策的最優粒度選擇方法。

現有最優粒度選擇方法大多在信息系統中利用靜態指標度量信息,如利用重要度方法選擇來看,存在數據冗余或未考慮各屬性間關系的問題。其次存在多使用一般性數據集,未能更符合實際應用場景的問題。為此,本研究提出了一種?；臻g下基于模糊曼哈頓距離加權的個性化最優粒度選擇方法。它實際上是一個三級結構,采用三支決策的三級思維方式。具體來說,它首先結合隸屬函數與曼哈頓距離,定義了模糊曼哈頓距離來重新計算屬性間的關聯程度;然后,放棄使用手動編輯的粒度,而利用自身屬性距離空間產生的數據?；?可以減少手動編輯粒度所導致的隨機性、不確定性甚至冗余。最后,分析數據分類結果,以其作為粒度選擇基礎,驗證算法有效性,實現對數據的最優粒度選擇,并以同物不同級數據作為實驗數據,驗證算法的可行性,將為樣本選擇可優化的最優粒度提供一種新的思路。

1 相關知識

1.1 三支決策

三支決策是將論域通過閾值劃分為獨立的三部分,每一個部分采取相應的行動,若樣本條件概率值大于上近似閾值,則劃分到接受域中;若其小于下近似閾值,則劃分到拒絕域中;若其在值域范圍內,需要等待更多信息對樣本做出判斷,則劃分到延遲域中。

定義1[16]給定信息系統S=(U,AT,V,f),U是論域,即需要處理的樣本對象,AT代表屬性集,是有限集合,C是條件屬性,D是決策屬性,V是屬性AT的值域,f:U×AT→V是一種映射,對于a∈AT,x∈U,f(x,a)∈Va,任一子集滿足φ≠H?AT,則在U上的等價關系為id(H)={(x,y)∈U×U|f(x,q)=f(y,q),?q∈H}。

定義2[17]給定信息系統S=(U,AT,V,f),λPP,λBP,λNP為樣本屬于決策類并且被分到正域、邊界域、負域時的決策風險代價,λPN,λBN,λNN為樣本不屬于決策類并且被分到正域、邊界域、負域時的決策風險代價。當樣本x屬于決策類時,其條件概率為P(X|x)=p,此時樣本x劃分到3個域的決策風險代價分別是:

正域:λPPp+λPN(1-p),邊界域:λBPp+λBN(1-p),負域:λNPp+λNN(1-p)

定義3[17]給定信息系統S=(U,AT,V,f),設狀態空間Θ=(D,D),表示對象x是是否屬于集合D,樣本xi屬于決策類D的條件概率為樣本構成的所有概率集合為P,當P(X|xi)=pi≥α時,樣本xi∈P1,即接受域;當β

由于P(X|x)+P(X|x)=1,λPP=λNN=0,同時λPP<λBP<λNP,λNN<λBN<λPN,(λPN-λBN)(λNP-λBP)>(λBP-λPP)(λBN-λNN),即:

(1)

(2)

1.2 廣義三支決策

廣義三支決策的概念被適時提出[18]針對的則是更加復雜、不確定和動態的數據集,相比于狹義,后者更強調對原有概念更深層次、更廣范圍的詮釋。二者聯系如圖1所示。

圖1中以垂直結構直觀地展示出了三支決策整體脈絡。從上到下,代表由廣至狹的三支決策;自下而上,由靜而動的三支決策。在現實中,決策分析一開始獲得的信息往往是不充分的,決策需要信息的更新和補充,由此序貫三支決策的概念被提出。

1.3 模糊曼哈頓距離

曼哈頓距離中的距離計算公式是將兩點坐標的 坐標相減取絕對值, 坐標相減取絕對值后再加和,用以度量樣本的相似程度。模糊集合描述的對象屬性邊界不分明,這一概念用于處理模糊性現象,被廣泛應用到數據預處理中。

定義4[19]設U為論域,U上的一個模糊集A表示?x∈U,有指定數μA∈[0,1],則稱x對A的隸屬程度,映射μA:X→[0,1],x→μA(x)稱為A的隸屬函數。設T(X)表示X上的一切模糊子集集合,則T(X)是由μ:X→[0,1]組成的函數空間。

定義5給定一個信息系統S=(U,AT,V,f),其中:AT=C∪D,C代表條件屬性集,D代表決策屬性集。在n個樣本中,μi(m)為第m個樣本在屬性i上對應的隸屬度,d(i,j)表示屬性i與屬性j間距離。定義屬性間模糊曼哈頓距離:

(3)

2 ?；臻g構造

數據集所包含的有效信息如表1所示。

表1 信息系統

數據集中有多個指標,該算法實施以屬性權重為基礎?；?構建粒層空間。下面將介紹具體步驟。

Step1:計算屬性重要度

步驟一:指標標準化處理

由于各指標量綱不同,且指標有正負之分,正負代表含義不同,正向指標數值越高越好,反之越低越好。因此為統一計量單位,對數據標準化處理。

其中,x*(i,j)為第i個樣本第j個評價指標值,xmax(i,j)為所有樣本中第j個評價指標最大值,xmin(i,j)為所有樣本中第j個評價指標最小值。

步驟二:熵權法計算屬性重要度并輸出

Step2:計算屬性間關系

步驟一:對原始數據模糊化處理

(4)

a是樣本集中各屬性的最小值,得到各屬性模糊隸屬度和消除量綱的矩陣。

Step3:構建?？臻g

根據模糊矩陣R,構建有序樣本的?？臻g,即根據d(i,j)的大小依次聚類,依據屬性重要度和距離加權,構建粒層。

3 模糊曼哈頓距離加權最優粒度選擇算法

粒計算以粒為基本單位,可利用屬性指標劃分得到不同粒層。該項研究采用模糊思想將數據模糊化處理后,構建不同層次空間,描述屬性或樣本之間的等價關系,應用多種算法框架分析分類結果,獲得最佳粒層空間上的優化指標。算法步驟

Step1:依據上述方法得到屬性模糊距離矩陣R。

Step2:構建粒層,首先在待分屬性中選取屬性重要度最低屬性放于拒絕域;其次選取與重要度最高屬性的距離從小到大計算平均重要度,選取平均重要度最高的距離,構建分類模型,將屬性放入接受域中;其余屬性放入延遲域。

Step3:將延遲域中屬性繼續按上述步驟構建層次?？臻g,分別用精確率、召回率及F1值檢驗所選擇的最優粒度,用以佐證其有效性。

4 仿真與應用

4.1 實驗準備

仿真實驗環境為:Python編程;

硬件環境:Intel(R) Core(TM) i5-10210U;16GB;

軟件環境:操作系統:Windows 10 家庭中文版;

解釋器:Python3.8,使用Python編程。

4.2 案例分析

以長江經濟帶省級行政區為研究區,綜合分析后選取16個指標,如表2所示。其中,指標性質為"正"代表指標為正向指標,指標值越大越好;指標性質為"負"代表指標為負向指標,指標值越小越好。

表2 長江經濟帶水資源評價指標

(1)指標標準化處理后,根據熵權法計算屬性重要度排序,結果如表3所示。

表3 屬性重要度排序

(2)計算各屬性間模糊曼哈頓距離,建立模糊矩陣R。

(3)第一次循環時在待分屬性中選取屬性重要度最低的"建成區綠化覆蓋率"屬性放于拒絕域;選取與重要度最高屬性的距離從小到大計算平均重要度,本次選取平均重要度最高的距離為1.926,得到屬性"萬元GDP用水"、"每萬人擁有公共交通數量"、"新能源發電占比"、"工業固體廢物綜合利用率"、"城市污水處理率"、"工業增加值率"、"第三產業產值占比"、"森林覆蓋率"、"空氣質量優良天數比例"放入接受域中,以不同算法為分類工具,構建分類模型計算準確率;其余屬性放入延遲域。

(4)第二次循環時在待分屬性中選取屬性重要度最低的"萬元GDP化學需氧量排放量"屬性放于拒絕域;選取與重要度最高屬性的距離從小到大計算平均重要度,本次選取平均重要度最高的距離為3.924,得到屬性"人均GDP"、"科教投入占GDP比重"放入接受域中,以不同算法為分類工具,構建分類模型計算準確率;其余屬性放入延遲域。

(5)第三次循環時在待分屬性中選取屬性重要度最低的"萬元GDP能耗"屬性放于拒絕域;選取與重要度最高屬性的距離從小到大計算平均重要度,本次選取平均重要度最高的距離為3.786,得到屬性"萬元GDP二氧化硫排放量"放入接受域中,以不同算法為分類工具,構建分類模型計算準確率。

根據每一輪選擇的接受域屬性,以ADABOOST、XGBOOST、隨機森林3種算法構建分類模型計算準確率,得到分類結果,證明其可行性。如圖2所示,縱坐標為準確率,橫坐標為循環次數。

圖2 長江經濟帶水資源準確率

由圖2準確率可知,三個算法下整體準確率達到0.8,驗證了算法的有效性,當t=1時3個算法分類準確率均為最高值,因此選擇第一粒層作為最優粒層,此時接受域中的屬性為待優化屬性。

圖3直觀展示出不同粒度下所需優化的屬性個數變化情況,黃色表示待決策屬性個數,綠色表示待優化屬性個數,黑色表示拒絕域中屬性個數。

圖3 長江經濟帶水資源需優化屬性變化情況

綜合3個學習算法反應結果,在第一次循環后準確率相對較好,此時再次通過F1值對分類結果進行驗證,證明其有效性。通過圖4對F1值走勢分析,XGBoost算法下F1值整體波動不大,AdaBoost、隨機森林算法下第一輪結束后F1值最高,綜上選擇第一粒層為最優粒層,當前粒層屬性為待優化屬性。

圖4 長江經濟帶水資源數據F1值

綜合圖中數據顯示,第一次循環結束后分類精度普遍較高,驗證了算法的有效性。所以對于優化長江經濟帶發展戰略在"控污"方面,可以優化的指標有萬元GDP用水量、工業增加值率、人均擁有公共交通數量、新能源發電占比、工業固體廢物綜合利用率、城市污水處理率、第三產業產值占比、森林覆蓋率和空氣質量優良天數比例。

5 結論

(1)利用屬性間關系選擇粒度,結合模糊曼哈頓距離構建層次粒層空間,可以有效節約時間成本,且可降低對分類結果的影響。

(2)基于模糊曼哈頓距離加權最優粒度選擇算法在保證數據完整的前提下為滿足不同用戶的不同需求,針對不同類別,控制一定成本的情況下,做到對數據的全方面優化提升,從決策系統中獲取最優粒度。但該項研究未體現序貫過程中代價變化,因此如何自動獲取決策過程代價變化確定最優粒層是未來研究方向。