(3.230.76.48) 您好!臺灣時間:2021/04/11 09:00
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:蔡俊賢
研究生(外文):C. S. Tsai
論文名稱:視覺化技術
論文名稱(外文):Visual Display Techniques
指導教授:李家同李家同引用關係
指導教授(外文):Chia-Tung Lee
學位類別:碩士
校院名稱:國立暨南國際大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2003
畢業學年度:91
語文別:中文
論文頁數:91
中文關鍵詞:視覺化技術叢集分析三角化法則緩和法則賽門法則多維層級法則最小生成樹
外文關鍵詞:visual display techniqueclustering analysistriangulation methodrelaxation methodSammon’s methodmultidimensional scalingminimal spanning tree
相關次數:
  • 被引用被引用:0
  • 點閱點閱:170
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:18
  • 收藏至我的研究室書目清單書目收藏:0
我們認為人類的視覺感觀在二維度和三維度空間上, 對於識別物件和影像上並沒有困難。 然而, 對於高維度空間上的資料或非k維度空間上的點(例如DNA和蛋白質的序列)而言, 有關於視覺化的問題就會發生。 為了解決這個問題, 我們應該試著去降低高維度的資料(或者是未知維度), 並且將這些資料映射到二度空間上, 使得點與點間的距離盡可能地被保存住。 透過視覺化的表現(visual display), 我們可以應用在叢集分析(clustering analysis)技術上。 在本論文中, 我們也會將叢集分析技術(clustering analysis techniques)應用到計算生物學的分析領域上。
本論文中, 四個有關叢集分析(clustering analysis)的主題將被討論。 第一個方法為三角化法則(triangulation method), 此法是透過所給定點(input point)的資料去建構最小生成樹(minimal spanning tree), 只要將給定點(input point)映射到平面上時, 其對應到最小生成樹上所有邊的距離都會被保存住。 稍後, 我們會指出此法則的缺點, 並提出改善之道。
我們提出兩個完全不同的方法, 它們是緩和法則(relaxation method)和賽門法則(Sammon’s method)。 這兩個方法都跟重複性(iterative)地運作有關, 那就是在一開始就給定隨機(random)的座標點, 並依據原本的距離矩陣一步一步地去調整這些座標點, 一直到最後,這些被調整過座標點的所有距離會近似地被保存住。
在最後的主題中, 我們將介紹多維層級法則(multidimensional scaling method)。 此法則的輸入資料為距離矩陣, 並產生k維度空間的座標點, 最後使得這k維度空間座標點對應的距離矩陣會和原本輸入資料的距離矩陣相似。 如果k = 2時, 這就是視覺化技術所要映射的空間。
稍後於論文中, 將會有許多的實驗結果被列出。
關鍵字: 叢集分析, 視覺化技術, 三角化法則, 緩和法則, 賽門法則, 多維層級法則。

Human beings have no difficulty in recognizing objects or images in the two- or three-dimensional space through the perception of eyes. However, for data from a higher dimensional space, or data which are not k-dimensional points, such as DNA and protein sequences, problems concerning visual conception would arise. For resolving these issues, we shall try to map the high dimension of data, or data which are not high dimensional points onto the 2-space such that the distances among points are preserved as much as possible. We shall show that we can apply this visual display to obtain clustering analysis techniques. In this thesis, we shall apply this kind of clustering techniques to some biological data.
In this dissertation, four topics related to visual display clustering analysis are considered. The first method is called the triangulation method. The triangulation method is based upon the minimal spanning tree constructed out of the input points. All of the distances corresponding to the edges of the minimal spanning tree will be exactly preserved after points are mapped to the 2-space. We shall point out some weakness of this method and suggest an improvement of it.
There are two entirely different approaches which are also described in this thesis. They are the relaxation method and Sammon’s method. Both methods are iterative ones. Data are initially mapped randomly to the 2-space and these points will be adjusted step by step based on the original distance matrix. Finally, the distances of these adjusted coordinate points are approximately preserved.
Finally, the multidimensional scaling method is introduced. In this approach, we purely start with the distance matrix of the input points. Then the multidimensional scaling techniques will produce k-dimensional points such that the distance matrix of these k-dimensional points will be approximately equal to the distance matrix of the original input points. If , the multidimensional scaling technique can be viewed as a visual display technique.
Many experimental results will be shown.
Keywords: clustering analysis, visual display technique, triangulation method, relaxation method, Sammon’s method, multidimensional scaling.

Abstract I
Chinese Abstract II
Acknowledgement III
Contents IV
List of Figures VI
List of Tables IX
List of Algorithms X
Chapter 1 Introduction 1
1.1 Motivations and Previous Works 1
1.2 Summary of Our Results 2
1.3 Structure of the Dissertation 4
Chapter 2 The Triangulation Method for Mapping 6
2.1 The Problem 6
2.2 The Triangulation Process 7
2.3 The Triangulation Mapping Method 9
2.4 Experimental Results 14
2.5 The Minimal Spanning Tree Preservation Method 20
2.6 Summary 27
Chapter 3 A Heuristic Relaxation Method 28
3.1 The Problem 28
3.2 The Relaxation Method 28
3.3 Details of the Relaxation Method 30
3.4 Experimental Results 33
3.5 Summary 38
Chapter 4 A Nonlinear Mapping for Sammon’s Method 39
4.1 The Problem 39
4.2 Sammon’s Method 39
4.3 Details of the Sammon Method 40
4.4 Experimental Results 44
4.5 Summary 57
Chapter 5 Multidimensional Scaling 58
5.1 The Problem 58
5.2 Multidimensional Scaling Method 59
5.3 The Mathematical Properties of Multidimensional Scaling 60
5.4 Experimental Results 66
Chapter 6 Conclusions and Future Work 79
6.1 Conclusions 79
6.2 Future work 80
Bibliography 82
Appendix 3.1 84
Appendix 3.2 86
Appendix 4.1 (46 species originated from human mitochndrial DNA control region) 87
Appendix 5.1 90

[CC2001] Multidimensional Scaling, Cox, T. F. and Cox, M. A. A., Chapman&Hall/CRC, ISBN: 1584880945, pp.1-308.
[CL71] Multivariate Data Analysis, Cooley, W. W. and Lohnes, P., New York: Wiley, 1971.
[CL73] A Heuristic Relaxation Method for Nonlinear Mapping in Cluster Analysis, Chang, C. L. and Lee, R. C. T., IEEE Transactions On Systems, Man and Cybernetics., Vol. SMC-3, No.2, March 1973, pp. 197-200.
[F1900] A Second Study of the Variation and Correlation of the Human Skull, with Special Reference to the Naqada Crania, Fawcett, C. D., Biometrika, Vol. 1, 1900, pp. 408-467.
[FSW2002] Rearrangement of DNA Fragments: a Branch-and-Cut Algorithm, Ferreira, C. E., de Souze, C. C. and Wakabayashi, Y., Discrete Applied Mathematics, Vol. 116, 2002,
[K64a] Multidimensional Scaling by Optimizing Goodness-of-Fit to a Nonmetric Hypothesis, Kruskal, J. B., Psychometrika, Vol. 29, pp. 1-27.
[K64b] Nonmetric Multidimensional Scaling: a Numerical Method, Kruskal, J. B., Psychometrika, Vol. 29, pp. 115-129.
[K68] A Course in Multivariate Analysis, Kendall, M. G., New York: Hefner, 1968.
[LSB77] A Triangulation Method for the Sequential Mapping of Points from N-Space to Two-Space, Lee, R. C. T., Slagle, J. R. and Blum, H., IEEE Trans. Comput., March 1977, pp. 288-292.
[S62a] “The Analysis of Proximities: Multidimensional Scaling with an Unknown Distance Function Ⅰ,” Shepard, R. N., Psychometrica, Vol. 27, 1962, pp. 125-140.
[S62b] “The Analysis of Proximities: Multidimensional Scaling with an Unknown Distance Function Ⅱ,” Shepard, R. N., Psychometrica, Vol. 27, 1962, pp. 219-246.
[S69] A Nonlinear Mapping for Data Structure Analysis, Sammon, J. W. Jr., IEEE Trans. Comput., Vol. C-18, May 1969, pp. 401-409.
[T52] Multidimensional Scaling: 1. Theory and Method, Torgerson, W. S., Psychometrika, Vol. 17, 1952, pp. 401-419.
[T58] Theory and Method of Scaling, Torgerson, W. S., New York: Wiley.
[YH38] Discussion of a Set of Points in Terms of Their Mutual Distances, Young, G. and Householder, A. S., Psychometrika, Vol. 3, 1938, pp.19-22.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔