改進的AGNES算法在羽毛球技戰術分析中的應用

摘要:該文給出了數據挖掘中的層次聚類算法在羽毛球技戰術分析中的一個應用。根據羽毛球技戰術采集系統所采集的技術，動態產生技術路線，然后采用數據挖掘中改進了的AGNES層次聚類算法，對動態產生的技術路線進行數據挖掘。本文對數據預處理過程中的技術路線進行排序，以及數據的合并進行了研究和探討。

關鍵字:數據挖掘;層次聚類;AGNES;動態技術路線;技戰術分析

中圖法分類號:TP311文獻標識碼:A文章編號:1009-3044(2009)33-9343-03

Implementation and Application of Improved AGNES Algorithm on Technical-tactics Analysis of Badminton Match

ZENG Jia-jun

(Dept. of Computer Science， Tongji University， Shanghai 201804， China)

Abstract: An application of data mining hierarchical clustering algorithms to technical-tactics analysis of badminton match was proposed in this paper. According to the technique which was gathered by technical-tactics gathering system of badminton match， and technical route which was dynamically produced， we could dig out significative information through them with an improved AGNES hierarchical clustering algorithms. This paper focused on sorting dynamically technical routes in data preprocessing and merging data.

Key words: data mining; hierarchical clustering; AGNES; dynamic technical route; technical-tactics analysis

羽毛球比賽項目由于其復雜的技戰術體系和在比賽中的靈活運用，因此技戰術是決定比賽勝負的主要因素。目前，國內外羽毛球項目比賽技戰術分析主要是傳統的比賽觀察與統計分析，而在智能處理與分析系統方面的研究還幾乎為空白。計算機輔助羽毛球比賽技戰術統計分析是減少了人工數據采集的工作量，能夠對前后關聯的單個技術，按照給定的規則，進行關聯，并能自動地對動態關聯生成的技術路線進行抽取、轉換和挖掘分析，并運用各種圖表將挖掘結果直觀的展示。

數據挖掘(Data Mining簡稱DM)是用算法來抽取信息和模式，它是知識發現(Knowledge Discovery in Databases，簡稱KDD)過程的一個步驟。一般認為數據挖掘是指從大量的、不完全的、有噪聲的、模糊的、隨機的數據中，提取出隱含在其中的、人們事先不知道的、但又是潛在有用的信息和知識的過程。本文主要研究凝聚的層次聚類算法在基于動態技術路線的羽毛球技戰術分析中的研究和應用。

1 凝聚的層次聚類

凝聚的層次聚類:自底向上的策略，首先將每個對象作為一個簇，然后合并這些原子簇為更大的簇，直到所有的對象都在同一個簇中，或則滿足終止條件。

AGNES(Agglomerative Nesting)是凝聚的層次聚類算法，如果簇C1中的一個對象和簇C2中的一個對象之間的距離是所有屬于不同簇的對象間歐式距離中最小的，C1和C2可能被合并。這是一種單連接方法，其每個簇可以被簇中的所有對象代表，兩個簇之間的相似度由這兩個簇中距離最近的數據點對的相似度來確定。

1.1 算法描述

輸入:包含n個對象的數據庫，終止條件簇的數目k

輸出:k個簇

1) 將每個對象當成一個初始簇

2) Repeat

3) 根據兩個簇中最近的數據點找到最近的兩個簇

4) 合并兩個簇，生成新的簇的集合

5) Until達到定義的簇的數目

1.2 算法性能

1) 簡單，但遇到合并點選擇困難的情況。

2) 一旦一組對象被合并，不能撤銷

3) 算法的復雜度為O(n2)，不適合大數據集計算

2 算法應用

下面以羽毛球為例，介紹改進的AGNES算法在基于動態技術路線的技戰術分析中的應用。

為了便于后面數據分析和挖掘，首先把復雜的專業技術名稱，通過一張映射表，映射成為技術代碼。

2.1 技術數據的表示

為了后面能夠動態生成技術路線，首先得在比賽視頻數據采集階段生成單個技術。擊球者單個技術數據結構SingleTech表示為{技術信息id，比賽編號，比賽局數，比賽回合數，當前拍數，選手A1得分，A2得分，B1得分，B2得分，此拍擊球者，落球位置，下個落球位置，技術號，下個技術，態勢，視頻位置，此回合發球者，得失分情況，心理狀態，體能狀態}=={id，matchnum，game，round，strike，aonescore，atwoscore，bonescore，btwoscore，hitplayer，position，nextpos，technum，nexttechnum，status，videolocation，serviceplayer，winorlose，psychology，bodyfunc}。

2.2 動態技術路線數據的表示

動態技術路線數據結構DynaTechRout為{記錄編號，比賽編號，隊員id，線路編號，比賽場次，比賽回合，線路得分數，線路失分數，線路定位，輸贏，擊球狀態，關聯拍數，路線數}=={routeid，matchnum，playerid，techroutenum，game，round，wintimes，losttimes，techroutelocations，winorlose，hitstatus，relevantstrikecount，currtechroutecount}的結構體。結構體包含Delete，Update，Compare操作。

其中路線定位是指在所挖掘的所有比賽中，該技術路線出現的位置集合，數據結構可表示為{比賽編號-比賽場次-比賽回合-輸贏情況;比賽編號-比賽場次-比賽回合-輸贏情況;… }。

2.3 AGNES層次凝聚算法具體應用的變體

2.3.1 數據采集

該羽毛球技戰術系統為了給后面階段的數據挖掘提供所需要的數據源，就必須把整個比賽的視頻信息，分解為每一個技術動作，并用SingleTech類型結構把它記錄下來。

2.3.2 數據預處理

1) 把數據采集階段得到的每個技術，按照挖掘要求，在每一回合內，動態組合成技術路線。

動態生成技術路線原則:

某個運動員在所選定的所有比賽中，

① 每一回合中，出現某個技術后，往前關聯n個技術(拍)，以及當前技術的得失分情況

② 每一回合中，出現得勝球后，與前n個技術(拍)的關聯

…

2) 把動態生成的技術路線進行排序。先按照動態生成的技術路線的總拍數排序，然后按照動態技術路線編號排序。

先對動態技術路線按照DynaTechRout結構中本技術路線拍數屬性，進行箱排序。然后按照DynaTechRout結構中技術路線編號屬性，進行插入排序。

算法的具體實現如下:

Input:數據預處理步驟1，所產生的未經過排序的動態生成的技術路線集合和該集合中，技術路線總數，關聯拍數:UnsortedTechRout[Total]，Total，RelevantStrikeCount

Output:已經排序的動態生成的技術路線集合:SortedTechRout[Total]

//數組UnsortedTechRout和SortedTechRout均是DynaTechRout結構體類型.

typedef struct{

int nUnsortTechRoutIndex;

SortedNode * npNext;

}SortedNode;

typedef SortedNode * SNPoint;

SNPoint snpArrTechRout = new SortedNode[RelevantStrikeCount];

for(int i = 0; i < Total; i++)

{//按照技術路線拍數屬性，進行箱排序

SortedNode *snpCurr = snpArrTechRout[UnsortedTechRout[i].currtechroutecount - 1];

SortedNode *snpNext = NULL，*snpPrevious = NULL;

//按照技術路線編號屬性，進行插入排序

1) 找到插入新節點的插入點

2) 插入新節點

if(snpCurr->npNext == NULL)

{

//當前節點為最后一個節點的插入情況

}

else

{//不是最后一個節點的插入情況

SortedNode *snpNewAdded = new SortedNode;

snpNewAdded->nUnsortTechRoutIndex = i;

snpPrevious->npNext = snpNewAdded;

snNewAdded->npNext = snpCurr;

}

}

/*把數組UnsortedTechRout中的元素按照數組snpArrTechRout所排序復制到數組SortedTechRout*/

for(int i = 0; i < RelevantStrikeCount; i++)

{

SortedNode *snpCurr = snpArrTechRout[i].npNext;

while(snpCurr)

{

1) 把當前節點中所指引的數組UnsortedTechRout中的元素復制到數組SortedTechRout

2) 指針往后走一步

}

}

動態技術路線排序總的時間復雜度為O(n2/d)，其中n為集合元素個數，d為關聯的拍數。它沒有對象移動問題，主要是通過連接指針的修改以實現對象的邏輯有序，所以計算時間主要是對關鍵碼的比較次數。

2.3.3 數據挖掘

根據算法的原理，設計在羽毛球技戰術比賽中動態技術路線挖掘的算法如下:

Input:數據預處理中的步驟2，所產生的已經排序的動態生成的技術路線集合和該集合中，技術路線總數:OriginalTechRout[Total]，Total

Output:每種技術路線的在挖掘范圍內的總使用次數，以及得分率和失分率.

//數組OriginalTechRout和RetMergeTechRout均是DynaTechRout結構體類型.

int nTechRouteCount，nWinCount，nLoseCount;

//nTechRouteCount 代表該技術路線總使用次數

//nWinCount代表該技術路線總得分次數

//nLoseCount代表該技術路線總失分次數

Int nCurrIndex，nNextIndex;//nCurrIndex指向當前記錄，nNextIndex指向后一個記錄

nCurrIndex = 0;

for(int i = 1; i <= Total; i++)

{

if(OriginalTechRout[nCurrIndex]與OriginalTechRout[nNextIndex]中本技術路線拍數是否相同 技術路線編號是否相同)

{

1) 把nNextIndex所指的記錄合并到nCurrIndex所指的記錄，包括路線定位，總使用次數，總得/失分次數

2) 把nNextIndex所指的記錄從OriginalTechRout集合中刪除，令nNextIndex指向剛才所刪記錄的后面一條記錄

3) 更新OriginalTechRout集合

}

else

{ nCurrIndex = nNextIndex;

nNextIndex++;

}}

動態技術路線合并挖掘，總的時間復雜度為O(n)，其中n為集合元素個數。因此改進后的AGNES算法用于動態技術路線的挖掘，其算法總的時間復雜度為 O(n2/d)。并且改進后的算法，在動態技術路線向前/向后關聯拍數越多，其算法效率提高越大。

3 實驗結果

該實驗數據的來源為林丹于08年奧運會的三場羽毛球比賽。按照挖掘條件“出現得勝球后與前2拍之間的關聯”挖掘后部分結果如表1所示。

從挖掘結果表中，可以看出，當林丹使用“左區發網前1號位”技術的時候，其主動得分的機率比較大。

4 結束語

將計算機技術和數據挖掘算法應用于羽毛球技戰術分析，相比于傳統方法，能夠基于更大量的歷史比賽信息，對羽毛球運動員的技戰術特點進行分析。對于臨場比賽過程中，能夠更好和跟準確的幫助教練和運動員做出技戰術調整。對于比賽前的備戰，則能夠更全面的為提出運動員正對性的專項訓練。當問題規模達到一定程度的時候，其算法執行效率還需要改進。

參考文獻:

[1] HAN Jiawei，KAMBER Micheline.數據挖掘概念與技術[M].孟小峰，范明，譯.北京:機械工業出版社，2007.

[2] 張雨佳，趙會群，吳杰偉.數據挖掘算法在排球比賽技戰術分析中的應用研究[J].計算機應用，2006，26(12):3027-3029.

[3] 高洪歌，趙會群.關聯規則挖掘在乒乓球比賽技戰術分析中的應用[J].北方工業大學學報，2006，18(1):15-20.

[4] DING C.，HE Xiaofeng.Cluster merging and splitting in hierarchical clustering algorithms[C].IEEE International Conference 2002:139-146

[5] 沈潔，趙雷，楊季文，等.一種基于劃分的層次聚類算法[J].計算機工程與應用，2007，43(31):175-177.

[6] BOHM C.，KREBS F..high performance data mining using the nearest neighor join[C].IEEE International Conference，2002:43-50.