對稱矩陣演算法

㈠ 實對稱距陣指數冪的演算法

如果有n階矩陣A，其各個元素都為實數，矩陣A的轉置等於其本身(AT = A) ，則稱A為實對稱矩陣。

如果有n階矩陣A，其各個元素都為實數，且aij=aji i,j=1,2,...,n（即
這兒的T表示轉置），則稱A為實對稱矩陣。

特點

1.實對稱矩陣A的不同特徵值對應的特徵向量是正交的。
2.實對稱矩陣A的特徵值都是實數，特徵向量都是實向量。
3.n階實對稱矩陣A必可對角化，且相似對角陣上的元素即為矩陣本身特徵值。
4.K重特徵值必有K個線性無關的特徵向量，或者說必有秩r(λE-A)=n-k，其中E為單位矩陣。
5.實對稱矩陣的所有特徵值都是實數。

㈡ 請問一下數據結構中對稱矩陣的壓縮存儲的一 一對應關系怎麼算的呀。

其實書本上說的已經夠了，我就不再贅述了，下面說說不明白的地方吧！

書本上說了 1<=i,j<=n,所以矩陣下標ij是以1開始的，但書本上的k是從0開始的

則下三角區和主對角線下標ij和一維向量下標k的關系式為i(i-1)/2+j-1，如果k從1開始，則關系式為i(i-1)/2+j。

好，進入正題思路：

第1行一個，第2行兩個，。。。，第i-1行i-1個；第i行元素位置在第j，也就是說，第i行截止到它有j個。

所以要分開思考，1到i-1行的元素之和+本行截止到它的元素之和=它在一維數組的位置。

第i行前面i-1行的總和為i(i-1)/2,本行第i行截止到所求元素總數為j，所以加起來為i(i-1)/2+j。然後-1，代表k從0開始。

比如想取第3行第2列矩陣元素隱射到一維數組的位置

本行第3行之前2行的元素總數為3*2/2=3 對應 [i(i-1)/2]

然後j是在本行的位置是2 對應[+j]

總的等於5

這個第3行第2列的元素應該在一維數組的第五個位置，但是一維是從零開始的，所以5-1，得到對應一維數組的下標為4.

王道書上和樓上的答案都是正確的，只不過思路和我的有點不同，我的是處的位置，他們是要求元素之前位置，區別也就+-1

㈢ k-means演算法怎麼為對稱矩陣進行聚類

幾種典型的聚類融合演算法：
1.基於超圖劃分的聚類融合演算法
(1)Cluster-based Similarity Partitioning Algorithm(GSPA)
(2)Hyper Graph-Partitioning Algorithm(HGPA)
(3)Meta-Clustering Algorithm(MCLA)
2.基於關聯矩陣的聚類融合演算法
Voting-K-Means演算法。
3.基於投票策略的聚類融合演算法
w-vote是一種典型的基於加權投票的聚類融合演算法。
同時還有基於互信息的聚類融合演算法和基於有限混合模型的聚類融合演算法。
二、基於關聯矩陣的聚類融合演算法——Voting-K-Means演算法
Voting-K-Means演算法是一種基於關聯矩陣的聚類融合演算法，關聯矩陣的每一行和每一列代表一個數據點，關聯矩陣的元素表示數據集中數據點對共同出現在同一個簇中的概率。
演算法過程：
1.在一個數據集上得到若干個聚類成員；
2.依次掃描這些聚類成員，如果數據點i和j在某個聚類成員中被劃分到同一個簇中，那麼就在關聯矩陣對應的位置計數加1；關聯矩陣中的元素值越大，說明該元素對應的兩個數據點被劃分到同一個簇中的概率越大；
3.得到關聯矩陣之後，Voting-K-Means演算法依次檢查關聯矩陣中的每個元素，如果它的值大於演算法預先設定的閥值，就把這個元素對應的兩個數據點劃分到同一個簇中。

Voting-K-Means演算法的優缺點：
Voting-K-Means演算法不需要設置任何參數，在聚類融合的過程中可以自動地的選擇簇的個數 並且可以處理任意形狀的簇。因為Voting-K-Means演算法在聚類融合過程中是根據兩個數據點共同出現在同一個簇中的可能性大小對它們進行劃分的，所以只要兩個數據點距離足夠近，它們就會被劃分到一個簇中。
Voting-K-Means演算法的缺點是時間復雜度較高，它的時間復雜度是O(n^2);需要較多的聚類成員，如果聚類成員達不到一定規模，那麼關聯矩陣就不能准確反映出兩個數據點出現在同一個簇的概率。

package clustering;import java.io.FileWriter;import weka.clusterers.ClusterEvaluation;import weka.clusterers.SimpleKMeans;import weka.core.DistanceFunction;import weka.core.EuclideanDistance;import weka.core.Instances;import weka.core.converters.ConverterUtils.DataSource;import weka.filters.unsupervised.attribute.Remove;public class Votingkmeans2 extends SimpleKMeans { /** 生成的序列號 */ private static final long serialVersionUID = 1557181390469997876L; /** 劃分的簇數 */ private int m_NumClusters; /** 每個劃分的簇中的實例的數量 */ public int[] m_ClusterSizes; /** 使用的距離函數，這里是歐幾里德距離 */ protected DistanceFunction m_DistanceFunction = new EuclideanDistance(); /** 實例的簇號賦值 */ protected int[] m_Assignments; /** 設定聚類成員融合閥值 */ private final static double THREASOD = 0.5; /** 生成一個聚類器 */ public void buildClusterer(Instances data) throws Exception{ final int numinst = data.numInstances(); // 數據集的大小 double [][]association = new double[numinst][numinst]; // 定義並初始化一個關聯矩陣 int numIteration = 40; // 設置生成的聚類成員數 final int k = (int)Math.sqrt(numinst); // 設置K-Means聚類演算法參數——簇數 for(int i = 0; i < numIteration; i++) { if(data.classIndex() == -1) data.setClassIndex(data.numAttributes() - 1); // 索引是從0開始 String[] filteroption = new String[2]; filteroption[0] = "-R"; filteroption[1] = String.valueOf(data.classIndex() + 1);// 索引是從1開始 Remove remove = new Remove(); remove.setOptions(filteroption); remove.setInputFormat(data); /* 使用過濾器模式生成新的數據集；新數據集是去掉類標簽之後的數據集 */ Instances newdata = weka.filters.Filter.useFilter(data, remove); /* 生成一個K-Means聚類器 */ SimpleKMeans sm = new SimpleKMeans(); sm.setNumClusters(k); sm.setPreserveInstancesOrder(true); // 保持數據集實例的原始順序 sm.setSeed(i); // 通過設置不同的種子，設置不同的簇初始中心點，從而得到不同的聚類結果 sm.buildClusterer(newdata); int[] assigm = sm.getAssignments(); // 得到數據集各個實例的賦值 /* 建立關聯矩陣 */ for(int j = 0; j < numinst; j++) { for(int m = j; m < numinst; m++) { if(assigm[j] == assigm[m]) { association[j][m] = association[j][m] + 1.0 / numIteration ; } } } } System.out.println(); /* 將生成的關聯矩陣寫入.txt文件（註：生成的txt文本文件在e:/result.txt中） */ FileWriter fw = new FileWriter("e://result.txt"); for(int j = 0; j < numinst; j++) { for(int m = j; m < numinst; m++) { //由於關聯矩陣是對稱的，為了改進演算法的效率，只計算矩陣的上三角 String number = String.format("%8.2f", association[j][m]); fw.write(number); } fw.write("\n"); } /* 處理關聯矩陣，分別考慮了兩種情況 ：1.關聯矩陣中某個元素對應的兩個數據點已經被劃分到了不同的簇中 * 2.兩個數據點中有一個或者兩個都沒有被劃分到某個簇中。 */ int[] flag = new int[numinst]; int[] flagk = new int[k]; int[] finallabel = new int[numinst]; for(int m = 0; m < numinst; m++) { for(int n = m; n < numinst; n++) { if(association[m][n] > THREASOD) { if(flag[m] == 0 && flag[n] == 0) { // 兩個數據點都沒有被劃分到某個簇中， int i = 0; // 將他們劃分到同一個簇中即可 while (i < k && flagk[i] == 1) i = i + 1; finallabel[m] = i; finallabel[n] = i; flag[m] = 1; flag[n] = 1; flagk[i] = 1; } else if (flag[m] == 0 && flag[n] == 1) { // 兩個數據點中有一個沒有被劃分到某個簇中， finallabel[m] = finallabel[n]; // 將他們劃分到同一個簇中即可 flag[m] = 1; } else if (flag[m] == 1 && flag[n] == 0) { finallabel[n] = finallabel[m]; flag[n] = 1; } else if (flag[m] == 1 && flag[n] == 1 && finallabel[m] != finallabel[n]) { // 兩個數據點已被劃分到了不同的簇中， flagk[finallabel[n]] = 0; // 將它們所在的簇合並 int temp = finallabel[n]; for(int i = 0; i < numinst; i++) { if(finallabel[i] == temp) finallabel[i] = finallabel[m]; } } } } } m_Assignments = new int[numinst]; System.out.println("基於關聯矩陣的聚類融合演算法——Voting-K-Means演算法的最終聚類結果"); for(int i = 0; i < numinst; i++) { m_Assignments[i] = finallabel[i]; System.out.print(finallabel[i] + " "); if((i+1) % 50 == 0) System.out.println(); } for(int i = 0; i < k; i++) { if(flagk[i] == 1) m_NumClusters++; } } /** * return a string describing this clusterer * * @return a description of the clusterer as a string */ public String toString() { return "Voting-KMeans\n"; } public static void main(String []args) { try {String filename="e://weka-data//iris.arff"; Instances data = DataSource.read(filename); Votingkmeans2 vk = new Votingkmeans2(); vk.buildClusterer(data); /* 要生成Voting-K-Means的聚類評估結果包括准確率等需要覆蓋重寫toString()方法； * 因為沒有覆蓋重寫，所以這里生產的評估結果沒有具體內容。 */ ClusterEvaluation eval = new ClusterEvaluation(); eval.setClusterer(vk); eval.evaluateClusterer(new Instances(data)); System.out.println(eval.clusterResultsToString()); } catch (Exception e) { e.printStackTrace(); }}}

分析代碼時注意：得到的類成員變數m_Assignments就是最終Voting-K-Means聚類結果；由於是採用了開源機器學習軟體Weka中實現的SimpleKMeans聚類演算法，初始時要指定簇的個數，這里是數據集大小開根號向下取整；指定的閥值為0.5，即當關聯矩陣元素的值大於閥值時，才對該元素對應的兩個數據點進行融合，劃分到一個簇中，考慮兩種情況，代碼注釋已有，這里不再詳述。但聚類融合的實驗結果並不理想，鶯尾花數據集irsi.arff是數據挖掘實驗中最常用的數據集，原數據集共有三個類；但本實驗進行四十個聚類成員的融合，其最終聚類結果劃分成兩個簇；其原因可能有兩個：一是演算法本身的問題，需要使用其他更加優化的聚類融合演算法；二是實現上的問題，主要就在聚類結果的融合上，需要進行一步對照關聯矩陣進行邏輯上的分析，找出代碼中的問題。關聯矩陣文本文件http://download.csdn.net/detail/lhkaikai/7294323

---------------------

本文來自 Turingkk 的CSDN 博客 ，全文地址請點擊：https://blog.csdn.net/lhkaikai/article/details/25004823?utm_source=

㈣ 實對稱矩陣行列式的值怎麼求，求方法！！！！！！

解: |A-λE|=

|2-λ 2 -2|

|2 5-λ -4|

|-2 -4 5-λ|

r3+r2 (消0的同時, 還能提出公因子, 這是最好的結果)

|2-λ 2 -2|

|2 5-λ -4|

|0 1-λ 1-λ|

c2-c3

|2-λ 4 -2|

|2 9-λ -4|

|0 0 1-λ|

= (1-λ)[(2-λ)(9-λ)-8] (按第3行展開, 再用十字相乘法)

= (1-λ)(λ^2-11λ+10)

= (10-λ)(1-λ)^2.

如果有n階矩陣A，其矩陣的元素都為實數，且矩陣A的轉置等於其本身（aij=aji）(i,j為元素的腳標)，而且該矩陣對應的特徵值全部為實數，則稱A為實對稱矩陣。

主要性質：

1.實對稱矩陣A的不同特徵值對應的特徵向量是正交的。

2.實對稱矩陣A的特徵值都是實數，特徵向量都是實向量。

3.n階實對稱矩陣A必可對角化，且相似對角陣上的元素即為矩陣本身特徵值。

4.若λ0具有k重特徵值必有k個線性無關的特徵向量，或者說必有秩r(λ0E-A)=n-k，其中E為單位矩陣。

之前恰有j個元素，即ai0,ai1,…,ai,j-1，因此有：

sa[i×(i+1)/2+j]=aij

③aij和sa[k]之間的對應關系：

若i≥j，k=i×(i+1)/2+j0≤k<n(n+1)/2

若i<j，k=j×(j+1)/2+i0≤k<n(n+1)/2

令I=max(i，j)，J=min(i，j)，則k和i，j的對應關系可統一為：

k=i×(i+1)/2+j0≤k<n(n+1)/2

（3）對稱矩陣的地址計算公式

LOC(aij)=LOC(sa[k])

=LOC(sa[0])+k×d=LOC(sa[0])+[I×(I+1)/2+J]×d

通過下標變換公式，能立即找到矩陣元素aij在其壓縮存儲表示sa中的對應位置k。因此是隨機存取結構。