Lin, X. (1997). Map displays for information retrieval. Journal of the American Society for Information Science, 48(1), 40-54.

Lin, X. (1997). Map displays for information retrieval. Journal of the American Society for Information Science, 48(1), 40-54.

information visualization/self-organizing map

本研究分析瀏覽做為資訊檢索方式的適用性以及各種以瀏覽為基礎的視覺化組織格式。

資訊檢索包含搜尋及瀏覽兩種方式。若是要將瀏覽應用做為一種資訊檢索的方式，必須考慮 1)資訊項目需要具有良好的組織結構，2)使用者有需要探索他們不熟悉的集合內的資訊項目，3)使用者不了解集合內的資訊組織並且希望有較低認知負荷的探索方式，4)使用者對表達他們的資訊需求有困難和5)使用者能夠識別他們想要的資訊，但很難描述它們。

為了在資訊檢索服務提供瀏覽方式，需要將大量的資訊項目進行視覺化組織，並且希望能夠保留資訊的結構與關係，以提供使用者能有效地運用他們的視覺能力。因此本研究也比較階層式、網絡式、散佈式和地圖式等四種視覺化組織形式的特性與優缺點。

1) 階層式顯示的優點在於能夠藉由分層、分支與分群等方式簡化複雜的資料結構，可以同時表現出資訊的全體性質與區域性質，而且可以將觀看者的注意力集中在適當的廣度上。但若是資訊本身的結構不是階層式時，階層式結構往往過度簡化；此外，若是資訊空間較大時，較難產生與顯示階層式結構；並且使用者在選擇接下來要瀏覽的分支時需要較大的認知負荷。

2) 網絡式顯示以圖形上的節點代表資料項目，使用者在瀏覽時可以循著節點之間的連結線找到相關的資料項目。相較於階層式顯示，網絡式顯示能夠表示更複雜的結構，應用的範圍較廣。但也因為如此，當網絡結構較為複雜時，使用者可能不容易理解。

3) 散佈式顯示運用映射演算法將高維度的資料對應到二維的圖形平面上，並且這樣的映射過程必須使資料間原先的距離關係得以盡量保存在對應後的結果上。散佈式顯示非常適用於表現資料的整體型態，並且能夠展現出資料的意義結構。

4) 地圖式顯示劃出成若干區塊，每個區塊代表一個可能的主題(由一組相關的詞語組成)，區塊的尺寸大小表現主題的重要性(愈出現的詞語在地圖上佔有愈大的區塊，而其出現的)，區塊之間的距離遠近則表現出主題之間的關連程度，距離愈近的區塊表示主題之間愈相關。作者並認為地圖式顯示兼具前三者顯示方式的優點，也就是可以包含階層式顯示的階層的叢聚，網絡式顯示的相關連結，以及散佈式的空間映射方式。有別於前三者，地圖式顯示方式並不直接輸出最後文件資料映射到圖形上的結果，而是產生一個關聯式網路(associative network)。

本研究以三個文件資料集做為範例，以SOM做為地圖式顯示的方法，並且運用不同的索引(文件特徵)方式代表這些資料集內的文件資料。

(1) 311篇多語言資料檢索(multilingual information retrieval)主題相關的論文，以論文題名中出現的85個詞語為特徵，特徵向量上每個成分為是否有出現的二元值。結果發現地圖上的區域能代表論文的主題，區域的大小與主題出現的論文數量有關，較常出現的主題佔有較大的面積，相連的區域表示這些主題曾經共同在論文內出現。

(2) 660篇研究者個人蒐集的論文，以論文題名、關鍵詞及摘要出現的1472個詞語為特徵，特徵向量上每個成分為詞語在該篇論文資料的出現次數乘上詞語的倒文件頻率(inverse document frequency)。結果發現地圖上的區域能表示研究人員感興趣的主題，區域的面積愈大表示研究人員對這個主題愈重視；當論文映射到自組織映射圖上相對應的位置時，也可以發現論文的分布情形。

(3)143篇1990-1993年間SIGIR的會議論文，以論文題名出現的154個詞語為特徵，特徵向量上每個成分為詞語在該篇論文的題名、關鍵詞及摘要等資料的出現次數。產生的地圖作為資訊檢索的互動介面，可以增減自組織映射圖上出現的詞語數量，並可以點選圖上的任一區域檢索相關的論文。

Computers are expected to be used to reveal associations and properties of electronic information to allow people to use their visual capabilities for information seeking (Veith, 1988) .

The map display attempts to show both contents and semantic structures of a document space by mapping major concepts and documents of a document space to a two-dimensional map. It preserves, as faithfully as possible, document semantic relationships and reveals these relationships through various visual components of the display. 

Most users have difficulty specifying their needs by a specific query formulation; even if users are successful in doing so, systems have difficulty retrieving all relevant documents without overwhelming the users with irrelevant documents. The issue of precision/ recall has been a bottleneck for retrieval systems: Retrieving more relevant documents (high recall ) is often at the price of getting more irrelevant documents (low precision) .

Visual displays that show terms and document relationships and reveal underlying structures of the document space will be such browsing aids that will relax demands on the performance of retrieval mechanisms and query generations. Such displays will allow the user to interact and browse a large quantity of search results in a limited display space.

Browsing is a direct application of human perception for information seeking, both in the electronic and non-electronic environment (Chang & Rice, 1993) . Browsing is explorative; it is an interactive process in which one will scan large amounts of information, perceive or discover information structures or relationships, and select information items through focusing one’s visual attention.

In relation to information retrieval, browsing is particularly useful when:

1) There is a good organizational structure and related information items are often located near each other (Thompson & Croft, 1989).

2) Users are not familiar with the content of the collection and they need to explore the collection (Motro, 1986).

3) Users have less understanding of how information is organized in the system and they prefer to take a low  cognitive load approach to explore the system (Marchionini, 1987) ,

4) Users have difficulties in articulating their information needs (Belkin, Oddy, & Brooks, 1982).

5) users look for information that is easier to recognize than to describe (Bates, 1986) .

Some techniques that researchers have explored to support browsing for information retrieval include:

1) displaying a dynamic hierarchical information structure (Frei & Jauslin, 1983) ,

2) providing an overview map of the information space (Halasz, Moran, & Trigg, 1987) ,

3) providing a neighborhood map for each item (Thompson & Croft, 1989) ,

4) showing both a miniature of the entire information space and a detailed local map (Beard and Walker, 1990) ,

5) distorting the display so that the center of focus will be shown in more detail than other areas—the fish-eye views (Furnas, 1986) , and

6) supporting interactive functions such as zoom in, zoom out functions so that the user can select different level of details to display (Schatz & Caplinger, 1989) .

A central issue of organizing information for visualization is what formats and features of visual displays will help to organize large amounts of information to reveal information structures and to support effective use of human visual capabilities.

Hierarchical displays simplify complex data structures and separate data into different levels, branches, or clusters. These functions help to represent both global and local views of data, to utilize the display screen effectively, and to direct the viewer’s attention to the appropriate level of generality.

Cutting, Karger, Pedersen, & Tukey, (1992) showed that hierarchical clustering could be an effective information access tool, particularly for browsing.

These disadvantages of hierarchical displays include (1) oversimplification of structures for certain data, particularly for those that are more appropriate to be represented by structures other than a hierarchy, (2) difficulty in generating and displaying hierarchical displays for large information spaces, and (3) increased cognitive load for users who are forced to make selections among the hierarchical branches, especially when the whole hierarchy is not displayed on the screen.

Network displays show associative structures on the screen and let the viewer follow the links to browse items represented by the nodes. ... They can represent more general and complicated structures than hierarchical displays can. ... However, if all the relationships in a complex document space are displayed in a network, the network display simply becomes a network maze. The network displays thus often present more information than the user can immediately comprehend (Beard & Walker, 1990) .

Scatter displays refer to the graphical (dotted) image resulting from mapping high-dimensional data to a two-dimensional visual space. ... Most of the scatter displays are generated automatically by mapping algorithms. Because the mapping is usually driven by an error-minimum process or by the principle of finding a display configuration whose overall layout most closely matches the structure of the given data, the mapping creates a spatial orientation that reflects the overall layout of underlying data.

Scatter displays are very useful in revealing underlying data structures of statistical data (Tufte, 1983) . In particular, scatter displays can also be used to reveal semantic or intellectual structures embedded in statistical data.

Among the three display formats reviewed, scatter displays most faithfully reflect underlying data structures. In a scatter display, the viewer is not constrained to follow predetermined links as in the network display or to follow a rigid hierarchical structure in the hierarchical display. However, this lack of regularity in the scatter display also poses problems for the viewer trying to discover the underlying structure. In this respect, the scatter display particularly needs the help of other context or interactive probes such as verbal labeling or mouse sensitive areas.

Compared to the physical space, the document space is much less clearly defined in terms of its measurement, its dimensionality, and its semantic relationships, all of which largely depend on the selected indexing process. ... It would be difficult to have a map that is a ‘‘true’’ representation of the document space like the geographical map is for the physical space. ...  The map displays should also provide rich visual information, and be able to present dynamic displays at different detail levels to allow the user to interact with the underlying information.

The map display was designed to provide the advantages of mapping, linking, and clustering as in the scatter displays, network displays, and hierarchical displays reviewed earlier.

The mapping algorithm selected will keep the display structure as similar to the underlying data structure as possible.

With an appropriate indexing, Kohonen’s feature map algorithm can be used to ‘‘survey’’ contents of a document space, to ‘‘detect’’ semantic relationships of terms and documents, and to generate map displays that will show both contents and semantic relationships of documents.

Kohonen’s feature map algorithm takes a set of input objects, each represented by an N-dimensional vector, and maps them onto nodes of a two-dimensional grid.

The mapping procedure is a recursive learning process of the following:
1) Select an input vector randomly from the set of all input vectors,
2) find the node (which is also represented by an N-dimensional vector called weights) closest to the input vector in the N-dimensional space,
3) adjust weights of the node (called the winning node) , so that it will more likely be selected again if this input is presented later,
4) adjust the weights of those nodes within a neighborhood of the winning node, so that nodes within this neighborhood will have similar weight patterns.
This process goes through many iterations until it converges, i.e., the adjustments all approach zero.

To ensure its convergence, two control mechanisms are imposed.
The first is the updating parameter. It approaches to zero as the number of iterations increases.
The second is the neighborhood structure that shrinks gradually during the process. A large neighborhood will achieve ordering and a small neighborhood will help to achieve a stable convergence of the map (Kohonen, 1989) . By beginning with a large neighborhood and then gradually reducing it to a very small neighborhood, the feature map achieves both ordering and convergence properties.

Early applications of the algorithm mostly demonstrated that the feature map could preserve metric relationships and the topology of input patterns.

I. A Map Display for a Retrieved Set of Documents

This example used a set of documents retrieved by a search done on INSPEC database in DIALOG for the topic of multilingual information retrieval. The set contains 311 documents. The indexing for this document set was based on titles only. ... As the result, 85 terms were retained to index the document set. A vector of 85 dimensions was created for each document, where a component was a ‘‘1’’ if the corresponding term occurred in the document title and a ‘‘0’’ otherwise. The document vectors were used as input to train a feature map of 85 input features and 10 by 14 output nodes arranged in a grid.

Results:

The areas on the resulting map can be seen as concept areas(more precisely, word areas) . 
The size of the areas corresponds to the word occurrence frequencies.
The neighboring relationships of areas indicate frequencies of the co-occurrence of words represented by the areas.

A Map Display for a Personal Collection

The second example is a map display for a personal document collection. The collection contained 660 documents, which were accumulated over many years as a by-product of a researcher’s research activities. ... The indexing for this collection was fulltext-based—every word in the titles, keywords, and abstracts was used. After the stopword-removing and stemming procedures, and the elimination of the most-frequently and the least-frequently occurring terms, 1,472 terms remained in the indexing list. To create the indexing vectors, weights of each term were computed based on both the term frequency and the inverse document frequency. The 660 document vectors of 1,472 dimensions were then used as input to train a 10 by 14 Kohonen’s feature map of 1,472 input features.

Results:

The map display generated shows the researcher’s major research areas and the relationships of these areas.
The size of areas, corresponding to the frequencies of the words, indicates relative importance of the areas to the researcher (the more often a word appears in the personal collection, the more likely the word will correspond to a large area in the space) .
The neighboring relationships, corresponding to the frequencies of co-occurring words, reflect degrees of word associations as derived from the researcher’s collection.
When each document in the collection was mapped to a position on the display, the document distribution over the map display can also be shown.
The map can also reveal migration of the researcher’s interest over time.

A Map Display for Conference Proceedings

The third example is about documents from 1990–1993 SIGIR conference proceedings. These proceedings contain 143 documents. The indexing terms for this collection were collected from titles only, but the weights of terms were computed based on the term frequency in titles, keywords, and abstracts. ... After the same stopword-removing, stemming procedures, and elimination of the most- and the least-frequently occurring terms, 154 terms were used to index the collection, resulting in 143 vectors of 154 dimensions. These vectors were then used to train a 14 by 14 feature map of 154 input features.

As a mapping tool, the feature map has the properties of economic representation of underlying data and their interrelationships ( in these examples, the feature map self-organizes major terms selected from hundreds or thousands of indexing terms to represent the document spaces) .

As a visualization tool, the feature map produces rich geographical features that can be used for visual inferences. The algorithm generates an associative network as the output, rather than the direct mapping of the input. This makes it easy to implement various interactive tools and provide different ‘‘views’’ of the underlying information.

Finally, that the algorithm allows classification of any input to more than one location is certainly beneficial to information retrieval.

A major challenge to the success of document mapping is how to evaluate map displays and how to compare different map displays. ... This result suggests that comparisons of map displays need to be done on how the map displays help the user locate documents, not just how they look. It is quite possible to have different organizations of map displays that can provide the same level of access to a document space.