基于張量分解的多維數(shù)據(jù)填充算法

朱彥君，吳向陽

(杭州電子科技大學(xué)計(jì)算機(jī)學(xué)院，杭州 3 10018)

基于張量分解的多維數(shù)據(jù)填充算法

朱彥君，吳向陽

(杭州電子科技大學(xué)計(jì)算機(jī)學(xué)院，杭州 3 10018)

在多維數(shù)據(jù)分析和處理中，經(jīng)常會出現(xiàn)部分?jǐn)?shù)據(jù)丟失或者部分?jǐn)?shù)據(jù)未知的情況，如何利用已知數(shù)據(jù)的潛在結(jié)構(gòu)對這些缺失數(shù)據(jù)進(jìn)行填充是一個(gè)亟待解決的問題。目前對于缺失數(shù)據(jù)填充的研究大多是針對矩陣或者向量形式的低維數(shù)據(jù)，而對于三維以上高維數(shù)據(jù)填充的研究則很少。針對該問題，提出一種基于張量分解的多維數(shù)據(jù)填充算法，利用張量分解中CP分解模型的結(jié)構(gòu)特性和分解的唯一性，實(shí)現(xiàn)對多維數(shù)據(jù)中缺失數(shù)據(jù)的有效填充。通過實(shí)驗(yàn)對以三維形式存儲的部分?jǐn)?shù)據(jù)缺失圖像進(jìn)行填充修復(fù)，并與CP-WOPT算法進(jìn)行比較，結(jié)果表明，該算法具有較高的準(zhǔn)確度以及較快的運(yùn)行速度。

缺失數(shù)據(jù)填充；張量分解；多維數(shù)據(jù)填充；多維數(shù)據(jù)分析；多維數(shù)據(jù)處理；圖像修復(fù)

1 概述

在生物信號處理、化學(xué)數(shù)據(jù)分析、數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)等方面，經(jīng)常需要處理部分?jǐn)?shù)據(jù)缺失的多維數(shù)據(jù)[1]。這些缺失的數(shù)據(jù)可能是因?yàn)閬G失或者無法觀察到而引起的，是不可避免的?，F(xiàn)階段大部分處理數(shù)據(jù)的算法都是基于完整的數(shù)據(jù)。例如在數(shù)據(jù)挖掘中，對含有缺失數(shù)據(jù)的多維數(shù)據(jù)進(jìn)行分析，有可能建立錯誤的挖掘模型。處理缺失數(shù)據(jù)的方法大致分為3類：刪除元組，數(shù)據(jù)填充和不處理[2]。目前，最有效地分析和處理這些多維數(shù)據(jù)的方法，就是給缺失數(shù)據(jù)一個(gè)填充值[3-4]。過去，數(shù)據(jù)填充局限于二維矩陣或者向量形式的低維數(shù)據(jù)[5-6]，對于高維數(shù)據(jù)填充的研究很少。Acar E等人于2011年提出了CP-WOPT算法[7]，可以對高維數(shù)據(jù)進(jìn)行填充，但它是基于梯度值最優(yōu)的方法對缺失數(shù)據(jù)進(jìn)行估計(jì)的，因此，填充數(shù)據(jù)非常不準(zhǔn)確。

本文提出一種基于張量分解[8]的多維數(shù)據(jù)填充算法，稱為CPWF(Candecomp/Parafac Weighted Filling)算法。它可對高維數(shù)據(jù)進(jìn)行填充，并且能夠充分挖掘所有已知數(shù)據(jù)的潛在結(jié)構(gòu)[9]，實(shí)現(xiàn)對缺失數(shù)據(jù)的準(zhǔn)確填充。為了便于觀察和描述，實(shí)驗(yàn)中將彩色圖像按三維形式存儲并進(jìn)行處理，但該算法不局限于三維數(shù)據(jù)，任意維數(shù)據(jù)均可處理。

2 預(yù)備知識

2.1 張量的矩陣化

由于張量矩陣化的形式不唯一，不同的矩陣化方法會導(dǎo)致完全不同的計(jì)算結(jié)果，因此本文中的矩陣化方法如無特殊說明，均指本節(jié)所說的矩陣化方法。

為了便于理解，這里用一個(gè)實(shí)例作為說明。假設(shè)有一個(gè)張量X(3× 4×2)：

2.2 C P分解模型

一個(gè)張量可看成一個(gè)多維數(shù)組。張量特別是高維的張量，在應(yīng)用上實(shí)現(xiàn)對數(shù)據(jù)和實(shí)際情況較為準(zhǔn)確的建模，但是這種建模方法使得張量的計(jì)算成為一個(gè)巨大問題。因此，需要對張量進(jìn)行分解，以降低其維數(shù)，減少計(jì)算的復(fù)雜度，并能夠最大程度保留原始數(shù)據(jù)的特征?，F(xiàn)有的張量分解法主要有CP分解法和Tucker分解法。本文只關(guān)注CP分解法。

為了便于理解，本文以一個(gè)三維張量X(I×J×K)為例，高于三維的情況可以很容易的推導(dǎo)出來。X的CP分解模型如圖1所示。

圖1 三維張量的CP分解模型

張量的元素值與分解后的向量元素值之間的關(guān)系如下：

如果將矩陣A(I×R)看成由a1～aR共R個(gè)列向量構(gòu)成的矩陣，將矩陣B(J×R)看成由b1～bR共R個(gè)列向量構(gòu)成的矩陣，將矩陣C(K×R)看成由c1～cR共R個(gè)列向量構(gòu)成的矩陣，那么X、A、B、C之間有如下性質(zhì)：

其中，X(n)表示張量X的第n維矩陣化[8]；表示Khatri-Rao積[10]；T表示矩陣的轉(zhuǎn)置。

CP分解的目的是求出A，B，C這3個(gè)矩陣。假設(shè)R值是給定的，那么問題轉(zhuǎn)化為：

其中，“*”表示矩陣的Hadamard積[8]。

由于CP分解是唯一的[11]，因此迭代一定會收斂。當(dāng)R大于張量的秩[12]時(shí)，

3 CP-WOPT算法簡介

CP-WOPT算法[7]可以對高維數(shù)據(jù)進(jìn)行填充。

給定一個(gè)部分?jǐn)?shù)據(jù)缺失的張量X，定義一個(gè)記錄缺失信息的權(quán)值張量W如下：

4 CPWF算法

4.1 算法步驟

本文提出算法稱為CPWF算法。為了便于理解，以三維張量為例，高于三維的情況可以很容易推導(dǎo)出來。

為了記錄哪些數(shù)據(jù)丟失，定義一個(gè)和原始張量大小相同的權(quán)值張量W如下：

該文提出的CPWF算法具體如下：

(1)給定張量X和記錄缺失數(shù)據(jù)位置的張量W；

(2)隨便填充張量X的缺失數(shù)據(jù)(隨機(jī)數(shù)或者平均值)；

(3)初始化A，B，C和R；

4.2 算法原理

針對三維張量，4.1節(jié)步驟(4)每迭代一次，就把原始張量X的每個(gè)元素值分散到A，B，C 3個(gè)矩陣中，即按式(2)進(jìn)行映射。此時(shí)，隨機(jī)填充的缺失數(shù)據(jù)值和已知數(shù)據(jù)的值都映射到矩陣A，B，C中，并且在一定程度上混合了，即矩陣A，B，C中每個(gè)元素值不僅與已知數(shù)據(jù)相關(guān)，而且與隨機(jī)填充的缺失數(shù)據(jù)相關(guān)。

由于數(shù)據(jù)具有一定的潛在結(jié)構(gòu)，因此每個(gè)缺失位置的元素值根據(jù)第一輪迭代后的A，B，C值按照式(2)還原后，會含有一定的新信息，這些信息就是通過CP分解模型挖掘出的理論填充值。

重復(fù)4.1節(jié)的步驟(4)，每迭代一次，都會根據(jù)已知數(shù)據(jù)不斷修正填充值。由于CP分解的唯一性，因此每迭代一次，填充值的變化會越來越小，直到收斂。

5 實(shí)驗(yàn)結(jié)果與分析

5.1 算法準(zhǔn)確性

為了驗(yàn)證算法的準(zhǔn)確性，本文實(shí)驗(yàn)將部分?jǐn)?shù)據(jù)丟失的BGR圖像像素值寫入張量X中，X的第一維為通道數(shù)(BGR圖像時(shí)長度為3)，第二三維為圖像的高度和寬度，xijk表示第i通道在位置(j,k)處的像素值。實(shí)驗(yàn)結(jié)果如圖2、圖3所示。圖2(a)為按三維形式存儲的挖掉一塊數(shù)據(jù)的原始圖像，圖2(b)為CP-WOPT算法填充結(jié)果，圖2(c)為CPWF算法填充結(jié)果。由于CP-WOPT算法不夠準(zhǔn)確，因此圖2(b)中填充的效果很不好，當(dāng)局部塊缺失時(shí)，該算法不能準(zhǔn)確挖掘已知數(shù)據(jù)的潛在結(jié)構(gòu)去填充缺失部分。實(shí)驗(yàn)結(jié)果表明，對于局部整塊缺失的多維數(shù)據(jù)，CPWF算法填充效果很好。

圖2 R=4時(shí)圖像填充效果

圖3(a)為按三維形式存儲的添加30%噪聲的原始圖像，圖3(b)為CP-WOPT算法填充結(jié)果，圖3(c)為CPWF算法填充結(jié)果。被噪聲污染的部分被認(rèn)為是數(shù)據(jù)缺失的部分。顯然，CP-WOPT算法填充有一些效果，但是帽子和肩膀部分的填充仍然不是很好。而本文提出的CPWF算法填充效果明顯比CP-WOPT算法要好，不僅平滑，而且細(xì)節(jié)更明顯。該實(shí)驗(yàn)表明，本文提出的CPWF算法對于離散型缺失的多維數(shù)據(jù)填充效果同樣非常好。

圖3 R=11時(shí)圖像填充效果

5.2 算法效率

針對圖2、圖3中三維形式的數(shù)據(jù)，CP-WOPT算法和CPWF算法運(yùn)行時(shí)間如表1所示。本文所有實(shí)驗(yàn)數(shù)據(jù)都在聯(lián)想Y460N筆記本上測試運(yùn)行，CPU為i3 380M，2.53 GHz。內(nèi)存4 GB，64位Win7操作系統(tǒng)。由表1可以看出，CPWF算法運(yùn)算速度明顯比CP-WOPT算法快。

表1 C P-WOPT和CPWF算法運(yùn)行時(shí)間比較 s

6 結(jié)束語

本文提出一種基于張量分解的多維數(shù)據(jù)填充算法，利用張量分解中CP分解模型的結(jié)構(gòu)特性和分解的唯一性，實(shí)現(xiàn)了對多維數(shù)據(jù)中缺失數(shù)據(jù)的有效填充。實(shí)驗(yàn)結(jié)果證明，不管是局部數(shù)據(jù)整塊缺失還是全局離散缺失，本文提出的CPWF算法都可以很好地填充缺失數(shù)據(jù)，不僅比CP-WOPT算法準(zhǔn)確，而且運(yùn)行速度更快。對于沒有規(guī)律或者規(guī)律不明顯的多維數(shù)據(jù)，如果是全局離散缺失，本文算法仍然可以很好地填充，但當(dāng)局部數(shù)據(jù)整塊缺失時(shí)，算法效果并不理想，因此，需要作進(jìn)一步研究。另外，本文中的R值需要手動調(diào)整以達(dá)到最佳填充效果，如果取值過大，填充效果反而不好，因此，如何選取一個(gè)合適的R值也需要作進(jìn)一步研究。

[1] Smilde A, Bro R, Geladi P. Multi-way Analysis: Applications in the Chemical Sciences[M]. [S. l.]: Wiley, 2004.

[2] Pearson R K. The Problem of Disguised Missing Data[J]. ACM SIGKDD Explorations Newsletter, 2006, 8(1): 83-92.

[3] Witten I H, Frank E. Data Mining: Practical Machine Learning Tools and Techniques with Java Implementations[M]. 2nd ed. [S. l.]: Morgan Kaufmann, 2005.

[4] Han Jiawei, Kamber M. Data Mining Concepts and Techniques[M]. 2nd ed. [S. l.]: Morgan Kaufmann, 2006.

[5] Nocedal J, Wright S J. N umerical O ptimization[M]. [S. l.]: Springer, 1999.

[6] 鄒 薇, 王會進(jìn). 基于樸素貝葉斯的EM缺失數(shù)據(jù)填充算法[J]. 微型機(jī)與應(yīng)用, 2011, 30(16): 75-77, 81.

[7] Acar E, Dunlavy D M, Kolda T G, et al. S calable Tensor Factorizations wi th Missing Data[C]//Proceedings of SI AM International Co nference on Da ta Mining. Colu mbus, US A: [s. n.], 2011: 41-56.

[8] Kolda T G, Bader B W. Tensor Decompositions and Applications[J]. SIAM Review, 2009, 51(3): 455-500.

[9] 廖志芳, 李 玲, 劉麗敏, 等. 三部圖張量分解標(biāo)簽推薦算法[J]. 計(jì)算機(jī)學(xué)報(bào), 2012, 35(12): 2625-2632.

[10] Golub G H, V anloan C F. Matrix C omputations[M]. [S. l.]: Johns Hopkins University Press, 1996.

[11] Kruskal J B. Rank, Decomposition, and Uniqueness for 3-way and N-way Arrays[M]. Amsterdam, the Netherlands: North-Holland Publishing Co., 1989: 7-18.

[12] Hastad J. Tensor rank is NP-complete[J]. Journal of Algorithms, 1990, 11(4): 644-654.

編輯 陸燕菲

Multi-dimensional Data Filling Algorithm Based on Tensor Decomposition

ZHU Yan-jun, WU Xiang-yang

(School of Computer Science and Technology, Hangzhou Dianzi University, Hangzhou 310018, China)

On the multi-dimensional data an alysis and processing, data with missing or unknown values is ubiquitous. How to use the potential structure of the known data to reconstruct the missing data is an urgent problem to be solved. Previously, the missing data filling mostly aims at low-dimensional da ta in matrix or vector format, while research on high-dimensional data above 3D is very few. To solve this problem, this paper proposes a multi-dimensi onal data filli ng algorithm based on tensor deco mposition, adequ ately using te nsor decomposition’s structure and uniqueness of CP model, to realize the multi-dimensional data filling effectively. Filling image with missing data stored in 3D format by experiment and comparison with CP-WOPT algorithm, it proves that this algorithm is not only accurate but also rapid.

missing data filling; tensor decomposition; mulit-dimensional data filling; multi-dimensional data analysis; multi-dimensional data processing; image inpainting

10.3969/j.issn.1000-3428.2014.05.010

國家自然科學(xué)基金資助項(xiàng)目(61003193)；浙江工業(yè)大學(xué)重中之重學(xué)科開放基金資助項(xiàng)目。

朱彥君(1988－)，男，碩士研究生，主研方向：大規(guī)模數(shù)據(jù)處理，圖形圖像處理；吳向陽，副教授、博士。

2013-05-09

2013-06-09E-mail：156372288@qq.com

1000-3428(2014)05-0045-04

A

TP301