邢光林，胡一然，孫 翀，帖 軍

(中南民族大學 計算機科學學院，武漢 430074)

改進的k中心點算法在茶葉拼配中的應用

邢光林，胡一然，孫 翀，帖 軍

(中南民族大學 計算機科學學院，武漢 430074)

為了提高茶葉拼配效率，節(jié)約人工成本，實現(xiàn)茶葉企業(yè)效益最大化，探討了將茶葉拼配問題建模成多維層次空間聚類問題，并通過定義多維概念分層空間中的相似性度量準則，提出了改進的k中心點算法求解最優(yōu)拼配方案，并引入Dewey編碼提高了求解效率.根據(jù)真實數(shù)據(jù)集上的實驗表明：同等實驗條件下較人工拼配方式而言，文中所提出的茶葉拼配智能化求解方法大大提高了茶葉企業(yè)工作效率和經(jīng)濟利益.

茶葉拼配；空間聚類；多維概念分層；Dewey編碼；k中心點算法

我國是最早種植茶樹、最早進行茶葉加工的國家，消費者對茶飲料的喜愛更是推動了茶葉市場的發(fā)展.在快速發(fā)展的茶葉市場中，茶葉拼配技術作為茶葉加工的一種工藝，多為商品茶加工企業(yè)采用，尤其是在我國非產(chǎn)茶區(qū)的北方茶葉加工企業(yè)，一般只能對茶葉進行拼配加工.茶葉拼配是指將兩種以上形質(zhì)不一，具有一定共性的茶葉，拼合在一起的作業(yè)，是一種常用的提高和穩(wěn)定茶葉品質(zhì)、擴大貨源、增加數(shù)量、獲取較高經(jīng)濟效益的方法[1].

傳統(tǒng)的茶葉拼配主要是依賴茶葉專家的經(jīng)驗，其拼配方式通常也取決于茶葉的品質(zhì)及數(shù)量.國內(nèi)已有眾多學者對茶葉拼配問題進行了深入研究，大部分研究在于高效機器的應用[2,3]和拼配技術的提高[4,5]等方面.這種傳統(tǒng)的人工拼配方式對于拼配人員的技術要求過高，同時由于茶葉加工企業(yè)眾多，不同企業(yè)因其茶葉質(zhì)量和數(shù)量的不同，對拼配而成的成品茶品質(zhì)要求也不同.這將導致拼配專家在茶葉拼配過程中需要花費大量時間和精力為不同的企業(yè)制定不同的拼配方案，更難以比較各種方案的成本并加以優(yōu)化，即使是對于同一企業(yè)，在茶葉品質(zhì)和庫存變化的情況下，也需要調(diào)整拼配方案.

近年來，隨著計算機技術的高速發(fā)展，傳統(tǒng)行業(yè)人工操作越來越多地被智能化系統(tǒng)所替代，在茶葉拼配中應用計算機技術將大幅提高工作效率[6]，降低企業(yè)成本.本文提出將改進的k中心點算法應用到茶葉拼配技術中，首先將茶葉拼配問題抽象為數(shù)據(jù)表的語義匯總問題，再建模成空間聚類問題，利用空間聚類匯總算法將相似的茶葉合并.傳統(tǒng)的空間聚類算法只適合歐氏距離度，而茶葉拼配問題屬性維度多為概念分層類型，因此本文提出了多維概念分層空間中的相似性度量準則，從而改進了k中心點算法.在數(shù)據(jù)預處理過程中，通過Dewey編碼快速將原始數(shù)據(jù)映射到多維層次空間的點集.本文提出的方法不僅為茶葉企業(yè)提供了一個通用的、低成本、高效率的茶葉拼配方案，同時也為企業(yè)的成本優(yōu)化決策提供了重要幫助.

1 問題描述

本節(jié)首先將茶葉拼配問題模型化為數(shù)據(jù)表的語義匯總問題，再對表語義壓縮進行約定和形式化，最后將茶葉拼配問題轉(zhuǎn)化為空間聚類問題，并提出多維概念分層空間中的距離度量.將茶葉拼配這一實際生產(chǎn)中的問題建模為聚類問題，能更好地利用數(shù)據(jù)挖掘的思想和技術對該問題進行高效求解.

1.1 茶葉拼配問題模型化

茶葉拼配問題的核心是合并形質(zhì)不一、具有一定共性的茶葉，本文將形質(zhì)不一、具有一定共性定義為“相似”，因此茶葉拼配工作可描述為合并相似的茶葉.對茶葉相似性的判斷實際是對茶葉品種、加工工藝等多方面信息的綜合考量.本文以茶葉的名稱、茶樹品種、加工工藝和產(chǎn)地這4方面的信息為例，將拼配前的原茶葉信息以數(shù)據(jù)表的形式表示，如表1所示，其中附加列ID用于唯一標識元組.

表1 茶葉信息Tab.1 Tea information

在表1中，每一種待拼配的茶葉用一個元組表示，拼配所需考量的信息用數(shù)據(jù)表中的屬性值表示，因此茶葉拼配問題可描述為數(shù)據(jù)表的縮減問題，即考慮語義因素的匯總數(shù)據(jù)表，使用少量“抽象”元組來表示大量“詳細”元組.

1.2 符號約定和形式化定義

本文的表匯總技術利用表中各個屬性的屬性值概念分層[7]對原始茶葉信息數(shù)據(jù)表進行元組泛化.屬性值概念分層是一種樹形層次結(jié)構，描述了屬性值域上的分類關系，文獻[7]對建立該結(jié)構的方法有說明，在此不做詳述.表1中的茶樹品種、加工工藝和產(chǎn)地三個屬性的概念分層如圖1所示，以分類型的屬性加工工藝為例，其屬性值可以從“加工工藝小類”泛化到層次較高的“加工工藝大類”.在概念分層結(jié)構中，節(jié)點的位置決定了語義的“詳細”程度和屬性值的泛化能力：位置越接近根節(jié)點的語義信息越少，而其泛化的范圍越大，任意節(jié)點能泛化以其為根的子樹內(nèi)的所有節(jié)點.

根據(jù)上述約定，下面給出屬性值泛化及元組泛化等相關形式化定義.

定義1(屬性值語義量)對于屬性a中的任意屬性值x，其語義量為x在概念分層中對應節(jié)點的層數(shù)，用ASemantic表示，即x.ASemantic=level(x).

定義4(元組間泛化關系)若對于任意兩個元組t1和t2，其第i個屬性值均有t1[i] ∠t2[i]成立，則稱t1可以泛化t2，用t1∠t2表示.

定義5(最優(yōu)泛化)給定屬性a的任意屬性值集Sa和屬性值x，若滿足：(1)Sa中的任意屬性值對應的節(jié)點均為ha中以label(x)為根節(jié)點的子樹上的葉節(jié)點；(2)不存在當Sa中的任意屬性值對應的節(jié)點均為ha中以label(x′)為根節(jié)點的子樹上的葉節(jié)點時，label(x′)子樹上的節(jié)點數(shù)大于label(x)子樹上的節(jié)點數(shù)，則稱x為Sa的最優(yōu)泛化屬性值，表示為x∠optSa.若泛化元組tc的每個屬性值均是元組Ts中所有元組對應屬性值集的最優(yōu)泛化屬性值，則稱tc是Ts的最優(yōu)泛化元組，表示為tc∠optTs.

定義6(語義損失)對于屬性a中任意兩個屬性值x1和x2，若存在關系x2∠x1，則其語義損失為x2與x1的語義量之差，用AInfoLoss(x2,x1)表示，即AInfoLoss(x2,x1) =x2.ASemantic-x1.ASemantic.對于任意兩個元組t1和t2，若存在關系t2∠t1，則其語義損失為t2與t1的語義量之差，用TInfoLoss(t2,t1)表示，即TInfoLoss(t2,t1) =t2.TSemantic-t1.ASemantic.

1.3 茶葉拼配轉(zhuǎn)換為空間聚類問題

根據(jù)1.2節(jié)中關于表語義匯總的相關約定和定義，本文給出1.1中模型化后的茶葉拼配問題的形式化定義: 給定原始茶葉信息表T和泛化元組后的元組個數(shù)k，構建滿足如下條件的匯總表T′：(1)T′中的任意元組可以泛化T中的「|T|/k?個元組；(2)泛化后的元組語義損失之和最小.

泛化過程中，Tx表示元組集的泛化元組集合，tx為Tx中具有最大語義量的泛化元組，則tx為元組集的最優(yōu)泛化元組.所以當原始表T中的分組確定后，用每個分組的最優(yōu)泛化元組來替換分組中的原始元組即可使T′語義量最大.由此可見，T′的質(zhì)量取決于T中的分組.本文將線性空間中表的元組表示為空間中的點，則表中元組的分組問題可被表示為多維空間中點的聚類問題.

在此本文可將茶葉拼配問題描述為：在多維空間中，將點集T聚類成k個子簇，每個子簇用一個點表示，并且使得語義損失最小，定義如下：

定義7(空間距離)對于T中的任意兩點t1和t2，稱其最優(yōu)泛化元組的語義量為兩點間的空間距離，用d(t1,t2)表示，即d(t1,t2) =t.TSemantic，其中t∠opt{t1,t2}.

2 基于k中心點聚類的茶葉拼配算法

針對茶葉拼配空間聚類問題，本節(jié)首先引入Dewey編碼，在原始數(shù)據(jù)中利用該編碼表示概念分層樹中的泛化關系，提高語義量的計算效率；隨后提出基于改進的k中心點算法高效地對空間中的原始數(shù)據(jù)點進行聚類.

2.1 Dewey編碼

Dewey編碼(點分十進制編碼)是一種快速樹編碼，已有超過一百年的歷史，常用于樹的索引及檢索.其基本思想是前綴編碼.本文根節(jié)點編碼設置為“0”，若節(jié)點t的編碼為“0……xx”，則其第i個子節(jié)點的編碼表示為“0……xxi”.如圖1所示，每個節(jié)點的Dewey編碼為其概念分層樹中每個節(jié)點右下角的數(shù)字.通過Dewey編碼標識節(jié)點可快速判斷概念分層樹中節(jié)點的分層關系和節(jié)點間的泛化關系，使用節(jié)點的Dewey編碼能快速計算點間的空間距離.Dewey編碼方案具有編碼效率高、解碼速度快的優(yōu)點，被廣泛應用于樹形結(jié)構編解碼.

以表1中的茶葉信息屬性值為例，本文在聚類過程中只考慮茶樹品種、加工工藝和產(chǎn)地這三方面信息，其Dewey編碼如表2所示.使用Dewey編碼后的屬性值語義量等于其編碼長度，元組語義量等于其屬性值語義量的累加和，如表2中t1.TSemantic= |011| +|012| + |0112| = 10.

表2 茶葉信息屬性值Dewey編碼Tab.2 The Dewey coding of tea information attribute value

給定元組集的Dewey編碼集，將該編碼集在各維屬性上做投影操作，所得字符串集的最長公共前綴是該元組集上最優(yōu)泛化元組的Dewey編碼.以表2中t2和t3為例，其最優(yōu)泛化元組用t23表示，則t23各屬性的Dewey編碼為{02,011,01}，在多維空間中，t2和t3間的空間距離為d(t2,t3) =t23.TSemantic= |Dewey(t23)| = 2+3+2 = 7.

2.2 基于k中心點的空間聚類算法

茶葉拼配空間問題的關鍵在于聚類過程中的元組劃分，k中心點算法[8,9]是一個常用的聚類算法，其劃分是基于最小化所有對象與其對應的參照點之間的相異度之和的原則來執(zhí)行的.本文采用k中心點的思想來求解茶葉拼配空間聚類問題.

k中心點聚類算法的基本思想可描述為：首先任意選擇原始點集中的k個對象為中心點，計算剩余對象與這k個點之間的距離，并將其分配到與其最近的中心點；然后通過多次迭代，反復用非中心點代替中心點并計算替換代價的方法，使聚類質(zhì)量達到最優(yōu).

根據(jù)上述思想以及本文所提出的多維概念分層空間中的距離度量，本文設計茶葉拼配求解算法如算法1.

算法1 TBBOK(T,K,Num)

Input:T, 原始數(shù)據(jù)元組；

K，輸出子簇的個數(shù)

Num: 最大迭代次數(shù)

Output:T′,拼配后數(shù)據(jù)元組

Begin

Initial(T);

N←0;

While (N

DT←InitDivision(T);

RPoint←RSelect(T);

S←ReplaceCost(RPoint,DT);

If (S<0)

Replace(RPoint,DT);

else

T′←DealWithOB(DT);

Break;

End If

N←N+ 1;

End While

End

算法中Initial(T)對聚類輸入進行初始化，完成對原始數(shù)據(jù)元組的編碼工作；N記錄了當前迭代次數(shù).DT為三元組(GCP,GCPCode,GPSet)的集合，GCP和GCPCode分別記錄了分簇中心點的ID和Dewey編碼，GPSet記錄分簇包含的點集，InitDivision函數(shù)完成對原始數(shù)據(jù)編碼集的初始化工作，即隨機選取k個點作為初始的中心點，指派每個剩余對象給離它最近的中心點所在的分簇.RSelect函數(shù)在原始數(shù)據(jù)點中隨機選擇一個非中心點對象.ReplaceCost計算選中的非中心點替換DT中某一中心點的代價，如果替換代價為負，使用RePlace函數(shù)完成替換工作，并形成新的簇.當k個中心點不再發(fā)生變化，或者迭代次數(shù)達到用戶設置的最大值時，算法結(jié)束.

假設算法輸入規(guī)模為n，輸出規(guī)模為b，則算法需要循環(huán)(n-b)次.每次循環(huán)至少遍歷一次數(shù)據(jù)，至多遍歷次數(shù)為數(shù)據(jù)的常數(shù)倍，因此每輪循環(huán)中的算法處理時間可以認為是O(n).故算法的執(zhí)行代價在最差情況下為O(n2).

3 實驗與分析

3.1 實驗環(huán)境

本文實驗的數(shù)據(jù)集采用真實數(shù)據(jù)集Tea Set，該數(shù)據(jù)集含有約50000條元組，選擇數(shù)據(jù)集中的3個屬性作為實驗對象，其屬性的相關信息描述見表3.實驗采用的硬件：主頻為1.6GHz的CPU以及1GRAM(DDR)；TBBOK算法使用CSharp語言,在VS.NET2005環(huán)境下實現(xiàn).

表3 Tea Set數(shù)據(jù)集描述

下文主要從算法執(zhí)行時間分析實驗算法.

3.2 實驗結(jié)果與分析

本文在不同樣本數(shù)(原始數(shù)據(jù)的元組數(shù))的情況下對TBBOK算法的執(zhí)行效率和人工拼配方式進行考察.實驗目的是比較拼配數(shù)據(jù)智能處理與人工處理方式效率的差異以及樣本數(shù)的變化對算法效率的影響.實驗結(jié)果如圖2所示.

根據(jù)圖2所示結(jié)果，對于104數(shù)量級的數(shù)據(jù)，使用拼配數(shù)據(jù)智能處理求解拼配方案時間上遠低于人工拼配.此外，隨著樣本數(shù)的增加，兩種拼配方式求解拼配方案的時間均呈線性增加，但總體來說，樣本數(shù)對算法運行效率的影響較小.因此，將茶葉拼配問題作為空間聚類問題進行智能化求解可大幅提高拼配效率，減少工作時間，節(jié)約企業(yè)成本.

圖2 人工拼配方式和智能拼配方式比較Fig.2 Comparison of artificial blending way and intelligent blending way

4 結(jié)束語

本文通過Dewey編碼將茶葉拼配問題中原始信息元組編碼成層次空間中的點，同時將茶葉拼配問題轉(zhuǎn)化為空間聚類問題，再結(jié)合k中心點算法的思想求解該問題.通過將茶葉拼配工作利用智能化數(shù)據(jù)處理方法進行求解，無論是在茶葉企業(yè)實際生產(chǎn)中運用，還是作為企業(yè)決策支持系統(tǒng)的一個重要組成部分，均比傳統(tǒng)的人工方法更高效、更精確，同時也為茶葉企業(yè)提供了一個通用的、低成本的茶葉拼配方案，具有社會和經(jīng)濟效益.

下一步的工作可考慮對該問題中原始數(shù)據(jù)的各屬性計入權重，使拼配工作更能滿足不同用戶的精

確需求；同時，對已有茶葉拼配方案進行學習和挖掘，利用半監(jiān)督學習求解茶葉拼配問題將是今后的研究重點.

[1] 青青柳岸. 茶葉的拼配技術工藝[EB/OL].( 2011-09-04). [2011-12-23]. http://blog.sina.com.cn/s/blog_442cf7e50100tf4j.html.

[2] 王國海. 滾筒勻堆機在茶葉拼配中的實踐[J]. 廣東茶葉, 2003(1): 31-32.

[3] 肖宏儒，朱志祥. 茶葉機械化加工裝備技術發(fā)展趨勢[J]. 農(nóng)業(yè)裝備技術, 2005, 31(6): 7-10.

[4] 施和森. 出口綠茶的拼配技術與品質(zhì)管理[J]. 中國茶葉, 1999 (5): 10-11.

[5] 童華榮，龔正禮. 茶葉拼配的混料設計研究[J]. 茶葉科學, 2004, 24(3): 207-211.

[6] 琚春華，王光明. 一個基于知識的規(guī)劃型出口茶葉拼配決策支持系統(tǒng)PTBDSS的研究與實現(xiàn)[J]. 計算機研究與發(fā)展, 1998, 35(2): 145-149.

[7] 金勝男. 基于多層關聯(lián)規(guī)則的概念分層知識庫中知識發(fā)現(xiàn)的研究[D]. 天津:天津大學, 2006.

[8] Han Jiawei, Kamber M. 數(shù)據(jù)挖掘概念與技術[M]. 范 明，孟小峰，譯. 北京：機械工業(yè)出版社, 2001.

[9] 劉金嶺. k中心點聚類算法在層次數(shù)據(jù)的應用[J]. 計算機工程與設計，2008, 29(24): 6418-6422.

ApplicationoftheImprovedk-MedoidsAlgorithminTeaBlending

XingGuanglin,HuYiran,SunChong,TieJun

(College of Computer Science, South-Central University for Nationalities, Wuhan 430074, China)

In order to improve the efficiency of tea blending, saving the labor costs and achieving the maximum profit for tea enterprise, we model the problem of tea blending as the spatial clustering based on multi-dimensional hierarchy. We define the similarity measure criteria in multi-dimensional conceptual hierarchy space to improve k-medoids algorithm and solve the optimal blending scheme. By introducing Dewey coding, we improve the solving efficiency. The experiment on real life dataset shows that, compared with the manual way under the same experimental conditions, the intelligent tea blending scheme proposed in this paper has greatly improved the working efficiency and economic benefits for tea enterprises.

tea blending; spatial clustering; multi-dimensional conceptual hierarchy; Dewey coding; k-medoids algorithm

2017-05-05

邢光林(1972-)，男，副教授，博士，研究方向：移動計算與分布式系統(tǒng)，信息安全，E-mail: xingguanglin@gmail.com

國家科技支撐計劃項目子課題(2015BAD29B01)；中央高?；究蒲袠I(yè)務費專項資金資助項目(CZP17007)

TP391

A

1672-4321(2017)04-0126-05