動態增量聚類算法在足球運動員跑動能力挖掘中的應用

尹 倩,張 翠

(1.安徽體育運動職業技術學院, 安徽 合肥 230051; 2.安徽農業大學經濟技術學院,安徽 合肥 230011 )

動態增量聚類算法在足球運動員跑動能力挖掘中的應用

尹 倩1,張 翠2

(1.安徽體育運動職業技術學院, 安徽 合肥 230051; 2.安徽農業大學經濟技術學院,安徽 合肥 230011 )

以聚類技術為手段，對足球運動員跑動類型進行挖掘分析，主要工作包括：針對實際跑動數據動態增加的特點，提出動態增量聚類算法應用在訓練跑動能力挖掘研究中；對聚類數據來源和數據類型等進行一系列的處理；對所提出的算法進行了實驗和驗證.結果表明，此方法符合足球訓練技術特點，挖掘出的知識智能且準確，具有一定的應用價值.

動態數據集; 增量聚類; 跑動加速度

足球運動是一項要求技術和速度能夠很好結合的體育項目，足球的技術要有跑動速度作為前提和保證，足球運動員在比賽的過程中要做大量的起動、急轉、急停、變向、變速、轉身等動作，這就要求運動員具有出色的瞬間速度、加速度、制動速度和最高速度.然而現有訓練方式全憑教練員肉眼和經驗判斷，難以深入認識其本質[1].

在足球訓練跑動過程中，教練希望挖掘發現不同運動類型的小球員，并從類別中發現其肉眼無法發掘的隱含的指標特征.教練員很難憑肉眼實時掌握小球員跑動速度、瞬時加速度等指標，因此本文基于已有智能采集技術得到的足球訓練數據[2]，對采集到的小球員加速度，利用數據挖掘中的聚類算法進行初步挖掘分析各球員的技、戰術類別和綜合實力.球員跑動是動態變化的，此外，在整場比賽中產生的數據量是巨大的，因此如何對動態且數據量巨大的數據樣本快速高效地聚類成為本文研究重點內容.

1 聚類算法及其在足球領域的應用

1.1 聚類算法

數據挖掘技術用于從大量繁雜數據中挖掘分析隱含的潛在的重要信息，其中的聚類算法就是根據數據特征挖掘出數據間相似性，將相似數據(相似距離越近認為數據越相似)聚為一類.在概括出每個類的特點的同時，亦可集中注意力對特定的某些類做進一步的分析[3].

常用聚類算法分為劃分方法(k均值、k中心等)、基于密度的方法、基于層次的方法等.

1.2 增量聚類算法

傳統聚類算法均為針對靜態數據集的，而對于時刻更新變化的動態數據卻無法高效處理.因此，增量聚類算法[4-7]應運而生.其在原有聚類結果基礎上，對于新的數據集，分析新數據集與原有聚類結果的關系和影響，運用增量聚類算法對兩者進行迭加，得到最終聚類結果，避免了對于大量原有數據集的重復計算，大大提高效率，做到了實時有效處理.

1.3 足球領域聚類分析

已有聚類應用在足球信息挖掘的研究眾多[8-12]，但均為針對觀看足球視頻肉眼所記錄的數據進行靜態的聚類挖掘，此類研究只能比賽結束后觀看分析視頻且完全取決于肉眼判斷, 具有嚴重滯后性且大量隱含信息無法憑肉眼發掘，不能實時真實反映訓練技術指標.因此，如何實時采集挖掘分析運動員訓練跑動數據進而分析其技戰術類型很有必要，但此項研究未見相關研究的報道.

2 原始數據處理

2.1 原始數據采集

本文數據采集基于文獻[2]無線采集技術基礎上，將三維加速度傳感器綁定在足球運動員腳踝部位，獲取其三維(X,Y，Z三個維度方向)加速度(如圖1).可以看到X,Y,Z任一方向加速度突然增加，反應了運動員的瞬時爆發力.任兩個方向之間的突然加速度變化，反應了運動員此時身體(本文為小腿部位)的瞬時轉向程度.

圖1 小球員小腿部位在跨跳動作時三維加速度

圖1顯示出某一小球員在訓練時跨跳動作時三維加速度值(X,Y,Z三個方向)，單位為G，轉換到物理單位1G=9.8m/s2.可以看到靜止時，加速度不變.當跨跳時，會大幅急升或急降，特別是Z方向會出現短暫峰值.

2.2 聚類樣本

圖2顯示出某小學校園足球11名球員訓練時通過數據采集裝置采集到的三維加速度數據(原始數據為加速度數值大小,此處為直觀展示,將任一名球員加速度大小通過繪圖軟件顯示出來).

圖2 任一球員開始約5分鐘加速度數值直觀展示(約3000條數據)

由于篇幅有限，以上僅為該球員在約5分鐘時間范圍內的腳踝部位加速度數據.可以看到，在開始的5分鐘內加速度變化較大有多處，且最大加速度達到8G，相當于接近80 m/s2.所以無論從大小和頻率來看，均屬積極型隊員，但是隨著足球訓練時長的延長，各球員加速度狀態是不斷變化的.因此，實際聚類指標為11名球員在時長90分鐘訓練中的三維加速度的聚類樣本.

2.3 聚類距離計算

在聚類算法之前，首先需要進行聚類距離的計算.小球員帶球跑過程X，Y，Z三個方向加速度大小分別反映其小腿部位前后方向，側面方向(左右)，跳躍方向(上下)的能力.本文研究重點為小球員跑動的綜合能力，需將三維加速度加權處理.球員IDi在t時刻的加權加速度采取常用方法[13]，為原始三維數據的絕對值之和，其計算公式為

ALLsinal((IDi))t=|Xt|+|Yt|+|Zt|

(1)

其中，i為球員號碼標識 ,取值為1-11.t表示時間,實際跑動為提高瞬時性和靈敏度，每1秒獲取傳感器數據10次，如5分鐘即有3000條記錄.

(2)

3 動態增量聚類算法在運動員跑動能力挖掘中的應用

本文聚類算法希望輔助教練員發現各小球員技戰術類別，同時聚類樣本為三維加速度指標，不存在聚類樣本數據種類繁多造成的密度不同的問題，因此選取聚類算法中的k-均值算法最為合適.但由于訓練跑動數據量非常大，同時實時變化更新,要求算法復雜度不能過高.許多經典的聚類算法很難滿足這一點[14].因此本文研究重點在k-均值算法基礎上，采用基于中心點的動態增量聚類算法[15,16]，繼承了已有聚類結果，避免了每次更新數據對全部數據重新聚類的問題，有效降低算法復雜度.

3.1 動態增量數據聚類相關定義

(3)

其中num(Ci)為第i類簇中的樣本個數.

(4)

其中t表示時間.

3.2 增量聚類算法

動態增量聚類算法在運動員跑動能力挖掘中的應用基本思想是：對訓練前5分鐘內10名球員(守門員除外)的加權加速度運用經典k均值聚類算法進行聚類，初步劃定運動員跑動能力類別(實際按照教練員需求將小球員分為積極活躍類、穩健類型和消極類三類，K因此取值3).在此基礎上，之后每隔5分鐘獲取訓練各球員加速度信息增量，對增量數據進行聚類，直至訓練結束.可以看到，隨著增量數據的加入，增量聚類算法雖然對原始聚類進行局部更新或全局更新，但因本文研究重點在整場比賽中小球員綜合跑動能力，因此最終還需對數次增量聚類信息進行全局加權處理方為最終聚類結果.算法描述如下：

初始化：給定聚類類別個數k，設定聚類距離閾值ε,初始化原始聚類樣本中心矩陣；

步驟3：對于接下來5分鐘新增量樣本，重復步驟2，直至訓練結束.

步驟4：對每次增量結果進行全局加權處理即為其整場訓練最終跑動能力挖掘結果.

4 實驗結果及評價

4.1 原始聚類結果和增量聚類結果

采用動態增量聚類算法對足球訓練10名小球員的各5分鐘新增時間段3000條*3維聚類樣本進行聚類，其中K取值3，各時間段聚類過程如圖3.

圖3 上半場過程中采用動態增量聚類算法的球員跑動能力原始聚類和增量聚類結果

由圖3可以看到,各增量數據按照本文算法在原始聚類結果基礎上進行修正，避免了每次重復計算，提高了聚類效率.但也看到，在最后的5分鐘聚類結果中雖然ID為5號的選手表現較好，被挖掘至積極主動優秀類別1中，但其在其他時間段表現欠佳，因此此時間段聚類結果不可為其整場比賽的全局綜合評價結果，要挖掘出整場比賽小球員綜合表現還需對數次增量聚類結果進行合并綜合加權處理.

4.2 各增量聚類結果合并加權處理

整場比賽球員的綜合表現應該為其每次增量時間段表現的加權.故需統計各球員在各增量聚類結果中出現次數，其在某一類別中按時間段出現次數較多者則認為其整場表現最終屬于此類別.合并加權處理結果如圖4所示：

圖4 各增量聚類結果合并加權處理圖

由此可見，本過程在各增量聚類結果修正原始聚類結果的基礎上，對各增量聚類結果進行合并加權處理來反映其整場跑動能力，避免了概念偏移現象.綜合處理后，類別1中最終結果為1和4號球員，表明在整個上半場的比賽中其跑動加速度整體水平一直較高,這也反應其總體高質量跑動的時長,說明其無論耐力還是爆發力均屬于積極主動優秀型小球員.5號球員則被歸為類別2中，同時還挖掘分析出類別3中消極較差型.

4.3 閾值ε對聚類質量的影響

評價聚類質量在于兩個方面:聚類內部緊湊和聚類間距離盡可能遠，即類內差異和類間差異[17,18].

類內差異Diffinner(C)采用簇直徑度量.類間差異Diffinter(C1,C2)采用兩類中心點距離度量[19].具體度量公式如下：

Diffinner(C)=max(Dist(IDi,IDj))，?(IDi,IDj)∈C,且i≠j

(5)

Diffinter(C1,C2)=min(Dist(O(C1),O(C2)),其中O(C1),O(C2)為類C1C2中心點.

(6)

閾值ε越大或越小,均會造成孤立點太多且對類內和類間影響，如表1所示：

表1 閾值ε輸入時不同聚類結果類內差異和類間差異

根據表1各簇質量指標的比較，可看出ε取值為1.1G時聚類質量最高,按照1G=9.8m/s2的計算公式，相當于每個簇類約懸殊10m/s2的加速度級別，較符合足球實際跑動中的運動類型級別懸殊.

5 總結

本文將增量聚類算法應用于足球訓練運動員跑動能力挖掘，針對足球跑動數據動態和數據量大的特點，在已有聚類結果基礎上，采用增量聚類算法修正已有結果，避免了每次更新數據對全部數據重新聚類的問題，提高聚類效率.同時，針對實際應用，添加了加權處理模塊，避免了數據偏移.實驗表明，本算法能深刻準確地對足球訓練運動員跑動能力進行動態實時的挖掘分類，更客觀智能且意義重大.但也看到為改變肉眼觀察訓練跑動加速度這一落后、偏差的習慣，提高智能化水平，本文數據來源為無線加速度傳感器數據，此類數據在跑動和傳輸過程中難免會產生噪音數據，這在一定程度上影響本文聚類結果.下一步工作為使原始數據集更智能準確，將考慮對原始數據進行去噪處理.

[1] 曹景偉,馬相長,劉愛杰,等.基于運動學、動力學參數的皮艇專項竟技能力評估方法研究[J].北京體育大學學報,2007，(8)：1122-1125.

[2] 房霄.足球運動數據采集系統設計[D] .南京：南京理工大學碩士學位論文,2010.

[3] 張利敏.基于模糊聚類的路面識別研究[D] .鎮江:江蘇科技大學碩士學位論文,2013.

[4] 倪國元.基于模糊聚類的增量式挖掘算法研究[D].武漢:華中科技大學碩士學位論文,2004.

[5] 劉建曄,李芳.一種基于密度的高性能增量聚類算法[J].計算機工程,2006,(21):66-69.

[6] 陳峰.基于聚類的增量數據挖掘研究[D] .大連:大連海事大學碩士學位論文,2007.

[7] 宋宇辰,宋飛燕，孟海東.基于密度復雜簇聚類算法研究與實現[J] .計算機工程與應用,2007,(35):162-165.

[8] 龔明波,鐘平.尺度空間層次聚類在足球球隊技、戰術能力分類中的應用研究[J].體育科學,2005,(1):87-90.

[9] 顧舒文.足球視頻進球事件的分類和檢索方法研究[D] .武漢:華中科技大學碩士學位論文博士學位論文,2012.

[10] 牛振興.足球視頻主題建模及內容分析方法研究[D] .西安:西安電子科技大學,2012.

[11] 程澤凱,陳梅,秦鋒.基于密度峰值聚類的陣型識別算法[J].常州工學院學報,2016,(2):23-27.

[12] 金川江,蔡忠建，呂圣君.應用Q型聚類對第17屆世界杯足球賽各隊技戰術能力的綜合評價[J] .北京體育大學學報,2003,(1):11-15.

[13] 鐘君.基于加速度傳感器的日常行為識別的特征提取方法[D].蘭州:蘭州大學碩士學位論文,2016.

[14] 閔可銳,唐悅,胡運發,等.動態調整的Web文檔增量聚類算法[J].計算機輔助工程,2006,(1):87-90.

[15]LughoferE.Extensionsofvectorquantizationforincrementalclustering[J].PatternRecognition,2008,(3):995-1011.

[16] 吳琪,左萬利.一種基于距離的增量聚類算法[J].湖南工程學院學報:自然科學版,2005,(3):41-44.

[17] 吳友情.一種新的聚類有效性函數[J].計算機工程與應用,2010,(6):111-117.

[18] 安中華,安瓊.模糊聚類的有效性研究[J].湖北大學學報:自然科學版,2006,(3):222-226.

[19] 韓習武,趙鐵軍.一種聚類質量的評價方法及其應用[J].哈爾濱工業大學學報,2009,(11):225-227.

(責任編校：晴川)

Application Research of Dynamic Incremental Clustering Algorithm for Running Ability Data Mining of Soccer Training

YIN Qian1, ZHANG Cui2

(1.Anhui Sports Vocational and Technical College, Hefei Anhui 230051, China; 2.College of Economic Technology， Anhui Agricultural University, Hefei Anhui 230011, China)

This paper adopted clustering algorithm to conduct running ability mining of soccer training players. The main contributions included: according to the dynamic increase characteristics of the actual running data, the incremental clustering algorithm was proposed to be applied in running ability data mining; processed the clustering data sources and data types; implemented and tested the proposed algorithm. The experimental results show that the mining of running ability data when training based on incremental clustering accords with the basic characteristics of soccer training. The method has the virtue of high intelligence and accuracy, and has good application value.

dynamic dataset; incremental clustering; running acceleration

2016-11-29

安徽省高校人文社科重點項目(批準號：SK2015A659).

尹倩(1984— )，女，安徽淮北人，安徽體育運動職業技術學院講師，碩士.研究方向：人工智能、數據挖掘；張翠(1988— )，女，山東新泰人，安徽農業大學經濟技術學院助教.研究方向：計算機、自動化.

TP391.1

A

1008-4681(2017)02-0054-04