趙 鑫, 毋 濤

(西安工程大學(xué) 計算機科學(xué)學(xué)院, 西安 710048)

在物質(zhì)生活不斷提高的同時, 人們對西裝完美搭配的追求也愈加強烈了, 西裝個性化定制成為了人們追求高質(zhì)量生活最直接的表達(dá)方式之一[1]. 選擇西裝與搭配西裝將會有一系列的問題需要注意, 比如: 面料、色彩、版型、款式和衣扣等其他細(xì)節(jié)內(nèi)容的選擇, 這些細(xì)節(jié)內(nèi)容之間的搭配對于普通用戶是一個比較困難的問題[2,3]. 隨著西裝定制企業(yè)與互聯(lián)網(wǎng)應(yīng)用的相結(jié)合,企業(yè)定制平臺已存在大量的西裝定制訂單信息數(shù)據(jù),其中包括了上衣各部位的表仕樣、里仕樣、特殊輔料、特殊加工、指定色以及指定色位置等信息, 挖掘其中的關(guān)聯(lián)關(guān)系對企業(yè)發(fā)展有一定的促進(jìn)作用, 對西裝企業(yè)在服裝定制意愿不斷加強的消費趨勢下, 從批量生產(chǎn)向定制生產(chǎn)轉(zhuǎn)型的重要技術(shù)支持. 挖掘頻繁項集是數(shù)據(jù)挖掘過程中的一個重要的步驟, 在許多應(yīng)用環(huán)境中都非常有用, 但是, 在服裝定制領(lǐng)域的應(yīng)用少之甚少. 傳統(tǒng)算法以最小支持度作為輸入, 輸出內(nèi)容至少是在該相對事務(wù)數(shù)據(jù)庫中出現(xiàn)的全部項集, 一般都會發(fā)現(xiàn)成千上萬甚至更多的頻繁項集, 無法從中容易獲取到準(zhǔn)確有價值的信息.

目前國內(nèi)外眾多學(xué)者在數(shù)據(jù)挖掘方面做了深入的應(yīng)用研究, 并應(yīng)用到了很多不同的領(lǐng)域方向, 為其發(fā)展做出了巨大的貢獻(xiàn). 文獻(xiàn)[4]利用鄰接矩陣記錄所有數(shù)據(jù)項的支持度計數(shù), 刪除不滿足最小支持度計數(shù)的數(shù)據(jù)項, 從而進(jìn)行對FP-tree 的剪枝, 降低對存儲資源的占用浪費; 文獻(xiàn)[5]結(jié)合挖掘目標(biāo)篩選出相關(guān)的特定數(shù)據(jù)項進(jìn)行分析, 減少頻繁模式挖掘的次數(shù); 文獻(xiàn)[6]通過引入權(quán)重來區(qū)分?jǐn)?shù)據(jù)項在事務(wù)中的重要性程度; 文獻(xiàn)[7]采用哈希表替代項頭表, 并將最小支持度計數(shù)相同的節(jié)點合并在一起實現(xiàn)壓縮FP-tree; 文獻(xiàn)[8]采用有序樹代替?zhèn)鹘y(tǒng)FP-tree 并采用列表記錄項的頻繁度,從而降低對存儲空間資源的占用以及減少對FP-tree的遍歷次數(shù); 文獻(xiàn)[9]通過設(shè)置最小支持度并剔除不頻繁出現(xiàn)的項目集, 以提高操作效率; 文獻(xiàn)[10]增加每個維度屬性的權(quán)重設(shè)置, 以避免由于屬性分布不均勻而產(chǎn)生冗余的虛假規(guī)則.

本文結(jié)合目前對FP-growth 算法的各步驟改進(jìn)技術(shù)點, 新增不平衡比評價指標(biāo)過濾頻繁項集中用戶不感興趣的關(guān)聯(lián)規(guī)則, 融合K-means 聚類算法將挖掘到的頻繁項集進(jìn)行共性分組, 將具有相同共性的關(guān)聯(lián)規(guī)則劃分在一個簇中, 簡化對頻繁項集的分析. 綜上所述,將FP-growth 算法、K-means 聚類算法與西裝定制搭配工作相結(jié)合, 通過挖掘西裝定制項目之間隱藏的規(guī)則, 為企業(yè)工作人員提供可行的決策建議, 更好地為用戶提供高水平的服務(wù), 滿足用戶的不同需求, 進(jìn)而提升用戶的回購率. 實驗選擇日本最大的西裝銷售商青山洋服的某定制生產(chǎn)商的定制數(shù)據(jù)為研究對象, 對算法的改進(jìn)從不同方面進(jìn)行驗證.

1 西裝定制搭配問題模型

1.1 西裝定制搭配模型建立

為了高效、準(zhǔn)確分析西裝定制內(nèi)容搭配之間的關(guān)系, 結(jié)合某西裝定制企業(yè)實際情況, 本文通過將改進(jìn)FP-growth 算法、K-means 算法和西裝定制內(nèi)容搭配相互融合的方式, 建立挖掘算法模型, 如圖1 所示.

圖1 西裝定制內(nèi)容搭配算法模型

1.2 對一級定制內(nèi)容特征選擇處理

深入企業(yè)和公司人員溝通、交流, 可以了解到一級定制內(nèi)容中存在必須特征和非必須特征, 挖掘必須特征與非必須特征或者必須特征與必須特征之間的關(guān)系, 沒有實際的意義. 通過方差選擇方法對一級定制內(nèi)容進(jìn)行特征選擇. 結(jié)合實際場景, 可以總結(jié)出特征值全為1 的特征為必須特征, 不存在特征值全為0 的特征,故設(shè)置條件閾值為0. 通過特征選擇, 能夠?qū)⒁患壎ㄖ苾?nèi)容分為必須特征和非必須特征, 從而為一級定制和二級定制內(nèi)容頻繁項集的挖掘提供準(zhǔn)確的數(shù)據(jù)基礎(chǔ).

1.3 對頻繁項集的聚類處理

通過關(guān)聯(lián)規(guī)則算法進(jìn)行數(shù)據(jù)挖掘?qū)a(chǎn)生大量的頻繁項集, 為了降低對頻繁項集理解的復(fù)雜性, 本文使用K-means 算法對挖掘的頻繁項集進(jìn)行聚類處理, 將具有相同共性的樣本劃分在一個簇中, 每一簇內(nèi)的規(guī)則前件之間存在共同的特征, 簇內(nèi)規(guī)則的相似性很高,不同簇之間的趨勢不同. 采用SSE (誤差平方和)評價指標(biāo)選取最佳聚類數(shù), 可以高效地得到聚類簇數(shù)k. 為后續(xù)實驗提供數(shù)據(jù)基礎(chǔ), 同時用戶在得到聚類分組規(guī)則集時, 容易通過聚類規(guī)則集內(nèi)的規(guī)則找出規(guī)則之間的共同點, 快速得到有價值的信息, 對無意義的規(guī)則直接進(jìn)行刪除.

2 算法概述

2.1 關(guān)聯(lián)規(guī)則概念

(1) 支持度(support): 指事務(wù)數(shù)據(jù)庫中同時包含事件A和事件B的概率, 如式(1)所示:

其中,A和B表示不同的事件. 將項集在事務(wù)數(shù)據(jù)庫中出現(xiàn)的頻數(shù), 稱為支持度計數(shù). 能夠作為衡量關(guān)聯(lián)規(guī)則[11]是否是強關(guān)聯(lián)性的條件, 可以篩選出事務(wù)數(shù)據(jù)庫中滿足條件的頻繁項集[11,12].

(2) 置信度(confidence): 指由項集的條件推出后件的可信度, 體現(xiàn)了規(guī)則的確定性, 如式(2)所示.

置信度能夠作為衡量關(guān)聯(lián)規(guī)則是否有實際意義和價值的條件.

(3) 不平衡比(imbalance ratio): 是指關(guān)聯(lián)規(guī)則“A?B”的前件和后件所包含的項集A和B在事務(wù)數(shù)據(jù)庫中被包含的不平衡程度, 如式(3)所示.

其中,Sup表示的是支持度. 能夠很好地評估關(guān)聯(lián)規(guī)則的真實性, 當(dāng)不平衡比值無線接近于零時, 就可以說明項集之間的關(guān)聯(lián)規(guī)則是非常平衡的、用戶感興趣的, 反之亦然.

2.2 K-means 算法

K-means 聚類算法, 是一種通過劃分方法的迭代求解的分析算法, 時間復(fù)雜度和空間復(fù)雜度都是O(n).其優(yōu)點是原理通俗易懂; 算法實現(xiàn)過程比較簡單; 聚類效果也比較優(yōu)越. 缺點是簇數(shù)k值的選取是隨機的、經(jīng)驗化的, 初始質(zhì)心的選擇也很難抉擇; 對于非凸的事務(wù)數(shù)據(jù)集不容易收斂; 最終聚合結(jié)果和初始質(zhì)心的選擇有很大的關(guān)系, 其容易取得某個局部最優(yōu)的結(jié)果.

本文通過手肘法來選擇聚類最佳的簇數(shù)k, 其中誤差平方和是最為核心的評價方法, 簡稱SSE (sum of the squared errors), SSE 是全部樣本點數(shù)據(jù)的聚類誤差結(jié)果, 反映著聚合效果的優(yōu)劣.

2.3 FP-growth 算法

FP-growth 算法的數(shù)據(jù)挖掘過程是根據(jù)建立的FPtree 樹節(jié)點, 按照項頭表中支持度計數(shù)從小到大的順序依次遍歷, 采用了分而治之的搜索思想, 確定每一個項的條件模式基[13], 從而將存在的頻繁項集挖掘出來.

與傳統(tǒng)Apriori 算法分析對比: FP-growth 算法優(yōu)點是沒有候選集的產(chǎn)生; 僅需要兩次對數(shù)據(jù)集進(jìn)行遍歷訪問, 很大程度上降低了程序挖掘的時間[14]. 但是,由于這個過程是基于事務(wù)數(shù)據(jù)集整體進(jìn)行構(gòu)建FP-tree樹節(jié)點, 在處理多維度大型數(shù)據(jù)集的過程中, 算法將會表現(xiàn)出內(nèi)存資源消耗急速增加的問題, 而且程序中存在遞歸調(diào)用過程, 程序的執(zhí)行效率有所下降[15,16].

FP-growth 算法進(jìn)行挖掘的關(guān)鍵步驟是構(gòu)建FPtree 樹節(jié)點. 首次對數(shù)據(jù)集進(jìn)行遍歷, 設(shè)定最小支持度計數(shù)min_sup=3, 可以將所有的頻繁1 項集挖掘出; 將每個事務(wù)中非頻繁1 項集的項全部刪除, 并按照數(shù)據(jù)項的支持度計數(shù)對其進(jìn)行降序排列, 如表1 所示.

表1 第一次掃描原始數(shù)據(jù)庫處理

第2 次遍歷數(shù)據(jù)集, 創(chuàng)建項頭表并構(gòu)建FP-tree 樹節(jié)點, 初始設(shè)置樹的根節(jié)點為null, 并依次為每個事務(wù)創(chuàng)建一個分支, 如圖2 所示.

圖2 FP-tree 節(jié)點

FP-tree 的挖掘方式是自底向上, 如圖3, 根據(jù)項頭表中的數(shù)據(jù)項依次遍歷其條件模式基進(jìn)行挖掘, 設(shè)定最小支持度計數(shù)為2. 從節(jié)點p開始挖掘, 直到挖掘完所有節(jié)點, 就得到了可以挖掘到的事務(wù)數(shù)據(jù)庫中全部頻繁項集. 其中, 節(jié)點f的條件模式基為空, 故不用進(jìn)行挖掘.

圖3 節(jié)點p 頻繁項集挖掘

3 改進(jìn)FP-growth 算法

3.1 改進(jìn)算法的主要思想

本文在繼承FP-growth 算法優(yōu)點的前提下針對其存在的內(nèi)存資源浪費、執(zhí)行效率不高和頻繁項集數(shù)量龐大的問題進(jìn)行優(yōu)化改進(jìn). 綜合已有的幾項優(yōu)勢技術(shù),提出3 點優(yōu)化改進(jìn)思路: (1) 采用哈希表, 只需要掃描事務(wù)數(shù)據(jù)集一次, 把相關(guān)信息存入哈希表和對象數(shù)組中, 可以通過哈希函數(shù)高效定位需要的項, 提高查詢效率. (2) 采用有序FP-tree 結(jié)構(gòu)代替FP-tree, 由于樹結(jié)構(gòu)中節(jié)點是有順序的, 可以有效地使挖掘事務(wù)項的數(shù)量減少, 降低浪費存儲空間、加快程序執(zhí)行效率. (3) 增加不平衡比評估方法來判斷頻繁項的不平衡程度, 使頻繁項集數(shù)量得到很好的控制, 同時使有意義的項集呈現(xiàn)出來, 排除存在抑制的項集[17,18].

(1) 哈希表用來存儲和處理數(shù)據(jù)集每次事務(wù)記錄. 為清晰描述該效果, 使用二維矩陣結(jié)構(gòu)將表1 中的原始數(shù)據(jù)集表示出來, 如式(4)所示. 事務(wù)中每個數(shù)據(jù)項的位置對應(yīng)二維矩陣的行或列, 但該矩陣并沒有使用到算法中. 哈希函數(shù)f(Mij)=Rij可以通過矩陣的行號和列號進(jìn)行定義, 可以保證任意2 個項都不會發(fā)生哈希沖突, 因此可以說選擇Rij作為哈希函數(shù)是可行的. 首先掃描數(shù)據(jù)集得到所有頻繁項的集合和支持度計數(shù), 按照每個事務(wù)中項出現(xiàn)順序建立哈希表; 然后按照支持度計數(shù)遞減的方式重新排序生成新的項頭表.

(2) 使用有序FP-tree 代替?zhèn)鹘y(tǒng)的FP-tree, 有序FPtree 中的節(jié)點定義了4 個域空間內(nèi)容, 分別為name、count、pcLink 和nLink. name 域存放節(jié)點在哈希表中對應(yīng)的哈希地址值; count 域存放節(jié)點的頻繁數(shù); pcLink域在樹結(jié)構(gòu)建立時指向第1 個孩子節(jié)點, 完成建樹過程后指向父節(jié)點; nLink 域在樹結(jié)構(gòu)建立時指向兄弟節(jié)點, 完成后指向相同name 的下一個節(jié)點位置. 在相同父節(jié)點的不同子節(jié)點插入時需要按照節(jié)點的哈希地址值降序依次排列, 可以減少訪問子節(jié)點的次數(shù), 從而達(dá)到了高效建立樹的目標(biāo)[19]. 傳統(tǒng)FP-tree 中的節(jié)點是無序的; 有序FP-tree 的節(jié)點與傳統(tǒng)FP-tree 相比較占用約為2/3 的內(nèi)存資源. 在建樹過程可以利用橫向上節(jié)點的有序性減少子節(jié)點遍歷的次數(shù), 提升建樹過程的效率, 利用垂直方向上的有序性對最大頻繁項集挖掘時可以減少挖掘數(shù)量, 提升挖掘過程的效率[20,21]. 其中,name 就是該項在哈希表中的哈希地址值, 不需要進(jìn)行查找.

(3) 不平衡比可以有效地減少抑制項集的產(chǎn)生. 通過對挖掘的頻繁項集計算置信度和不平衡比, 可以判斷出該項集是否滿足設(shè)定的最小置信度和最大不平衡比, 可以在程序中對挖掘關(guān)聯(lián)規(guī)則數(shù)量進(jìn)行有效的控制, 剔除抑制項集對實驗結(jié)果產(chǎn)生偏差的可能性.

3.2 改進(jìn)算法的主要流程

改進(jìn)FP-growth 算法主要過程流程圖, 如圖4 所示.

圖4 改進(jìn)FP-growth 算法的主要過程流程圖

4 改進(jìn)算法在西裝定制搭配中的應(yīng)用

4.1 實驗環(huán)境

硬件環(huán)境: 英特爾 Core i5-6300HQ CPU @ 2.30 GHz處理器, 16 GB 內(nèi)存, 512 GB 固態(tài)硬盤.

軟件環(huán)境: Windows 10 系統(tǒng), PyCharm 2019.

編程語言: Python 3.7.

4.2 數(shù)據(jù)預(yù)處理

本實驗選擇日本最大的西裝銷售商青山洋服的某定制生產(chǎn)商的定制數(shù)據(jù)作為分析的數(shù)據(jù)源, 選取其中的上衣數(shù)據(jù)集為研究對象. 該數(shù)據(jù)集包含2021 年02 月的上衣歷史訂單記錄3 466 條, 其中一級上衣定制內(nèi)容特征31 個, 二級上衣定制內(nèi)容特征136 個, 如表2.

對上衣定制內(nèi)容數(shù)據(jù)集進(jìn)行one-hot 編碼數(shù)據(jù)預(yù)處理, 存在記為1, 不存在記為0, 用于一級定制內(nèi)容特征選擇, 記為實驗數(shù)據(jù)1, 如表3 所示; 表2 中上衣定制內(nèi)容歷史數(shù)據(jù), 用于二級定制內(nèi)容頻繁項集挖掘, 記為實驗數(shù)據(jù)2.

表2 上衣定制內(nèi)容歷史記錄(部分)

表3 上衣定制內(nèi)容one-hot 編碼處理(部分)

4.3 實驗結(jié)果分析

(1) 一級定制內(nèi)容特征選擇

使用過濾法的去掉取值變化小的特征方法對實驗數(shù)據(jù)1 進(jìn)行特征選擇. 結(jié)果如表4 所示, 其中一級定制內(nèi)容中必須特征7 項, 非必須特征24 項.

表4 一級定制內(nèi)容特征選擇

(2) 一級定制內(nèi)容頻繁項集

對實驗數(shù)據(jù)2 進(jìn)行數(shù)據(jù)轉(zhuǎn)換處理, 例如, 用“JK01”代替“JK0101”“JK0102”等, 并刪除必須特征內(nèi)容, 由于文章篇幅問題, 不展示經(jīng)處理后的數(shù)據(jù)集, 記為實驗數(shù)據(jù)3. 使用改進(jìn)FP-growth 算法挖掘一級非必須特征內(nèi)容中隱含的頻繁項集, 設(shè)定實驗的最小支持度計數(shù)為1 400、最小置信度為0.6. 通過實驗挖掘到頻繁項集273 組,如表5. 經(jīng)公司業(yè)務(wù)負(fù)責(zé)人審核實驗結(jié)果, 273 組關(guān)聯(lián)規(guī)則全部都是有意義的、用戶所感興趣的, 符合西裝定制搭配的實際情況, 并且不平衡比都在0.2 以下.

表5 一級定制內(nèi)容頻繁項集(部分)

(3) 一級定制內(nèi)容聚類分析

根據(jù)一級定制內(nèi)容頻繁項集規(guī)則進(jìn)行K-means 聚類實驗, 通過實驗發(fā)現(xiàn), 最佳聚類簇數(shù)為k=5, 如圖5所示. 可以將一級定制內(nèi)容頻繁項集根據(jù)聚類結(jié)果分組, 為二級定制內(nèi)容挖掘提供實驗基礎(chǔ).

圖5 一級定制內(nèi)容聚類K 值

(4) 二級定制內(nèi)容頻繁項集

根據(jù)一級定制內(nèi)容聚類結(jié)果分別與一級定制內(nèi)容必須特征進(jìn)行組合, 分組使用改進(jìn)FP-growth 算法進(jìn)行隱含的關(guān)聯(lián)規(guī)則挖掘, 設(shè)定實驗的最小支持度計數(shù)為800、最小置信度為0.9. 通過實驗挖掘到頻繁項集總計4 699 組, 如表6 所示. 經(jīng)公司負(fù)責(zé)人員審核發(fā)現(xiàn)其中有1 082 組關(guān)聯(lián)規(guī)則是無意義的、用戶不感興趣的,不符合西裝定制的實際情況. 例如, 滌綸面料與形狀記憶這個規(guī)則, 由于滌綸面料是不需要做形狀記憶的, 所以這個關(guān)聯(lián)規(guī)則是無意義的. 最后, 實驗得出最大不平衡比為0.55.

表6 二級定制內(nèi)容頻繁項集(部分)

(5) 二級定制內(nèi)容聚類分析

對二級定制內(nèi)容頻繁項集進(jìn)行匯總整理, 對匯總數(shù)據(jù)進(jìn)行one-hot 編碼處理, 然后進(jìn)行K-means 聚類實驗分析, 通過實驗可以發(fā)現(xiàn), 最佳聚類簇數(shù)k=6, 如圖6.

圖6 二級定制內(nèi)容聚類k 值

4.4 改進(jìn)FP-growth 算法性能測試

為增進(jìn)分析改進(jìn)的FP-growth 算法在性能方面優(yōu)勢, 利用實驗數(shù)據(jù)3 對改進(jìn)FP-growth 算法、傳統(tǒng)FPgrowth 算法和Apriori 算法進(jìn)行運行時間、內(nèi)存消耗以及頻繁項集數(shù)比較, 設(shè)置最小置信度為0.6. 運行結(jié)果比較結(jié)果如圖7(a), 內(nèi)存消耗比較結(jié)果如圖7(b), 頻繁項集數(shù)比較結(jié)果如圖7(c)所示. 可以發(fā)現(xiàn): 改進(jìn)的FP-growth 算法相比傳統(tǒng)算法提升了約15%的執(zhí)行時間, 內(nèi)存資源消耗上也相對降低6.7%左右, 并且挖掘的頻繁項集也相對較少. 因此改進(jìn)的FP-growth 算法是一個相對高效、可行的數(shù)據(jù)挖掘算法.

圖7 改進(jìn)FP-growth 性能比較

5 結(jié)束語

本文提出融合K-means 與改進(jìn)FP-growth 的西裝定制內(nèi)容搭配挖掘算法. 首先, 綜合相關(guān)文獻(xiàn)中先進(jìn)的技術(shù)點對FP-growth 算法進(jìn)行改進(jìn), 采用有序FP-tree代替FP-tree 的樹結(jié)構(gòu), 減少內(nèi)存資源占用; 采用哈希表, 只需要對事務(wù)數(shù)據(jù)集進(jìn)行一次掃描, 減少了讀取I/O 的開銷, 存儲和遍歷查詢所消耗的時間很明顯有所降低; 采用不平衡比評價方法對抑制型的頻繁項進(jìn)行刪除, 減少頻繁項集的復(fù)雜. 然后, 融合改進(jìn)FP-growth與K-means 算法并結(jié)合實際應(yīng)用場景, 利用該算法對西裝定制一級內(nèi)容、二級內(nèi)容進(jìn)行聚類分析和數(shù)據(jù)挖掘分析, 用戶通過查看每一簇中的規(guī)則就能快速地找到自己感興趣的規(guī)則, 并且針對簇內(nèi)的規(guī)則得出結(jié)論.通過實驗證明, 該算法在挖掘關(guān)聯(lián)規(guī)則上是可行的且高效的, 挖掘出的規(guī)則是用戶感興趣的且有意義的, 對企業(yè)的建設(shè)提供決策支持, 提供更切合實際、可行的建議, 更好地滿足用戶各類需求.