In this paper, we are the rst to construct a software programming taxonomy from Stackover ow. More precisely, we propose a machine learning based method with novel features to capture the hierarchical semantic structure of tags in Stackover ow. A graph pruning algorithm is applied to eliminate the con icts by constructing a Directed Acyclic Graph (DAG). As a result, our dataset, named Software.zhishi.schema, contains 38,205 concepts together with 36,249 subsumption relations. In order to further test the usability of our published data, we adopt a similarity computing task of words from software programming which is one of the most fundamental tasks in the software repository mining area. The results show that our dataset can outperform other knowledge bases due to its high coverage with nergrained domain concepts.
? Corresponding author 3 http://stackoverflow.com/
Unlabeled
Tag Pairs
about software programming. They can also re ect the fast changing nature of
technique terms because they are created on the y by Web users. So the large
amount of tags provide a promising way to build the taxonomy. In this paper,
we propose a machine learning based approach to construct the taxonomy. To the
best of our knowledge, we are the rst to build a software programming taxonomy
from Stackover ow. Our contributions mainly include: (
Features We adopt a classi cation model to determine the correct subsumption relation of each tag pair. The details of features we used are as follows: Lexical Feature LCS: the token-based longest common sub-string asymmetric similarity. Co-occurrence-based Features CQ: the Normalized Google Distance on the questions that the tags in the candidate tag pair have ever occurred in. CT: the Normalized Google Distance on the tags that the tags in the candidate tag pair have ever occurred with. CW: the Normalized Google Distance on the wiki descriptions that the tags in the candidate tag pair have ever occurred in. CS: the Normalized Google Distance on the sentences in all wiki descriptions that the tags in the candidate tag pair have ever occurred in. CU: the Normalized Google Distance on the users who have ever annotated the tags in the candidate tag pair. Topic-based Features TW: the KL-divergence on the topic distributions of the wiki descriptions of the candidate tag pair. TQ: the KL-divergence on the topic distributions of the randomly selected questions of the candidate tag pair. Wikipedia-based Features EW: the cosine similarity on the Wikipediabased representations (similar to ESA [1]) of the wiki descriptions of the candidate tag pair. EQ: the cosine similarity on the Wikipedia-based representations of the randomly selected questions of the candidate tag pair.
Semi-supervised Learning with Constraints The whole work ow of our
approach can be seen in Figure 1. We apply a simple but e ective semi-supervised
learning framework - self-training. Moreover, in order to avoid error propagation
to the following iterations, we add two constraints and lter out incorrect or
redundant subsumptions by leveraging the global structure information. We have
identi ed two general types of constraints in subsumption detection problem: (
DAG Construction We introduce a graph-based algorithm that works well in practice to convert subsumption relation set into an optimal tree-structured taxonomy. We rst construct a weighted directed graph from the subsumption relation set. The weight of the edge is the con dence generated by SVM classi er.Then, we apply Edmonds' algorithm4 to nd a maximum optimum branching of a weighted directed graph. The resulting taxonomy will be optimal with the sum of the edge weights is maximized. 3
Subsumption Accuracy Evaluation According to the results, the accuracy increases consistently when we perform more iterations. In particular, after the seventh iteration, the learner with constraints achieves the best accuracy of 85:96% 2:21% (1,000 samples with Wilson interval ).
Linked Data Software.zhishi.schema creates URIs for all concepts. The pattern http://seonto.apexlab.org/stackoverflow/tag/[label] comprises of two parts. http://seonto.apexlab.org/stackoverflow/tag/ is the namespace. The other part is the tag label. We use rdfs:subClassOf for subclassOf relations. When Semantic Web agents that accept \application/rdf+xml" content type access our server, resource descriptions in the RDF format will be returned. Our dataset is available at http://datahub.io/dataset/software-zhishi-schema.
Lookup Service We provide a lookup service for users to access Software.zhishi.schema. The service is available at http://seonto.apexlab.org/ lookup. Given a query, all tags whose labels exactly match the query are returned. We can click on any parent tag or child tag to switch to another page view. Such an interaction stands for navigation in our taxonomy. As a representative example shown in Fig. 2, our taxonomy contains a hyponym path like \data structures"!\tree"!\binary tree"!\binary search tree"!\avl tree".
SPARQL Endpoint We also provide a SPARQL endpoint for professional users at http://seonto.apexlab.org/sparql. 4
In this section, we investigate whether our dataset can outperform others by constructing a similarity computing experiment on terms from software programming. It is one of the most fundamental tasks in many research areas in software engineering. Unfortunately, there is no benchmark data set for semantic relatedness measuring on terms from software programming. In our experiment, we make our own data set and o er it as a standard for testing terms semantic relatedness5. We use the WUP [2] similarity as a semantic relatedness metric on our dataset. WUP similarity on WordNet and ESA [1] are used as comparison methods. We leverage Spearman rank correlation as the evaluation measure. Experimental result shows that our dataset signi cantly improves the performance of term semantic relatedness measurement. The results of WUP on WordNet and ESA are only 0.0238 and 0.2244 respectively while WUP similarity on our dataset can achieve the spearman correlation of 0.4608.
Acknowledgements This research is supported by 973 Program in China (Grant No. 2015CB352203), National Natural Science Foundation of China (Grant No. 61472242, Grant No. 61402173) and the Fundamental Research Funds for the Central Universities (Grant No: 22A201514045).