Shinji Kawaguchi†, Pankaj K. Garg††, Makoto Matsushita† and Katsuro Inoue† †Graduate School of Information Science and Technology, Osaka University 1-3 Machikaneyama, Toyonaka, Osaka 560-8531, Japan {s-kawagt, matusita, inoue}@ist.osaka-u.ac.jp ††Zee Source 1684 Nightingale Avenue, Suite 201 Sunnyvale, California, 94807, USA garg@zeesource.net
Abstract
Open Source communities typically use a software repos- itory to archive various software projects with their source code, mailing list discussions, documentation, bug reports, and so forth. For example, SourceForge currently hosts over seventy thousand Open Source software systems.  Because of the size of the rich information content, such reposito- ries offer numerous opportunities for sharing information among projects. For example, one would like to know a set of projects that are related or similar to each other, so that the project groups can collaborate and share their work. With thousands of projects in typical repositories, however, manually locating related projects can be difficult.  Hence, we propose MUDABlue, a tool that automatically catego- rizes software systems.  MUDABlue has three major as- pects: 1) it relies on no other information than the source code, 2) it determines category sets automatically, and 3) it allows a software system to be a member of multiple cate- gories. MUDABlue has a web interface to visualize deter- mined categories, which eases browsing a software reposi- tory. We show the effectiveness of MUDABlue's categoriza- tion capability by comparing its generated categories with that of some other existing research tools.
1
Introduction
The rapid use of Internet and Web-based technology has given rise to novel, global software archiving services, pi- oneered in the Open Source community through Source- Forge [22].  More recently, several large corporations are realizing the benefits of such services for their own, propri- etary software development. For example, Hewlett-Packard Company, IBM, Motorola, Nokia, and Xerox, are some of the corporations that are known to have deployed such archival service for their own internal corporate network. For large software archives, categorizing their contents for browsing and searching is essential for effective uti- lization of the software archive.  Automatic categorization would be helpful in several ways: ● Several similar software systems can be grouped to- gether in a category for ease of browsing. For example, SourceForge categorizes software according to their primary function (editors, databases, etc.), and also has the notion of software foundries for related software. ● Developers working on a software system may be in- formed about related software.  Finding related soft- ware systems has following advantages. 1. Developers can learn "best practices" and pro- gramming idioms from existing software sys- tems.  From related software systems, they can get strategies or hints for developing software. 2. Developers can leverage each other's work and promote more reuse.  This becomes especially useful in situations like Corporate Source [8], where global groups in companies may not be aware of the relationship among their work [11]. In the past, such relationships have been determined Manual categorization generally requires deep by hand. understanding of not only the target software system, but also other software systems and their categorization policy. With the increase in the number of software systems, e.g., SourceForge now has over seventy thousand software sys- tems registered and continues to evolve, such manual iden- tification is not enough. Automatic categorization of software systems is a novel and intriguing challenge on software archive. Past work in 1 software engineering (e.g., see [6, 21]), has focused on de- termining intra-component relations of one given software system.  We, however, propose finding inter-project rela- tions of many software systems. In this paper, we propose software automatic categoriza- tion system, MUDABlue.  It is based on Latent Semantic Analysis (LSA). LSA is a method for extracting and repre- senting the contextual-usage meaning of words by statistical computations applied to a large corpus of text [14]. LSA has found a variety of uses ranging from understanding human cognition [13] to data mining [7].  In software engineering field, it is used for clustering components in a software sys- tem [18], and recovering document-to-source links [19]. We apply LSA for automatic categorization of software systems.  To apply LSA, we consider a software system as a document and an identifier as a word.  We use LSA for retrieving categories, and then determining what software systems belong to those categories. We also implement the method and graphical user interface of retrieved categories. We define Unifiable Cluster Map method to draw a large number of categories and software systems.  It is based on Cluster Map [9].  Using the MUDABlue interface, a user can browse a software repository more naturally.
2
Software Categorization
Our categorization process consists of two steps: First step is constructing concepts that define categories for sub- jects. Second step is categorizing items, i.e., assigning items to categories. Existing researches on automatic software categoriza- tion [17, 25] have focused on only second step, categorizing items. They do not care, however, about first step, determin- ing categories. Their methods require manual determination of category sets. They are inadequate considering that the definition of category sets have major implications for the categorization results, and difficulties of constructing cate- gory sets increases in proportion to the number of subjects. Categorization made by hand is typically based on us- age of software systems.  We hypothesize, however, that it is also useful to categorize based on the software's in- ner structure.  For example, there are categorization based on its architecture (GUI application, CUI based filter, or server application) and categorization based on required li- braries (MFC, GTK or regexp library). To reflect such inner structures in categorization, we need detailed knowledge of many libraries and architectures.  Thus, automating such categorization is important. Additionally, the existing researches categorize each software system into one category.  Therefore it is hard to accommodate a variety of categorization criteria into a sin- gle category hierarchy. In Figure 1, software 1 and 2 have functionality for editing (inserting text, overwriting, delet- ing, copying, etc.) and are categorized as 'editor'. Further- more, software 1 and 3 are implemented with MFC library. Then thus they could be categorized into a same category. It is hard to represent such characteristics for categoriza- tion which does not allow overlapping.  In our previous work [12], we have tried to measure similarities between software systems. We applied LSA to software systems and found that software similarity values are reflected only by most influential aspects of software systems. For example, the similarity value between database software with GTK interface and editors using GTK is very high, despite dif- ferences in their usage.  The results indicate that software systems have multiple 'functional aspects.' Thus, catego- rization which allows overlapping is more suitable for soft- ware categorization. On the basis of stated above, we list the required charac- teristics for an ideal automatic software categorization:
1. Don't need pre-defined categorizations.
Category sets should be generated automatically. This is because a software system has several attributes, such as usage, architecture and depended library. Mak- ing category sets reflecting all these attributes is hard to determine a priori. 2. Allow a software system to be a member of multiple categories. Software systems can be categorized with functional aspects on a non-exclusive basis.  If a categorization is mutually exclusive, the categorization may capture only a few functional aspects.
3. Rely on source code only.
Some software systems have various artifacts like de- sign documents, build script, and so on.  Although these artifacts have highly abstracted information com¬ pared to source code, the amount and quality of documents are quite different with software systems. In contrast, source code is usually available for all projects, or at least the ones worth categorizing. Thus, we should use nothing but source code.  Depending on only source code enlarges the applicability of the method.
3
MUDABlue Method
In this paper, we propose automatic software categoriza- tion method implementing the three characteristics stated above.  At first, we introduce LSA used by MUDABlue method. Then, we show key idea of how to retrieve cate- gories automatically and explain our automatic categoriza- tion method.
3.1
Latent Semantic Analysis
LSA is a practical method for the characterization of word meaning. LSA produces measures of word-word, and passage-passage relations which are well correlated with se- mantic similarity [14]. The method creates a vector descrip- tion of documents. This representation is used for compar- ing and indexing documents, and various similarity mea- sures can be defined. Consider the six simple documents in Table 1. In LSA, these documents are represented by a matrix shown in Ta- ble 2.  Each column represents a document and each row represents a word which appears in the documents.  Cell entries show the occurrence of the word in the document.

Table 2. An Example of LSA Matrix
Each row vector of this matrix indicates the characteris- tics of the word through the whole documents occurrences. This row vector can be used to determine the similarity of two words.  A simple similarity definition used here is cosine of two vectors. In LSA, single value decomposition (SVD) is applied to the matrix.  SVD is a form of factor analysis, and acts as a method for reducing the dimensionality of the matrices. Why does LSA apply such translation?  This is because a simple term-by-document matrix does not capture relation- ship among terms.  Two documents show high similarity only when the documents have some same words; however, there are many synonyms. Thus similar documents do not always share completely same words.  They may contain many synonyms. Using SVD, LSA can retrieve such undi- rected relationship among documents.  For more details, please see [14].
3.2
Retrieving Category
To retrieve categories from various software systems, we focus on identifiers (variable names, function names, and so on).  Such identifiers are usually labeled according to their contents and deeply relate to the behavior of source code. For example, identifier “gtk_window” represents some window, and source code near “gtk_window” will contain some GUI operation on the window. As stated above, identifiers may represent a part of functions implemented in the program. Thus we as- sume that semantically related identifiers retrieved from many identifiers represent one “concept.” “gtk_window”, “gtk_main” and “gpointer” seem to indicate that such identifiers would be contained in GTK related software sys- tem. We define such a derived concept as a "category." Then, we define that if a software system has iden- tifiers contained in a category, that software belongs In this way, if we to the category (Figure 2). can retrieve "editor" category which contains identifiers “cut, copy, paste” and “MFC” category which con- tains identifiers "CWindow, CMenu." Software 1 in Fig- ure 2 belongs to both "editor" category and "MFC" cate- gory. To determine relationships between identifiers, we use LSA. LSA calculates the similarity values between words. LSA is purely statistical method and can be applied without any human knowledge. At the same time, the similarity val- ues of LSA reflect highly the semantic relationship among words.  Using LSA, we can get right relationships, even if there are many synonyms and homonyms.
Overview of MUDABlue Method
3.3
As stated in Section 3.2, MUDABlue retrieves highly re- lated identifiers, and considers them as a category.  In this section, we show how to retrieve categories concretely. Fig- ure 3 shows a dataflow of MUDABlue method. MUDABlue method consists of 7 parts, each explained below:
1. Extract identifiers.
First, we extract all identifiers from source codes of software systems.  From identifiers, we exclude re- served because they have no relation with software features.  We also cut out comments.  The reason is that amount and quality of comments in each software system vary widely, and many software systems have copyright notice or license terms in comments.
2. Create identifier-by-software matrix.
Considering a software system as a document and an identifier as a word, we create an identifier-by-software matrix, similar to the word-by-document matrix of Ta- ble 2. 3. Remove useless identifiers. Before performing LSA, we remove identifiers that appear in only one software system, or in more than half of software systems. Identifiers appearing in only one software system are not meaningful in LSA. And, identifiers appearing in more than half of software sys- tems are probably a general term and have no affect on categorization.
4.  Apply LSA.
We perform LSA for the identifier-by-software matrix without meaningless identifiers. 5. Retrieve categories using similarities between identi- fiers. From the matrix of LSA result, we compute similari- ties between all pairs of identifiers.  As stated above, we use cosine criterion for the similarity of each iden- tifiers. Thereafter, we apply cluster analysis using cal- culated similarities. The cluster analysis is a statistical analysis method that classifies individuals into clusters based on the similarity among individuals.  We call a cluster of identifiers an "identifier cluster."  We con¬ sider each identifier cluster as a category. 6. Make software clusters from identifier clusters. From each identifier clusters, we retrieve software sys- tems that contain one or more identifiers in the cluster, and make them a corresponding software cluster. 7. Make software cluster's titles. Although we obtain software clusters by previous steps, each software cluster needs description that ex- plains what software systems are included.  To gen- erate titles, we sum all identifier-vectors comprised in the identifier cluster.  We use ten identifiers that have highest values in the summation vector.
4
MUDABlue System
We implemented the MUDABlue method described in Section 3.3. To facilitate utilization of categories, we devel- oped a graphical interface for browsing software repository.
Figure 3. Algorithm of Retrieving Categories
Using our GUI, one can grasp a good overall picture of a software repository. MUDABlue system consists of two parts: (1) database, and (2) user interface.  Database part retrieves categories from source code contained in a software repository, and stores them into the database.  User interface part enables browsing the software repository using categories stored in the database. In this section, we give an explanation of Unifiable Clus- ter Map (UCM). UCM is developed to display relationships among categories and software systems graphically. Then we describe each part of MUDABlue system.
Unifiable Cluster Map
4.1
To draw categories retrieved by MUDABlue method, two requirements must be fulfilled.  It must draw multiple memberships and have high scalability.  Considering such requirements, we define a Unifiable Cluster Map method to draw categories and software systems based on Cluster Map [9]. In Cluster Map, a category is represented as a node (right side of Figure 5). A category is represented as a black node with a light-gray label. A charcoal gray square represents a cluster of elements.  Elements belonging to the same cate- gories are grouped into one cluster. The numeric characters inside the squares shows what elements are contained in the clusters. Edges between a category node and a cluster cir- cle indicate elements inside the circle belonging to the cat- egory. In the right side of Figure 5, the item 1 and 2 belong to the category A and B. Cluster Map method draws multi- ple memberships in smart way.  However, it does not have enough scalability. To adapt for dozens of categories, we define UCM. In UCM, you can refine categories by unifying categories in- teractively.  For instance, UCM draws some categories lo- cated higher position in the category hierarchy at first.  If the user has some interest in a category, the user can expand it and get more detailed categories. If a particular category is not what the user wants, the user can collapse it. Figure 4 shows how to unify categories. We would unify the category B and C. If the category B and C are unified, the cluster 1, 2 and 3 relate same categories. Thus, cluster 1, 2 and 3 are unified. Generally, if two categories are uni- fied, we also unify all clusters which relate same categories. Repeating such unification, a highly abstracted figure is ob- tained like Figure 5.
Database
4.2
Database part retrieves categories using the method de- scribed in Section 3.3, and stores them into a database. Database part requires name of software systems and their source codes.  It assumes that there is a directory for each software system, and source code is placed under the di- rectory.  All these directories are placed under a directory specified in a configuration file.
4.3
User Interface
Our system has a web-based interface (Figure 6).  This interface consists of four parts.  The top part is a keyword input box.  The middle of the page is Unifiable Cluster Map view (UCM view).  The left side of bottom is cate- gory hierarchy view, and at the right side of bottom is cate- gory/software list view. Keyword input box provides the ability to search cate- gories and software systems with given keyword. UCM view provides the whole picture of a software repository. It draws categories, software systems, and their relationships.  In UCM view, categories are arranged in a hierarchy by their similarities. UCM provides the brief map of categories and aids the exploration of details for inter- ested users. Category hierarchy view is another hierarchical view of categories. It presents category tree in direct way. If a user already has a desired category, he or she can access the cat- egory directly using this view. Category/software list view shows the result of keyword search or selected category/software in the UCM view or category hierarchy view.  The list of category shows se- lected categories and their software systems and the list of software systems shows selected software systems. In both pages, the category name and software name are links for detailed information pages. All components in MUDABlue interface collaborate closely with each other. If a category was selected in UCM, the category is selected in category hierarchy view and cat- egory/software list view, too, and vice versa. In this section, we present explanation about category hierarchy view, and how to construct hierarchy among cat- egories at first. Then we explain UCM view.
Category hierarchy view
4.3.1
In category hierarchy view, the automatically determined categories are reconstructed into hierarchy and similar cate- gories are arranged close to each other. In this way, the user can grasp the outline of categories more easily. To determine category hierarchies, we define quantita- tive similarity between categories.  In this paper, we use odds ratio with some modification. The odds ratio is a gen- eral measure for relationship between two categories.  Say there is population S ' and its subsets A , B ⊂ S ' , our odds ratio or' ( A, B ) is defined as below:
where
We apply cluster analysis to categories using or' ( A, B ). Then we make the dendrogram of categories used for the category hierarchy view.
Unifiable cluster map view
4.3.2
Category hierarchy view enables viewing categories along with their relationships with each other. This view, however, does not present any information about the contained soft- ware systems. To grasp the overview of a software reposi- tory, such a view is insufficient. In Figure 6, the middle of the interface is UCM part.  A category is represented as a black node with a light-gray label. A group of software systems is represented as a char- coal gray square.  An edge between a category node and a software group square depicts the fact that the software systems belong to the pointed category.  The retrieved cat- egories are unified using UCM method described in Sec- tion 4.1. The user can expand and collapse the categories interactively. The user can double-click the category node and expand it to determine its children categories.  If the user turns the mouse wheel up, the selected category is col- lapsed again. We use TouchGraph [24] library to implement UCM view.  TouchGraph is graph drawing library.  It dynami- cally arranges nodes by their edge connection, and allows the user to move nodes around the screen.
Experimentation
5
We have conducted some experiments with the MUD- ABlue software categorization system. The overall goals of our experiment were: Does our prototype properly catego- rize by target systems compared with existing manual cat- egorization?  Can our prototype categorize by the libraries used by the subject software systems?
5.1
Experiment Process
We collected sample data from SourceForge, selecting 41 C programs in five categories from SourceForge.  The list of categories and software systems are shown in Table 3. Then we ran MUDABlue for the 41 programs. Next, we evaluate the result using precision and recall. For this work, we define precision and recall from the view point of “Compared to an ideal categorization, how specific and exhaustive is the categorization determined by MUD- ABlue?" Let S' be a set of all software systems contained in a repository. Precision and recall are defined as:

Table 3. The list of sample software systems

where C MUDABlue(s) is a set of categories containing software s , generated by MUDABlue, C Ideal(s) is a set of categories containing software s , determined manually by the experimenters.  In both of the criteria, larger value is preferable. Besides precision and recall, we also employ F-Value to be an integrated measure for performance evaluation.  F- value is harmonic average of precision and recall, denoted as
5.2 Result
Table 4 shows excerpt of categories generated by MUD- ABlue.  A row represents one category.  Each column rep- resents title of the category, software systems belong to the category and the number of identifiers constructing the cat- egory. We got 40 categories in this experimentation.  18 cat- egories are the same as defined manually in SourceForge, and 8 categories are new categories based on depending li- braries and architectures. All 8 new categories are No.3, 35 (YACC category), No.8, 9 (GTK category), No.22 (regexp category), No.25 (JNI category), No.30 (getopt category) and No.32 (Python/C category). In Table 4, categories No.1, 2, 4, 5, 6, 7 and 10 are the same category as SourceForge, and categories No.3, 8 and 9 are new categories. Category No.3 contains software sys- tems using YACC, and category No.8 and 9 contain soft- ware systems using GTK library.
Figure 7 shows the result of recall and precision. We also shows the result of GURU [17] and SVM based method pro- posed by Ugurel et al. [25] (SVM stands for Support Vec- tor Machine).  They proposed automatic software catego- rization methods using information retrieval (IR) technique similar to MUDABlue.  GURU applied free-text indexing approach for software categorization. They retrieved infor- mation from Unix man pages and categorized Unix tools. Ugurel et al.  applied SVM to documents of software sys- tems to categorize software systems based on their usage. In this graph, points located in the upper right area im- ply good result i.e. both precision and recall are high. This graph indicates that MUDABlue categorizes software with higher precision and recall, when compared to some ex- isting systems.  Actually, the F-Value of MUDABlue is 0.72 while the best F-Value of GURU is 0.6591 (where precision = 0.9 and recall = 0.52) and of SVM is 0.6531 (where precision = 0.66 and recall = 0.65)
Discussion
6
MUDABlue categorization method
6.1
In this paper, we have confirmed that MUDABlue can properly categorize based on not only usages but also archi- tectures and depended libraries. For instance, MUDABlue retrieved GTK category, YACC category and JNI category. Considering MUDABlue needs no human knowledge about software systems, if a new library would appear, MUD- ABlue will follow the new library without any human oper- ation. While MUDABlue got higher score over other research tools for precision and recall, comparing such values di- rectly does not capture the essence of MUDABlue's ad- vantage over them. The reason is that MUDABlue is com- pletely different in some regards, as described below. MUDABlue generates categories by itself, and does not use a pre-defined category set.  Additionally, MUDABlue allows a software system to belong to multiple categories. Such differences are desirable characteristics for software categorization. Thus, the result indicates that MUDABlue has better precision and recall, and provides some additional suitable characteristics. Another major difference between MUDABlue and other research tools is subject of IR method. MUDABlue applies LSA to source codes. In contrast, the existing tools (SVM and GURU) apply IR method to software documents.  As mentioned in Section 2, depending on documents is not rea- sonable in the Open Source context because of the disparity of their amount and quality. About titles of a cluster, some titles are easy to under- stand, and others are not. Categories No.4 and 6 have ti- tles easy to understand, like "AVI" and "board, ply".  Gen- erally, categories based on depending libraries or architec- tures tend to have comprehensible titles. In contrast, cate- gories which are based on software usage tend to have ob- tuse titles like category No.1.  This is because identifiers typically have names related to the domain, not the domain name itself.
MUDABlue interface
6.2
MUDABlue provides several ways to browse a software repository.  Such hybrid methods are implementable and useful. Frakes et al. [10] empirically investigated what sev- eral presentation methods' effectiveness.  They state that "There were no significant differences in search effective- ness." and "Even though the methods were not significantly different in terms of recall and precision, they found differ- ent items."  Hence, we believe that more than one method should be presented to the user, rather than any given single browsing interface. To draw overlapping categories, we used Cluster Map method, derived from the concept of Venn diagrams, with some customizations.  InfoCrystal [23] is another research derived from Venn diagrams.  In InfoCrystal, a Venn dia- gram is exploded into disjoint subsets.  Next, the subsets were represented by icons whose shapes reflect the num- ber of criteria satisfied by their contents.  Dividing to the subsets, InfoCrystal adapts to the growth of categories. In- foCrystal, however, draws an n-polygon as outer frame of the figure, thus if there were dozens of categories, the fig- ure would be hard to read. Also, InfoCrystal has no way of collapsing categories. Another way to draw overlapping categories is arrang- ing all elements according to their belongings.  Sakai et al. [20] and Allan et al. [1] propose such methods.  These research works arrange elements belonging to same cate- gory closely and vice versa. In these ways, elements visu- alization is achieved reflecting relations in overlapping cat- egories. They, however, treat categories as just constraints and do not visualize what elements belong to the categories. 7
Related Work
In this section, we will review researches about appli- cation of IR method for software engineering world.  Re- searches about automatic software categorization and about UCM are mentioned at section 6. From the viewpoint of retrieving information from source code, some existing clustering methods cluster one software system into some functional parts for program understanding.  Such software clustering methods use La- tent Semantic Analysis [18], Self-Organizing Map [4], file structure and file names [2] or structure of program like call graph [5, 16]. They divide one software systems into some "component" (i.e. source file, function, and so forth). Some research works apply IR method to retrieving reusable components from a software system. These method search components highly related with a given query.  For example, CodeBroker [26] is one of the com- ponent retrieving systems for Java language.  CodeBroker present methods highly related with a given query. To deter- mine relationship between a method and a query, it applies LSA to a query and JavaDoc comment of methods. Marcus et al. [19] proposed a method automatically re- covering links between source codes and design documents. Their method applies LSA to comments of source codes and design documents. Then, they calculate similarity and re- cover the links. Lucca et al. [15] apply SVM to bug tracking system. They use SVM to decide responsible person of new bug en- try. They compare new bug entry and all submitted entries using SVM and suggest the person who is responsible for similar entries. Brun [3] uses SVM and decision tree for software fault identification. At first, some test software systems are pre- pared.  Half of them contain errors and the others are not. Next, some properties are retrieved from the test software systems and SVM and decision tree learner are trained with the properties.  The learner is used to determine whether given software system contains error or not.
Conclusion
8
In this paper, we have proposed MUDABlue method, an automatic categorization method for a large collection of software systems.  MUDABlue method does not only cat- egorize software systems, but also determines categories from the software systems collection automatically.  We have shown MUDABlue method can categorize without any knowledge about target software systems.  Then, we im- plemented MUDABlue interface, a category-based software repository browsing system. MUDABlue enables browsing a repository categorized, where a software system can be- long to multiple categories. For future works, we will apply our method to various, more large-scale data sets.  While we examine our method with 41 software systems, real software archives are larger. Increase of software systems would improve the result of LSA because LSA retrieves latent relation using statisti- cal method. To experiment with a large-scale data set, im- proving scalability of MUDABlue will be essential. At the present time, most time-consuming process is cluster anal- ysis of all identifiers.  We need to use some approximate algorithm and reduce the computational effort. Although MUDABlue automates categorization of a software archive, it does not accept any human guidance. Combining our automated categorization and human guid- ance may result in a powerful classification.