【0】README 0.1）本文旨在講解 哈兒小波變換（分解和重構）進行數據的降維和升維；
【timestamp: 1703281610】時隔幾個月再來review 哈兒小波變換算法的具體思路： 1）分解降維：首先對所有item進行分解降維，求相鄰維度的兩個元素的和均值和差均值，如 array[0] 和 array[1]為一組,array[2]和array[3]為一組；分別存儲在 array[i] array[i+span]， 其中span=該當前分辨率下的 分辨率長度，如當前分辨率為resolution, 則 length=2^resolution； 2）item重構升維：當前分辨率為curResolution，則? int span = (int) pow(2, curResolution); for (int i = 0; i < span; i++) {temp[2*i] = rawitem[i] + rawitem[i+span];temp[2*i+1] = rawitem[i] - rawitem[i+span]; } 因為 rawitem[i] 和 rawitem[i+span]是 降維時的和均值和差均值； 3）質心重構升維： 只需要將較低分辨率下的質心擴展一倍，如 if(ClusterData.resolutionLength < ClusterData.dimension) {for (int j = ClusterData.resolutionLength-1; j >= 0 ; j--) { ClusterData.centroid[i][2*j] = ClusterData.centroid[i][j];ClusterData.centroid[i][2*j+1] = ClusterData.centroid[i][j];} }
【1】intro to 哈兒小波

1.1）定義：哈爾小波變換分為哈爾小波分解和重構。本文利用哈爾小波分解和哈爾小波重構分別對社交網絡中的時間序列進行降維和升維操作，而分解降維和重構升維互為逆過程，這里以哈爾小波分解降維步驟為例進行說明。

1.2）哈爾小波分解（重構是其逆過程）：可以被看作是一系列對離散時間函數的均值和差操作。本文計算離散函數f(t)，即時間序列元素值的每兩個相鄰值間的均值和差。找出離散函數f(t)={9，?7，?3，?5}的哈爾小波分解過程如下表所示：

分辨率 級別	分辨率 （維度）	均值	差值	哈爾小波 分解系數	降維后的 時序	全分辨率下的時序
2	4	{9,7,3,5}		{9,7,3,5}		{9,7,3,5}
1	2	{8,4}	{1,-1}	{8,4,1,-1}	{8,4}	{8,8,4,4}
0	1	{6}	{2}	{6,2,1,-1}	{6}	{6,6,6,6}

對上表的分析（Analysis）： A1）intro to 分辨率：哈兒小波分解和重構常應用于圖像的降維和升維，這里的分辨率，你與可以理解為是圖像的分辨率，分辨率越低，圖像質量越不清晰，分辨率越高圖片質量越清晰（數據顯示更加豐富）；（干貨——我們看到的圖片為什么不清晰） A2）上表中最后一列（全分辨率下的時序）：我們看到數據由 [9 7 3 5] 到 [8 8 4 4] 再到 [6 6 6 6]，顯然在一個圖像的某個區域內，分辨率越低，數據越不豐富，變化越不明顯，這也是為什么低分辨率下數據模糊的一個原因（因為低分辨率下，數據經過降維處理了）；

【2】將上述哈爾小波分解過程用倒置二叉樹表示如下：

【3】看個荔枝

對上圖的分析（Analysis）： A1）以上數據[2, 5, 8, 9, 7, 4, -1, 1]在不同分辨率下經過哈兒小波變換得到的數據如下： 分辨率3：它本身； 分辨率2：3.5， 8.5, 5.5, 0, -1.5, -0.5, 1.5, -1; 分辨率1：6， 2.75， -2.5， 2.75, -1.5, -0.5, 1.5, -1; 分辨率0：4.375， 1.625， -2.5， 2.75, -1.5, -0.5, 1.5, -1; A2）哈兒小波變換分為哈兒小波分解和哈兒小波重構，且我們可以指定最低級分辨率（并不一定是0）；
【4】將哈兒小波變換應用到Kmeans聚類算法（干貨——目的是降低聚類時間復雜度） 1）Kmeans聚類進行前：先對數據進行哈兒小波分解以降維到0分辨率（或你自己指定）（干貨——聚類開始前，我們數據的分辨率是0，而維度是1，即2^0=1）； 2）Kmeans聚類過程中：聚類是一個迭代的過程，每輪迭代，我們都對數據進行哈兒小波重構進行升維（以降低聚類時間復雜度）； 如第1輪聚類后，我們將數據升維到分辨率1下；第2輪迭代后，將數據升維到分辨率2下，以此類推......；當達到全分辨率下時，我們不再進行哈兒小波變換，但可以繼續聚類，直到滿足聚類結束標志的條件為止；
【5】哈兒小波分解和重構源代碼實現? 5.1）哈兒小波分解和重構的源代碼? public class HaarTransform{public static int maxResolution;/*** executing haar reconstruction transform towards given array* @param rawitem raw array* @param curResolution current resolution*/public static void haarReconstruct(double[] rawitem, int curResolution) {double[] temp = new double[rawitem.length];System.arraycopy(rawitem, 0, temp, 0, temp.length);int span = (int) pow(2, curResolution);for (int i = 0; i < span; i++) {temp[2*i] = rawitem[i] + rawitem[i+span];temp[2*i+1] = rawitem[i] - rawitem[i+span];}System.arraycopy(temp, 0, rawitem, 0, temp.length);}/*** @param rawitem is a array* @param leastResolution is the least resolution allowed be zero.* @param maxResolution is equals to log(full dimension)* @return*/public static double[] haarDecompose(double[] rawitem, int leastResolution) {double[] temp = new double[rawitem.length];int resolutionLength = rawitem.length; int maxResolution = HaarTransform.maxResolution;// if rawitem.length=8, maxResolution = 3; // you know least resolution equals to 0.for (int i = maxResolution; i > leastResolution; i--) {System.out.println("第"+i+"級分辨率下");AlgTools.printOneDimArray(rawitem);for (int j = 0; j < resolutionLength / 2; j++) {temp[j] = (rawitem[2*j] + rawitem[2*j+1]) / 2;temp[resolutionLength/2+j] = (rawitem[2*j] - rawitem[2*j+1]) / 2;}resolutionLength /= 2;System.arraycopy(temp, 0, rawitem, 0, temp.length);}return temp;} } 5.2）哈兒小波分解和重構的測試用例
public class HaarTransformTest {public static void main(String[] args) {double[] data = {2, 5, 8, 9, 7, 4, -1, 1};int resolutionNum = (int) (log(data.length) / log(2));System.out.println("分辨率總級別個數為： " + resolutionNum);HaarTransform.maxResolution = resolutionNum;int leastResolution = 0;HaarTransform.haarDecompose(data, leastResolution);System.out.println("最低級分辨率"+leastResolution+"下");AlgTools.printOneDimArray(data);// 哈兒小波分解over.for (int i = leastResolution; i < resolutionNum; i++) {HaarTransform.haarReconstruct(data, i);System.out.println("第"+ (i+1) + "級分辨率下");AlgTools.printOneDimArray(data);}// 哈兒小波重構over.} } 對以上代碼的分析（Analysis）： A1）因為總共維度是8，所以最大分辨率==log8=3； A2）上述哈兒小波分解過程中對應的變量變化如下（為了便于更加理解分解過程）：

循環次數 round	分辨率級別 i?	分辨率級別的對應維度 resolutionLength	j(max)	下一分辨率級別 的維度sum
1	3	8	3(0~3)	4
2	2	4	1(0~1)	2
3	1	2	0(0~0)	1
4	0	1
	?	?	?	?

5.2）打印結果（共8維）（也可以指定哈爾小波分解的最低級分辨率，如1,2，但最小是0） 分辨率總級別個數為： 3 第3級分辨率下2.000 5.000 8.000 9.000 7.000 4.000 -1.000 1.000 第2級分辨率下3.500 8.500 5.500 0.000 -1.500 -0.500 1.500 -1.000 第1級分辨率下6.000 2.750 -2.500 2.750 -1.500 -0.500 1.500 -1.000 最低級分辨率0下4.375 1.625 -2.500 2.750 -1.500 -0.500 1.500 -1.000 第1級分辨率下6.000 2.750 -2.500 2.750 -1.500 -0.500 1.500 -1.000 第2級分辨率下3.500 8.500 5.500 0.000 -1.500 -0.500 1.500 -1.000 第3級分辨率下2.000 5.000 8.000 9.000 7.000 4.000 -1.000 1.000

總結

以上是生活随笔為你收集整理的哈儿小波分解和重构（降维和升维）实现算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。