臺灣博碩士論文加值系統

一般在處理具有上下位關聯之資料時，均先將這些資料圖示成階層圖，然後再做進一步分析，以達到資料探勘的目的。然而，這類資料之實證性研究中，往往碰到資料圖示成之階層圖過於複雜，特別是因為交錯邊過多，而大大降低階層圖之可讀性與實用性。

有鑑於此，如何提高階層圖之可讀性與實用性，已逐漸受到資料分析或教育統計研究之重視。例如何氏圖、概念圖等之最新分析研究，即在解決降低交錯邊數過多之問題。

雖然，目前已有很多方法可以解決降低交錯邊過多的問題。然而，這些方法當中，常發生對某些階層圖可以有效降低交錯邊數，但對其他之階層圖時，則成效有限之問題。另外，何氏圖、概念圖等之研究中，閑少對兩種或兩種以上之分析法，進行理論性的探討。基於此，本研究擬探討上述研究中常使用之重心法（Barycentric method）；簡稱BC法與Eades＆Wormald於1994年所提出的中位數法（Median Heuristic），在二階階層圖（Bipartite Graphs）情況之下，對降低階層圖交錯數之成效與比較。

本研究主要目的有二，其一為當固定階層圖之一層，排另一層時，兩種方法在降低階層圖交錯數之成效與比較。其二為以階層圖之鄰接矩陣為基礎，同時考慮兩層的排序時，兩種方法在降低階層圖交錯數之成效與比較。

本研究主要的結果如下：
（1）當固定一層，對另一層做排序時，發現中位數法在減少交錯邊數上優於BC法；
（2）當同時考慮鄰接矩陣之行與列兩方向來排序時，BC法在減少交錯邊數上優於中位數法。

When dealing with data having upper and bottom correlations, these data will generally be diagrammed into hierarchies followed by a further analysis to understand the meanings of the data. However, the readability and practicability of hierarchies are usually descended in some recent researches because the hierarchies are mostly too complicated, especially too many crossing edges.

Therefore, how to increase the readability and practicability of hierarchies has become an important issue in data analysis and educational statistic research. Latest analysis researches like the Forrester Diagram and concept maps are famous ones dealing with such issue.

Although there are many methods able to solve the problem of too many numbers of crossings now, some of them can usually effectively descend the number of crossing edges only in certain cases while the result is limited in others. On the other hand, the studies of the Forrester Diagram and concept maps were lack of proceeding the theoretical discussions of minimizing the crossing edges. This research is, therefore, trying to discuss and compare the effects on reducing the numbers of crossings in hierarchies, comparing the Barycentric methods (i.e. BC Method) and Median Heuristic proposed by Eades and Wormald in 1994 using in Bipartite Graphs.

There are two purposes in this research. One of them is to discuss and compare the effects of the two methods on reducing the numbers of crossings in hierarchies when fixing one layer and arranging another. The other purpose is to discuss and compare the effects in two methods on reducing the numbers of crossings in hierarchies when regarding adjacency matrix as basis and simultaneously consider two layers.

We find that:
(1) when fixing one layer and only arranging another, Median Heuristic reduces more numbers of crossing edges than BC Method does;
(2) when BC Method arranges with column barycenter and row barycenter, it reduces more numbers of crossing edges than Median Heuristic arranging with column Median and row Median.

目錄

第一章 緒論…………………………………………………………………1
第一節 研究動機……………………………………………………1
第二節 研究目的……………………………………………………2
第三節 名詞釋義……………………………………………………3
第四節 研究限制……………………………………………………6
第二章 文獻探討……………………………………………………………7
第一節 重心法………………………………………………………7
第二節 中位數法 …………………………………………………13
第三章 研究結果 …………………………………………………………21
第一節 固定一層排另外一層時之比較分析 ……………………21
第二節 同時考慮鄰接矩陣之行與列時之比較分析 ……………31
第四章 結論及建議 ………………………………………………………43
第一節 結論 ………………………………………………………43
第二節 建議 ………………………………………………………43
參考文獻 ……………………………………………………………………45

一、 中文部分
陳俊宏（民95）。應用GM法於階層概念圖。台中教育大學碩士論文。
楊維楨、郭乃文(民90)。一種增進何氏圖可讀性的方法。淡江人文社會學刊, 9, 81-109。
賈蓉生、故大源、林金池(民95)。精緻離散數學。台北市：金禾資訊。
管中閔（民93）。統計學,觀念與方法。台北市：華泰文化。
廖寶貴（民95）。探討階層結構圖最少交錯邊之問題與應用－以國小一到六年級「數」概念之階層結構圖為例。台中教育大學碩士論文。
二、 英文部分
Ahmed A. A. Radwan, Moheb R. Girgis, and Alla A. Ghanem. (2002). A study of barycentre algorithm for hierarchical graph crossing minimization., International Journal of Intelligent Computing & Information Sciences, 2(2), 13-22.
Douglas B. West. (2001). Introduction to graph theory., 2nd ed, Prentice-Hall, Inc.
Eades, P., Lin, T. and Tamassia, R. (1996). An algorithm for drawing a hierarchical graph. Int. J. Comput. Geom. Appl., 6, 145- 155.
Eades, P.and Wormald, N.C. (1994). Edge crossing in drawings of bipartite graphs. Algorithmica, 11, 379-403.
Lempel, A. and Cederbaum, I. (1966). Minimum feedback arc and vertex sets of a directed graph. IEEE Trans, 4, 399-403.
Mäkinen, E. (2000). A conjecture on the error bound of the barycenter heuristic. http://citeseer.ist.psu.edu/416315.html
Michael, K. and Dorothea, W. (2000). Drawing graphs methods and models. Berlin: Springer.
Sugiyama, K., Tagawa, S. and Toda, M. (1981). Methods for visual understanding of hierarchical structure. IEEE Trans, 2, 109-125.