Analysing Text in Software Projects

Most of the data produced in software projects is of textual nature: source code, specifications, or documentations. The advances in quantitative analysis methods drove a lot of data analytics in software engineering. This has overshadowed to some degree the importance of texts and their qualitative analysis. Such analysis has, however, merits for researchers and practitioners as well. In this chapter, we describe the basics of analysing text in software projects. We first describe how to manually analyse and code textual data. Next, we give an overview of mixed methods to automatic text analysis including N-Grams and clone detection as well as more sophisticated natural language processing identifying syntax and contexts of words. Those methods and tools are of critical importance to aid in the challenges in today's huge amounts of textual data. We illustrate the introduced methods via a running example and conclude by presenting two industrial studies.

Introduction
Most of the data we produce in software projects is of textual nature. It starts with requirements specifications over designs and documentation to customer surveys. Textual data, however, is notoriously difficult to analyse. We have a multitude of techniques and tools which are well known to software developers to process and analyse quantitative data. We handle numbers of bugs or lines of code very often. Yet, what should we do with all the textual data? So far, the potential of analysing this data is not used.
Hence, software analytics for practitioners does already (and will even more) involve how to make use of all this textual data. Fortunately, we have seen an interesting development in the research area of analysing texts. This is often promoted under the umbrella text mining or text analytics. Both mean roughly the same thing: systematically retrieve and analyse textual data to gain additional insights, in our case additional insights into the software development project.
In this chapter, we will first discuss and categorise where and what kind of textual data we usually encounter in software projects. Based on this categorization, we will discuss the sources of this textual data and how to retrieve them. Next, we will introduce manual coding and analysis as a very flexible but elaborate means to structure and understand different texts. As a means to handle large amounts of text and reduce the manual effort, we will discuss a sample of the nowadays available automatic analyses of texts such as N-Grams or clone detection.
Finally, we will employ a running example of textual data which we will analyse with each presented analysis approach. We use the publicly available specifications of the HTTP and IMAP protocols as typical representatives for textual requirements specifications. In case of automatic analyses, we will provide references to the used tools so that the examples can easily be reproduced.

Textual Software Project Data and Retrieval
Textual data appears at many points in a software development project. The main result of a software projectthe code -is also textual although we are more concerned with natural language text in this chapter. Yet, source code usually contains also a considerable share of natural language text: the code comments. Apart from that, we have requirements specifications, architecture documentation or change requests with textual data. There is no generally agreed on classification of the artifacts generated in a software development project and, hence, also not about textual data contained in these artifacts. As a foundation for the remainder of this chapter, we will therefore first discuss different sources for textual data and then classify them to describe how to retrieve the data for further analysis.

Textual Data
Sources for Textual Data. Although we often consider software developers to be people dealing mostly with formal languages, i.e. programming languages and alike, there are many sources for textual data in a software project. Most of this data comes from the developers themselves. A substantial part of any high-quality source code consists of informal or semi-formal text code comments. These already contain smaller inline comments as well as longer descriptions of interfaces or classes (as e.g. with JavaDoc for Java). Apart from that, depending on the development process followed, there are many other documents written by the developers or other people in related roles such as testers, software architects or requirements engineers. This then includes requirements specifications, design and architecture documents, test cases, test results and review results. Yet, we need to think also beyond the "classical" artifacts in software development. Team members nowadays communicate via e-mails and chats, change requests and commit messages which all are available electronically as text sources. Finally, in a software project, especially in the context of product development, customer surveys and product reviews are a common means to better understand the requirements for and satisfaction with a software product. These artifacts can contain also open questions which result in textual data to be analysed.
A Classification of Textual Software Project Data. We found the general structure of the German standard software process model V-Modell XT 1 to be useful to classify artefacts related to software engineering as it is rather general and applies to many application domains. It contains several detailed artefacts that we do not consider in our classification of textual software project data, but we follow the general structure. The classification is shown in Figure 1.
The V-Modell XT structures the textual artefacts mainly along different process areas or disciplines in the development process. This starts with documents for contracting such as requests for proposals or offers. One could, for example, be interested in analysing public requests for proposals to investigate technological trends. Next, there are several textual documents in project planning and control. An example that could be interesting for text analytics are risk lists from projects where we could extract typical risk topics to define mitigation points. We classified the above mentioned e-mails under reporting which could give relevant insights into the communication between developers or between developers and customers. A now commonly analysed area in software engineering research is configuration and change management. Problem reports, change requests and commit messages all contain valuable textual information about a project's progress. With evaluation, we mean artifacts related to evaluating other artifacts in the project, for example test case specifications. We could analyse, for instance, the terminology used in the test cases and compare it to the terminology used in the code. The next three categories correspond to the constructive phases of the project: requirements and analysis, software design and software elements. All contain valuable information about the product. In the latter, we see also the code and with it the code comments in which we can check the used language by text analytics. Finally, the logistic elements contain any further documentation which could also be analysed for the discussed topics and for relationships between documents.
Running Example. As a running example for the remainder of this chapter, we chose the specifications of internet protocols. They are openly available examples of software requirements specifications. The IETF publishes all open protocols as so-called Requests for Comments (RFC) and, hence, these documents are called RFC XXXX where "XXXX" is the number of the specification. We selected standards around two well-known internet protocols: HTTP and IMAP. We hope that by choosing these, we avoid lengthy introductions and potential misunderstandings about the domain. HTTP (Hypertext Transfer Protocol) is the application-level internet protocol for most network applications today. IMAP (Internet Message Access Protocol) allows access to mailboxes on mail servers. For methods that require a larger corpus, we add additional RFCs to the corpus that are related to HTTP or IMAP.
The following is a part of RFC 2616 of the specification of HTTP 1.1. It describes valid comments in the HTTP header. It shows that our examples contain text that is similar to text in other requirements specifications: Comments can be included in some HTTP header fields by surrounding the comment text with parentheses. Comments are only allowed in fields containing "comment" as part of their field value definition. In all other fields, parentheses are considered part of the field value.
Yet, also other kinds of text need to be analysed. In our industrial studies in Section 5, we see that free-text answers in surveys are usually not well-formed, complete sentences. Also code comments are often not complete sentences. Although we will not discuss this in detail in the following, most techniques are able to cope with this.

Text Retrieval
With the various sources and classes of different texts in software engineering projects, the first step is to collect or retrieve these texts from their sources. A complete text corpus, consisting of different texts, will often come from different sources and we want to keep connections between the texts as stored in the sources. For example, we often have pointers from the commit messages in the version control system to specific change requests in the change management system. These links are useful for further analysis and should be retrieved. Figure 2 gives an overview of such retained links between texts in the text corpus. In the following, we will go through the categories of textual project data from Section 2 and discuss the sources and possible links between texts.  The texts in the supply and contracting category are often not stored with most of the other project documentation. They are usually held either in the form of a formatted document on a file server or part of a larger enterprise resource planning (ERP) system. Hence, we either need to access the file server and extract the plain text from the formatted document or access the ERP system which usually has some kind of API to retrieve data. We should aim to keep links to the actual project in terms of project IDs or something similar.

Change
Similarly, planning and control texts are also often kept as formatted documents on file servers or in ERP systems. Then, they need to be treated in the same way as supply and contracting texts. They have a better chance, however, to be also kept in a version control system. For example, the above mentioned risk lists can be maintained also as plain text and, therefore, easily handled in Subversion 2 or Git 3 . Then, we can use the APIs of the corresponding version control system for retrieval. It also allows us to retrieve different versions and, hence, the history of documents which can be necessary for temporal analyses.
Reporting can be done in formatted documents, ERP systems as well as version control systems. Quality status reports can also be automatically generated by quality control systems integrated with the continuous integration system. For example, SonarQube 4 or ConQAT 5 can be used to auto-generate quality reports based on data from various sources. These reports can be directly used if they can be retrieved. Usually they provide the possibility to put the report as a file on a server, into a version control system or into a database. They often provide links to the artifacts analysed which should be retained if possible. E-mail can be most easily retrieved if a central mail server is used for the project. While most textual data we retrieve is sensitive, with e-mail we need to take the most care not to violate privacy rules established in the organisational context. It is advisable to anonymise the data already at this stage and only keep, for example, links to specifications or code explicitly referenced in the e-mails.
Texts from configuration and change management are programatically easy to obtain as they are nowadays stored in databases in most companies. We have the above mentioned version control systems, ticketing systems, e.g. OSTicket 6 , and change or issue management systems such as Bugzilla 7 or Atlassian Jira 8 . They all provide APIs to retrieve the contained text. Depending on the system and possible naming conventions, we can retrieve, besides the texts, links between commit messages and change requests or between problem reports and change requests.
The further categories are supposed to be held mostly in version control systems. Exceptions can be evaluation (i.e. test or review) reports that sometimes are stored separately on file servers. Also user survey results can be easiest to retrieve by going directly to the online survey servers used. They often provide some kind of API or export functionalities. Otherwise, we need to write a web crawler or retrieve it manually. To be able to retrieve code comments, we also need to write an extraction tool that is able to distinguish between code and comments. It can also be useful to distinguish different types of comments as far as this is possible in the retrieval directly. This could also be a further step in the analysis.

Manual Coding
Once we collect textual data for its analysis and interpretation, it needs to be structured and classified. This classification is often referred to as coding where we identify patterns in texts, having an explanatory or a exploratory purpose [1] and serving as a basis for further analysis, interpretation and validation. Coding can be done in two ways: manually or automated. In this section, we introduce coding as a manual process. A detailed example for applying the manual coding process is provided in Section 5.1.
Although manual coding is often associated with interview research, the data we code is not limited to transcripts as we can structure any kind of textual data given in documents, Wikis or source code (see also Section 2.2). This kind of structuring is used in social science research and also gains attraction in software engineering research. An approach commonly used in these research areas is Grounded Theory. We briefly describe Grounded Theory in Sidebar 1, but its theoretical background is not necessary for many practical text analysis contexts.

Coding Process
Manual coding is a creative process that depends on the experiences, views and interpretations of those who analyse the data to build a hierarchy of codes. During this coding process, we conceptualise textual data via pattern building. We abstract from textual data, e.g. interview transcripts or commit comments stated in natural language, and we build a model that abstracts from the assertions in form of concepts and relations. During this coding process, we interpret the data manually. Hence, it is a creative process which assigns a meaning to statements and events. One could also say that we try to create a big picture out of single dots.
There are various articles and textbooks proposing coding processes and the particularities of related data retrieval methods such as why and how to build trust between interviewers and interviewees (see e.g. Birks and Mills [1]). The least common denominator of the approaches lies in the three basic steps of the coding process itself followed by a validation step: Manual coding, as discussed in this chapter, has its origins in Grounded Theory (GT). Because GT is the most cited approach for qualitative data analysis [1] which comes at the same time with a plethora of different interpretations, we briefly clarify its meaning in a nutshell. GT describes a qualitative research approach to inductively build a "theory", i.e. it aims at generating testable knowledge from data rather than testing existing knowledge [1]. To this end, we thus make use of various empirical methods to generate data, and we structure and classify the information to infer a theory. A theory, in its essence, "provides explanations and understanding in terms of basic concepts and underlying mechanisms" [2,3]. In empirical software engineering, we mostly rely on the notion of a social theory [4] and refer to a set of falsifiable and testable statements/hypotheses. As most qualitative research methods, Grounded Theory has its origins in social sciences and it was first introduced in 1967 by Glaser and Strauss [5]. A detailed introduction into the background of Grounded Theory and the delineation with similar concepts arising along the evolution of Grounded Theory is given by Birks and Miller in [1]. For the remainder of the chapter where introduce a manual coding process, we rely on the terms and concepts as introduced in context of Grounded Theory.
Sidebar 1: Grounded Theory in a Nutshell

1.
Open coding aims at analysing the data by adding codes (representing key characteristics) to small coherent units in the textual data, and categorising the developed concepts in a hierarchy of categories as an abstraction of a set of codes -all repeatedly performed until reaching a "state of saturation".
3. Selective coding aims at inferring a central core category.
4. Validation, finally, aims at confirming the developed model with the authors of the original textual data.
Open coding brings the initial structure into unstructured text by abstracting from potentially large amounts of textual data and assigning codes to single text units. The result of open coding can range from sets of codes to hierarchies of codes. An example is to code the answers given by quality engineers in interviews at one company to build a taxonomy of defects they encounter in requirements specifications. During open coding, we then classify single text units as codes. This can result, for example, in a taxonomy of defect types, such as natural language defects which can be further refined, e.g. to sentences in passive voice. During axial coding, we then can assign dependencies between the codes in the taxonomies. For example, the quality engineers could have experienced that sentences in passive voice have frequently lead to misunderstandings and later on to change requests.The axial coding process then would lead to a cause-effect chain that shows potential implications of initially defined defects. The final selective coding then brings the results of open and axial coding together to build one holistic model of requirements defects and their potential impacts.
We subsequently form a process that we applied in our studies and which worked well for us. Figure 3 depicts the basic coding process and further steps usually (or ideally) performed in conjunction with the coding process.
The idea of (manual) coding -as it is postulated in Grounded Theory -is to build a model based on textual data, i.e. "grounded" on textual data. As the primary goal is to gather information out of text, we need to follow a flexible process during the actual text retrieval and the coding process as well. For example, in case of conducting interviews, we perform an initial coding of the first transcripts. In case we find interesting phenomena for which we would like to have a better understanding of the causes, we might want to change the questions for subsequent interviews; an example is that an interviewee states that a low quality of requirements specifications has also to do with a low motivation in a team leading to new questions on what the root causes for a low motivation are. We thereby follow a concurrent data generation and collection along with an emerging model which is also steered according to research or business objectives. Figure 4 shows the coding steps for our running example. During the open coding step (lower part of the figure), we continuously decompose data until we find small units to which we can assign codes ("concept assignment").

Axial Coding
Open Coding

Decomposition of Data
Concept Assignment

Assignment of Dependencies
Selective Coding

Identification of Core Category
Coding Process Text Retrieval

Figure 3: Coding process
This open coding step alone shows that the overall process cannot be performed sequentially. During the open coding step, we found it useful • to initially browse the textual data (or samples) before coding it to get an initial idea of its content, meaning and, finally, of potential codes we could apply, • to continuously compare the codes during coding with each other and especially with potentially incoming new textual data, and • to note the rationale for each code down to keep the coding process reproducible (of special importance if relying on independent re-coding by another analyst).
Having a set of codes, we allocate them to a category as a means of abstraction. In our running example, we allocate the single codes to the categories "entities" and "dependencies". During axial coding, we then assign directed associations between the codes. Finally, the last step in the coding process is supposed to be the identification of the core category, which often can be also predefined by the overall objective; in our case, it is "Operation".
The overall coding process is performed until we reach a theoretical saturation, i.e. the point where no new codes Most HTTP communication is initiated by a user agent and consists of a request to be applied to a resource on some origin server. In the simplest case, this may be accomplished via a single connection (v)between the user agent (UA) and the origin server (O).

Concept Assignment
Entities Categorization

Challenges
The introduced coding process is subject to various challenges, of which we identify the following three to be the most frequent ones.
Coding as a Creative Process. Coding is always a creative process. When analysing textual data, we decompose it into small coherent units for which we assign codes. In this step, we find appropriate codes that reflect the intended meaning of the data while finding the appropriate level of detail we follow for the codes. This alone shows the subjectivity inherent to coding that demands for a validation of the results. Yet, we apply coding with an exploratory or explanatory purpose rather than with a confirmatory one. This means that the validation of the resulting model is usually left to subsequent investigations. This, however, does not justify a creationist view on the model we define. A means to increase the robustness of the model is to apply analyst triangulation where coding is performed by a group of individuals or where the coding results (or a sample) of one coder are independently reproduced by other coders as a means of internal validation. This increases the probability that the codes reflect the actual meaning of textual units. We still need, if possible, to validate the resulting model with the authors of the textual data or the interviewees represented by the transcripts.
Coding Alone or Coding in Teams. This challenge considers the validity of the codes themselves. As stated, coding (and the interpretation of codes) is a subjective process that depends on the experiences, expectations and beliefs of the coder who interprets the textual data. To a certain extent, the results of the coding process can be validated (see also the next paragraph). Given that this is not always the case, however, we recommend to apply, again, analyst triangulation as a means to minimise the degree of subjectivism.
Validating the Results. We can distinguish between an internal validation, where we form, for example, teams of coders to minimise the threat to the internal validity (the above mentioned analyst triangulation), and external validation. The latter aims at validating the resulting theory with further interview participants or people otherwise responsible for the textual data we interpret. This, however, is often not possible; for example, in case of coding survey results from an anonymous survey. In such cases, the only mitigation we can opt for is to give much attention to the internal validation where we try to increase the reliability of the theory during its construction, e.g. by applying analyst triangulation.

Automated Analysis
As any manual coding and analysis of textual data is difficult, largely subjective and very elaborate, automation can have a huge positive effect. Especially in the recent years, automated natural language processing has made progress we can exploit for analysing software data. We cannot replace reading a complete introductory book on natural language processing with this chapter. Yet, we will concentrate on a selected set of promising techniques and corresponding tools that can give us insight into software engineering data complementing manual coding.

Topic Modelling
We often want to get a fast overview of what different texts are about, for example to decide what to read in-depth or to simply classify the texts. Topic modelling is an automatic approach that attempts to extract the most important topics per text document. The basic assumption of topic modelling [6] is that documents are created using a set of topics the authors want to describe and discuss in the documents. The topics might, however, not be explicitly specified in the documents and remain only implicitly in the heads of the authors. Nevertheless, for each topic, the authors still use certain words in the documents. Therefore, for this analysis, we say that a topic is formed by a set of related words. Hence, there are probabilities with which certain words appear in the context of several topics. Topic modelling makes use of this by aiming to extract these probabilities and thereby recreating the topics. Figure 5 shows the whole process from document creation based on topics and the subsequent topic modelling to rediscover the topics. Hence, the user of topic modelling does not have to specify any topics to look for in the documents, but they are extracted from the text.
Mathematically, we need an algorithm which is able to group the words extracted from documents into probable topics. The most common one used is Latent Dirichlet Allocation (LDA) [7] but there are others to choose from. The concrete algorithm is mostly uninteresting for the user of the topic modelling method, because all algorithms are not exact. An exact algorithm is impossible to define as the goal (the topics) are not clearly defined. The algorithms typically start by assigning topics to words randomly and then use Bayesian probability to incrementally refine the assignment. Finally, when an equilibrium is reached and the assignments cannot be improved, we have the most probable topics for the corpus of documents.
The uses for topic modelling of software engineering data are vast. For example, if we have a larger body of existing specifications to which our software has to conform, we can generate a network of documents based on the topics they share. Fortunately, there is open and usable tool support for building topic maps. Mallet 9 is written in Java and allows users either to run it using the command-line or include it into their own analysis software using an API. Hence, topic modelling is a useful tool for getting an overview of a large corpus of documents.  By applying topic modelling to our running example of RFC specifications using Mallet, we can reconstruct several useful topics related to HTTP and IMAP. Figure 5 also illustrates some of the rediscovered topics. The top topic for the URI specification contains server, message, client and standards. For the HTTP specification, we get the terms request, response, header and http, and for the IMAP specification command, mailbox, message, and http. Not every word in each topic is helpful. Some can even be confusing, such as http in IMAP, but most of the topics give a good idea what the specification is about. Furthermore, each document can have more than one topic. Figure 5 shows this by the thickness of the arrows.
A simple alternative for small documents, which are not suitable for topic modelling, are word clouds (see also Section 4.5) and counts. They cannot show semantic relationships between words but infer the importance of words by their frequencies. Available web tools, such as Voyant 10 , can also show the context in which chosen words appear in the text and, thereby, provide an initial semantic flavour.
Topic modelling can only give a rough idea what are the main topics consisting of important words. The further analysis and interpretation needs manual effort. Yet, especially for larger text corpora, topic modelling can be an interesting pre-analysis before manual coding. The topics found can form initial ideas for coding, and we can mark context in which they were found to be checked in detail by the coder.

Part-of-Speech Tagging and Relationship Extraction
A way to further dig into the meaning of a large text corpus is to analyse its syntax in more detail. A common first step for this is to annotate each word with its grammatical task. This is also referred to as part-of-speech (POS) tagging. In its simplest form, it means extracting which word is a noun, verb or adjective. Contemporary POS taggers [8] are able to annotate more, for example the tense of a verb. The taggers use machine learning techniques to build models of languages to be able to do the annotations.
We see an example sentence from the HTTP 1.0 specification in Tab. 1. We POS-tagged this sentence using the Stanford Log-linear Part-Of-Speech Tagger [9]. The tags are attached to each word with a " " as separator.
They use a common abbreviation system for the POS. For example, "DT" is a determiner and "NN" is a singular noun. The full list of abbreviations can be found in [10]. Original sentence from RFC 1945 The Hypertext Transfer Protocol (HTTP) is an application-level protocol with the lightness and speed necessary for distributed, collaborative, hypermedia information systems.
This allows us to extract the main nouns which probably form a part of the domain concepts of the specified system. In the example, if we combine consecutive nouns, we will find "Hypertext Transfer Protocol", "HTTP", "protocol", "lightness", "speed" and "hypermedia information systems". These nouns capture already a lot of the main concepts of the specification. We can further qualify them with adjectives. For example, the specification is not only about hypermedia information systems but about "collaborative" hypermedia information systems. Yet, we also see a problem in this kind of analysis in this example. The word "distributed" is tagged as verb (VBN) instead of an adjective which would probably distort an automated analysis.
The possibilities of further analysis having the POS tags in a text are very broad. A concrete example of exploiting this in the context of software engineering is to extract domain information from a specification to generate design models or code skeletons. For example, Chen investigated the structure of English prose specifications to create entity-relationship (ER) diagrams [11]. Put very simply, he maps nouns to entities and verbs to relationships. For example, the sentence Most HTTP communication is initiated by a user agent and consists of a request to be applied to a resource on some origin server.
from RFC 1945 can be transformed into the five entities HTTP communication, user agent, request, resource and origin server. They are connected by the relationships is initiated by, consists of, to be applied to and on. The resulting ER diagram is shown in Figure 6. Similar approaches were proposed by Abbott [12] to create a first skeleton of Ada code based on a textual specification or by Kof [13] who has built an ontology from a textual specification to infer initial component diagrams and message sequence charts. All these approaches can help to bridge the gap from textual specifications to further, more formal artefacts. Yet, a multitude of other applications of POS tagging are also possible on other kinds of textual software engineering artefacts. For example, we can assess the quality of requirements specifications by detecting requirements smells such as passive voice [14]. Furthermore, it can help as a preprocessing step in manual coding by highlighting nouns, adjectives, and verbs with different colours to quickly grasp the main concepts.

N-Grams
Computational linguists are looking for ways to predict what a next word in a sentence could be. One way to achieve this is by looking at the immediately preceding words. "On the basis of having looked at a lot of text, we know which words tend to follow other words." [15] Hence, we need a way of grouping these preceding words. A popular way is to construct a model grouping words having the same preceding n − 1 words. This model is then called an n-gram model. An n-gram is a contiguous sequence of n words in a piece of text. The n-gram-based analysis of texts is not aiming at abstracting the content of the texts but to categorise or predict attributes of them.
n-gram models have received a lot of interest in the last years. Part of the interest comes from the availability of the Google Ngram Viewer 11 for the books digitised by Google. It can show the percentage of an n-gram in relation to all n-grams of all books per year. For example, for the 2-gram "software engineering", we can see a spike in the early 1990s and a mostly flat line since the 2000s. So, one application of n-grams is to compare how frequently words occur together in different texts or over time.
Another interesting application of n-grams is for categorising texts into their languages. Based on already learned models for different languages, it can indicate in which language is a given text. Imagine, your company policy is to write all documents in English, including specifications and code comments. Then, an analyser using the n-gram models could look for non-english text in code and other documents. Another example is to automatically classify specification chapters into technical content and domain content. A useful tool in that context is the Java Text Categorizing Library (JTCL) 12 . It comes with n-gram models for a set of languages and is also capable of being trained for other categories. When we sent the RFC specification documents we use as running example into JTCL, it correctly classified them as being written in English.
There are further uses of n-gram models in software engineering. Hindle et al. [16] investigated the naturalness of source code. They built n-gram models for source code and then predicted how to complete code snippets similar to auto completion in modern IDEs. Allamanis and Sutton [17] built on the work by Hindle et al. and created n-gram language models of the whole Java corpus available in GitHub. Using these models, they derived a new kind of complexity metric based on how difficult it is to predict the sequence of the given code. The intuition behind this complexity metric is that complex source code is also hard to predict. Hence, the worse the prediction matches the actual source code piece, the more complex it is. These applications are not ripe for wide-spread industrial use but show the potential of the analysis technique.

Clone Detection
Clone detection is a static analysis technique born in code analysis but usable on all kinds of texts. It is a powerful technique to get an impression of the syntactic redundancy of a software, and it is highly automated at the same time.
What Is a Clone?. A clone is a part of a software development artifact that appears more than once. Most of the clone detection today concentrates on code clones but cloning can happen in any artifact. In code, it is usually the result of a normal practice during programming: Developers realize that they have implemented something similar somewhere else. They copy that part of the code and adapt it so that it fits their new requirements. So far, it is not problematic, because we expect that the developer will perform a refactoring afterwards to remove the introduced redundancy. Often, however, this does not happen, either because of time pressure or because the developer is not even aware that this can be a problem.
A developer most often does not create an exact copy of the code piece but changes some identifiers or even adds or removes some lines of code. The notion of a clone incorporates that, too. To identify something as a clone, we allow normalization to some degree, such as different identifiers and reformatting. If complete statements (or lines of text) have been changed, added or deleted, we speak of gapped clones. In clone detection, we then have to calibrate how large this gap should be allowed to be. If it is set too large, at some point everything will be a clone. Yet, it can be very interesting to see clones with 3 to 5 lines difference.
As mentioned above, clone detection is not restricted to source code. If the particular detection approach permits it, we can find clones in any kind of text. For example, we have applied our clone detection tool on textual requirements specifications and found plenty of requirements clones. We will discuss this study in detail in Section 5.2. This works because clone detection in the tool ConQAT 13 is implemented based on tokens which we can find in any text. Only normalization cannot be done because we cannot differentiate identifiers.
Impact of Cloning. It is still questioned today in research if cloning is really a problem [18] while Martin states that "Duplication may be the root of all evil in software" [19]. There are many factors influencing the effects of cloning. In our studies, however, we found two clearly negative impacts of cloning.
First, it is undeniable that the size of the software becomes larger than it needs to be. Every copy of text adds to this increase in size which could be avoided often by simple refactorings. There are border cases where a rearranging would add so much additional complexity that the positive effect of avoiding the clone would be compensated. In the vast majority of cases, however, a refactoring would support the readability of the text. The size of a software codebase is correlated to the effort needed to be spent to read, change, review, and test it. The review effort increases massively, and the reviewers become frustrated because they have to read a lot of similar text.
Second, we found that cloning can also lead to unnecessary faults. We conducted an empirical study [20] with several industrial as well as an open source system in which we particularly investigated the gapped clones in the code of those systems. We reviewed all found gapped clones and checked whether the differences were intentional and whether they constitute a fault. We found that almost every other unintentional inconsistency (gap) between clones was a fault. This way, we identified 107 faults in five systems that have been in operation for several years. Hence, cloning is also a serious threat to program correctness.
Clone Detection Techniques. There are various techniques and tools to detect clones in different artifacts [21]. They range from token-based comparison [22] over the analysis of abstract syntax trees [23] to more semanticsclose analyses such as memory states [24]. In the following example, we work with the tool ConQAT mentioned above. It is applied in many practical environments to regularly check for cloning in code and other artifacts.
The measure we use to analyse cloning is predominantly clone coverage which describes the probability that a randomly chosen line of text exists more than once (as a clone) in the system. In our studies, we often found code clone coverage values for source code between 20 % and 30 % but also 70 % to 80 % is not rare. The best code usually has single digit values in clone coverage. For other artifacts, it is more difficult to give average values but we have also found clone coverage up to 50 % in requirements specifications [25].
In general, false positives tend to be a big problem in static analysis. For clone detection, however, we have been able to get rid of this problem almost completely. It requires a small degree of calibration of the clone detection approach for a context but then the remaining false positive rates are neglectable. ConQAT, for example, provides black listing of single clones and can take regular expressions describing text to be ignored, such as copyright headers or generated code. Finally, we use several of the visualizations the dashboard tool ConQAT provides to control cloning: A trend chart shows if cloning is increasing or a tree map shows us which parts of our systems are affected more or less strongly by cloning.
Running Example. We now run the standard text clone detection of ConQAT on the HTTP and IMAP RFCs. By inspecting the found clones, we find several false positives, for example the copyright header which is similar in all documents. While these are copies, we do not care because we do not have to read them in detail or compare them for differences. We ignore the headers by giving ConQAT a corresponding regular expression. Figure 7 shows an example of a remaining clone in RFC 2616. It describes two variations of HTTP types which are mostly the same. A manual check of what is the same and what is different between the two clone instances would be boring and error-prone. Hence, clone analysis could be used to point to text parts that should be removed and, thereby, make understanding of the specifications easier. Overall, we have a clone coverage of 27.7 % over all 11 analysed documents from the HTTP and IMAP specifications. The clone coverage is rather evenly distributed as shown in the tree map in Figure 8. The tree map displays each file as a rectangle. The size of the rectangle is relative to the size of the file and the color indicates the clone coverage. The more red a rectangle is, the higher the clone coverage for this file. This can give us a fast overview of even a large number of documents.
Manual coding as well as automatic techniques, such as POS tagging or topic modelling, aim at providing a concise abstraction of the text. We can use it to describe, summarise, and better understand the text. Clone detection, however, has the goal to describe the redundancy created by copy&paste in the text. Hence, a possibility is to use clone detection as a first analysis step to exclude clones from the further analysis. Simply copied texts will otherwise distort the other analyses.

Visualization
"A picture is worth a thousand words." is a cliché but a graphical visualization can help strongly in understanding the results of text analyses. In the previous sections, we have already seen a tree map in Figure 8 to get a quick overview of cloning in different text files. It could be used to visualize the distribution of all kinds of metrics over files. A further visualization was the ER diagram in Figure 6 which shows the domain concepts in a text in an abstract form well known by computer scientists. The support for analysts by visualization is a very active research area, often denoted by the term visual analytics. Also for visualising unstructured textual data, several new methods and tools have appeared over the last years. Alencar et al. [26] give a good overview of this area. We will base our discussion on their work and only highlight three exemplary visualizations.
Word Cloud. A nowadays well known, simple but effective visualization of text is called word cloud, tag crowd 14 or wordle 15 . Different implementations give different concrete visualizations but the idea is always to extract the most frequent words and show them together with the size of each word in relation to its frequency. Our example of the HTTP and IMAP RFCs gives us the word cloud in Figure 9. A useful tool for that is Voyant 16 which we have already mentioned in the context of topic modelling (Section 4.1). It can create a word cloud out of a text corpus and allows interactively to change its appearance, include stop word lists (to avoid having "the" as the largest word) and click onto any word to see its frequency and context. The word cloud in Figure 9 was created using Voyant. A word cloud can be a good first step for finding the most important terms in a set of texts. For example, it could be an input into a manual coding process for identifying a set of prior codes likely to appear often in the texts.
Phrase Net. A comparable visualization that adds a bit more semantics is a Phrase Net [27]. It not only presents very frequent words but also their relationship to other frequent words. The kind of relationship can be configured: for example, the connection of both words by another word such as "the" or "is" can be a relationship. Figure 10 shows a Phrase Net for the RFC corpus with the selected relationship "is". It shows frequent words, the larger the more frequent, as well as arrows between words that are connected by an "is". The arrow becomes thicker the more frequent the relationship occurs in the text. For example, the RFCs contain often the word "response" -as we already saw in the word cloud -but we additionally see that "response" is frequently connected by "is" to "state-based" and "cacheable". If the data can be publicly accessible, the IVM Many Eyes 17 system is an easy tool to create Phrase Nets. It is a more complicated visualization than word clouds but also gives more information. It could be used as an alternative to create domain models as with part-of-speech tagging (Section 4.2) or to check and extend those domain models. Furthermore, it could provide a more comprehensive input to manual coding as it not only contains single words but important relationships between words.
Temporal Change. A next step in visualising textual data has been to introduce a further dimension in the visualization such as the change over time in texts. This can be interesting for the analysis of several versions of a document or survey results collected regularly. We can see changes in the interest in different topics, for example. Havre et al. [28] propose ThemeRiver to visualise topics as streams horizontally over time with the thickness of the stream in relation to the strength of the topic at that point in time. Chi et al. [29] extend this with their approach TextFlow which adds specific events extracted from the texts such as the birth or death of a topic to the streams. At present, there is no tool available to perform this kind of analysis.
We sketched a text flow of the different versions of the RFC on HTTP in Figure 11 to show the concept. We see that in 1996, the stream for "request" is bigger than for "response" and, hence, was more often used. This changes in the later versions. The word "header" comes only in as a very frequent word in 1997 and continues to increase in importance in 1999.

Two Industrial Studies
We further illustrate the application of text analytics in software engineering by two industrial studies: first, a survey on requirements engineering we manually coded and analysed, and, second, clone detection on requirements engineering which we combined with manual coding of the found requirements clones.

NaPiRE: A Requirements Engineering Survey
We conducted this survey study in 2013 as a collaboration between TU München and the University of Stuttgart. We have been working with industrial partners on requirements engineering (RE) for several years and had a subjective understanding of typical problems in this area. Yet, we often stumbled on the fact that there is no more general and systematic investigation of the state of the practice and contemporary problems of performing requirements engineering in practice. Therefore, we developed a study design and questionnaire to tackle this challenge called Naming the Pain in Requirements Engineering (NaPiRE). While you are not likely to perform the same study, the way we analysed the free-text answers to our open questions is applicable to any kind of survey. You can find more information on the complete survey in [30,31] and on the website: http://www.re-survey.org/.
Goals and Design. Our long-term research objective is to establish an open and generalisable set of empirical findings about practical problems and needs in RE that allows us to steer future research in a problem-driven manner. To this end, we want to conduct a continuously and independently replicated, globally distributed survey on RE that investigates the state of the practice and trends including industrial expectations, status quo, experienced problems and what effects those problems have. The survey presented in the following describes the first run of our survey in Germany.
Based on these goals, we developed a set of research questions and derived a study design and questionnaire. For most of the aspects we were interested in, we designed closed questions that can be analysed with common quantitative analyses from descriptive statistics. Often we used the Likert-scale from "I fully agree" to "I do not agree at all" to let the survey respondents rate their experiences. We complemented closed questions often with an open question to let the respondents voice additional opinions. At the end of the questionnaire, we asked open questions about the personal experiences with requirements engineering in their projects. Our design included a manual analysis using manual coding (Section 3) of all the textual data we would get from the open questions. We wanted to derive an improved and extended understanding of potential problems which we then include in the closed questions of the next survey run. The context was that we first asked about normative standards, defined by external parties, that they use for improving their requirements engineering practices. An example of such a standard would be the Capability Maturity Model Integration (CMMI) of the U.S. Software Engineering Institute and adaptations of that standard for requirements engineering. We were interested in how satisfied the respondents are with such standards and, in turn, why they did not use them. Answers included "We want to live our own agility.", "We do not use any standard" and "I am not convinced of the external standards." The second question we look at provoked longer answers from most respondents. It is also the one where we could get the most from with our manual coding later. It reads: Considering your personally experienced most critical problems (selected in the previous question), how do these problems manifest themselves in the process, e.g., in requests for changes?
We had presented a set of problems we encountered in practice before in the previous question. Now, we wanted to better understand what problems the respondents consider most critical. From this, we wanted to learn about the context of the problems, potential causes and candidates for new problems. The answers we got included "Requirements emerge and change priority once the system is deployed. Again, this is no problem but the environment. It becomes a problem if you're not prepared to deal with it." and "Hard negotiations regarding the CR/Bug question, mostly leading to bad relationship with the customer on project lead level." Coding Process and Challenges. For analysing the free-text answers, we followed the manual coding procedure as introduced in Section 3. However, we already have a predefined set of codes (given RE problems) for which we want to know how the participants see their implications. For this reason, we have to deviate our procedure from the standard procedure and rely on a mix of bottom-up and top-down. We start with selective coding and build the core category with two sub-categories, namely RE problems with a set of codes each representing one RE problem and Implications which then groups the codes defined for the answers given by the participants. For the second category, we conduct open coding and axial coding for the answers until reaching a saturation for a hierarchy of (sub-)categories, codes and relationships.
During the coding process, we had to tackle several challenges. One was the lack of appropriate tool support for manual coding, especially when working in distributed environments. Another one was the missing possibility to validate the results by getting feedback from the respondents. Figure 12 sketches our procedure we followed during manual coding. . During this open coding step, we decomposed the data relying on spread sheets and worked with paper cards where we also denoted the rationale for selected codes. In a third step, we arranged the cards according to categories by using a whiteboard. A third analyst then repeated, as a validation step, independently the open coding process on a sample.
Coding Results. Due to the resulting complexity in the given answers and resulting coding scheme, we describe the results step-wise. To this end, we first introduce the full results from the open coding, followed by the full results of the axial coding. In a last step, we present a condensed overall view of the results as a graph with a minimal saturation. We show only those results having a minimal occurrence in the answers to include only those in our theory. Figure 13 summarises the full results from the open coding. We distinguish a hierarchy of categories as an abstraction of those codes defined for the answers given in the questionnaire. For each code, we furthermore denote the number of occurrences. Not included in the coding are statements that cannot be unambiguously allocated to a code, for example, the statement "never ending story" as an implication of the problem "Incomplete / Hidden requirements".  participants also stated, however, reasons for the problems and occasionally also how they would expect to mitigate the problem. As shown in Fig. 13, we thus categorise the results into the pre-defined category RE Problems, Implications, and the additional category Reasoning.

RE
Regarding the implications, we distinguish three sub-categories. Consequences of problems in the RE phase itself, consequences to be seen in further phases of the SW life cycle other than RE and more abstract consequences on the overall project quality. The highest occurrence of statements is given for the code Change Request being stated 22 times. Other codes resulted from only one statement, but they were unique, specific formulations that could not be merged with other statements. For instance, the code Weak Relationship Customer & Project Lead in the category Overall SW Project Quality resulted from a statement which we could not allocate to another code without interpretation and potentially misinterpreting the statement (given that no validation with the respondents is possible).
Regarding the reasoning for given RE problems, we distinguish the category Rationale as a justification of why particular problems occurred, and Improvement/Mitigation for statements that suggested how to mitigate particular problems. The first category can be further divided into Factors in RE and General Factors.
Also here, we encountered very mixed statements including detailed ones we had to allocate to codes having in the end only one occurrence and vague statements we could accumulate with (consequently vague) codes. Subsequent original statements shall give an impression about the answers given: Code Missing Abstraction from Solution Level: "Stakeholders like to discuss on solution level, not on requirements level. Developers think in solutions. The problem is: even Product Managers and Consultants do it." Code No RE explicitly planned (in tendering): "A common situation is to take part in a tender process -where requirements are specified very abstract -most of these tender processes do not include a refinement stage, as a supplier we are bound to fulfill vague requests from the initial documents." Code Weak Communication: "The communication to customer is done not by technicians, but by lawyers." Code Too Ambitious Time Planning: "Delivery date is known before requirements are clear." Code Implicit Requirements not made explicit: "Referencing common sense as a requirement basis." Code Failed Acceptance: "After acceptance testing failed, the hidden requirements came up and had to be fixed on an emergency level." Code Missing Coordination of Interdisciplinary Teams: "Missing coordination between different disciplines (electrical engineering, mechanical engineering, software etc.)." The axial coding defines the relationships between the codes. As a consequence of the categories introduced in the previous section, we distinguish two types of relationships: 1. The consequences of given RE problems to the category Implications, and 2. The consequences of the codes in the category Reasoning to the RE problems including rationales and improvement suggestions.
We cannot show the full results of the axial coding here. We further refrain from interpreting any transitive relationships from reasonings to implications because of the multiple input-/output-relationships between the codes of the different categories; for instance, while "Too ambitious Time Planning" was stated as an exclusive reason for "Time Boxing" as an RE problem, the problem "Incomplete / hidden Requirements" has multiple reasons as well as multiple consequences.
We are especially interested in a condensed result set that omits the codes and the dependencies with limited occurrences in corresponding statements. The reason is that we need a result set with a minimal saturation to propose its integration into the questionnaire for the next run of the survey. After testing the results with different values for the minimal occurrences, we defined a graph including only codes with a minimal occurrence level of 7. This resulting graph is shown in Fig. 14. Nodes represent a selection of codes and edges represent a selection of relationships between nodes.
With the chosen minimal occurrence level, the final graph does not include statements coded in the category

Clone Detection in Requirements Specifications
We performed this case study in 2009 in a collaboration between TU München and itestra GmbH as an exploratory study on the extent of cloning in commercial requirements specifications. We had a subjective feeling that there is a lot of textual redundancy in those specifications from the experiences with project partners but we had not investigated systematically before. All details of the study can be found in [25]. It is an example for clone detection on natural language texts (Section 4.4) as well for manual coding (Section 3).
What Is the Problem with Clones in Specifications?. Requirements specifications are a central artifact in most software development processes. They capture the goals of the software to be developed and constitute the connection between the customer/user and the developers. Many call the specifications the determining part for project success or failure. Yet, as with any other development artifact, requirements specifications contain redundancy. Semantic redundancies are the source for many potential problems in a development project but are also extremely hard to detect. Yet, there are also syntactic redundancies: Specifications are written by people who tend to copy (and adapt) text if they need similar things at different parts of the document or different documents. These syntactic redundancies can be found by clone detection (see Section 4.4).
In our collaborations with various industry partners on their requirements engineering processes, we often found syntactic redundancies in their specifications. They lead to various problems. The most direct is the sheer increased size of the specifications which, in turn, leads to higher efforts for reading, reviewing and changing them. In addition, similar to code cloning [20], redundancy can introduce inconsistencies. The copies of the text drift apart over time as some copies are adapted, for example to changes in the requirements of the customer, while others are forgotten. We now have conflicting requirements and the developers can introduce faults into the software. Finally, an undesired effect of clones in requirements specifications is also that the developers introduce redundancy by cloning the implementation or, even worse, develop the same functionality more than once.
Analysis Approach. To better understand the actual extent of cloning in industrial requirements specifications, we designed a study in which we use automated clone detection on a set of industrial specifications and then classify the found clones with manual coding. The former gives us a quantification of the phenomenon and the latter a qualitative insight into what information is cloned. We worked in several research pairs and followed the process shown in Fig. 15.

Inspect detected clones
Run clone detection tool We assembled a set of 28 requirements specifications of various length and for a wide variety of systems and domains. We first assigned the specifications randomly among pairs of analysts. Each pair ran a clone detection without any filters using the tool ConQAT. We then inspected the found clones for false positives (pieces of text reported as clones but not actual redundancies). As expected, we found a few false positives such as copyright headers and footers. We added corresponding filters in the form of regular expressions so that the false positives will be ignored. Afterwards, we ran the clone detection again and inspected the results. This continued until we could not find any false positives in a random sample of the clones. This gave us the quantitative results of the study.
Afterwards, we manually coded a random sample of the clones to form categories of the type of information that was cloned. We had no pre-defined codes but developed them while inspecting the clones. As we did not need any larger theory, we skipped axial coding (Section 3). The coding gave us a complete set of categories.
To validate the more subjectively developed categories, we made an independent re-coding of a sample of the categorised clones and found a substantial agreement between the raters. Besides that, we also noted additional effects such as the impact on the implementation. This gave us the qualitative results of the study.
Results of Automatic Analysis. All the quantitative results of our study are shown in Tab. 2. The outcome is clear: There are many industrial requirements specifications that contain cloning, several with high clone coverage values between 30 % and 70 %. The third column gives the number of clone groups per specification. A clone group is a set of clones, the individual copies. There are several specifications with more than 100 clone groups. Hence, there has been a lot of copy&paste in these documents. There are also several specifications, however, with no or almost no cloning. Therefore, it seems to be possible to create specifications without copy&paste. Results of Manual Classification. The manual coding of a sample of clones resulted in 12 categories of cloned information encountered. The categories we identified are described in Table 3 [25]. Overall, we coded a sample of over 400 clone groups almost 500 times because we sometimes assigned a clone group to more than one category, especially if the clones were longer and, hence, contained different aspects. To better understand these different categories and how they occur in practice, we quantified the results by counting the number of clone groups per category in our sample (Fig. 16). The highest number of assigned codes are to the category "Detailed Use Case Steps" with 100 assignments. "Reference" (64) and "UI" (63) follow. The least number of assignments are to the category "Rationale" (8).
Overall, this study was a beneficial combination of manual and automatic text analyses to better understand the extent and type of cloning in requirements specifications. The automatic analysis has the advantage that we could integrate it into a regular quality analysis, for example contained in the nightly build of the corresponding system. This way, introduced clones could be detected and removed early and easily. Nevertheless, it is interesting to regularly also inspect the clones and categorise them to understand if there appear new types of clones. Detailed Use Case Steps Description of one or more steps in a use case that specifies in detail how a user interacts with the system, such as the steps required to create a new customer account in a system. Reference Fragment in a requirements specification that refers to another document or another part of the same document. Examples are references in a use case to other use cases or to the corresponding business process. UI Information that refers to the (graphical) user interface. The specification of which buttons are visible on which screen is an example for this category. Domain Knowledge Information about the application domain of the software. An example are details about what is part of an insurance contract for a software that manages insurance contracts. Interface Description Data and message definitions that describe the interface of a component, function, or system. An example is the definition of messages on a bus system that a component reads and writes. Pre-Condition A condition that has to hold before something else can happen. A common example are pre-conditions for the execution of a specific use case. Side-Condition Condition that describes the status that has to hold during the execution of something. An example is that a user has to remain logged in during the execution of a certain functionality. Configuration Explicit settings for configuring the described component or system.
An example are timing parameters for configuring a transmission protocol. Feature Description of a piece of functionality of the system on a high level of abstraction. Technical Domain Knowledge Information about the used technology for the solution and the technical environment of the system, for example used bus systems in an embedded system.

Post-Condition
Condition that describes what has to hold after something has been finished. Analogous to the pre-conditions, post-conditions are usually part of use cases to describe the system state after the use case execution. Rationale Justification of a requirement. An example is the explicit demand by a certain user group.

Summary
Textual data constitutes the majority of data that is generated in a software project. Yet, we often do not make use of the information and insights contained in this textual data. The problem is that many analysis methods are focused on quantitative data. There are various possibilities of manual as well as automatic analyses now available that help us in employing textual data in better understanding our software projects.
In this chapter, we saw first manual coding to analyse any kind of textual data. We assign different types of codes to the text to abstract and interpret it. This is a highly subjective task which needs appropriate means such as triangulation of analysts to make it more objective. Yet, it can be flexibly applied and allows the analysts to bring in their own expertise in the data analysis. The biggest problem, however, is the large amount of effort necessary for the analysis.
Therefore, we discussed a sample of automatic analyses available, mostly with easily accessible tool support. For example, clone detection is an easy and viable means to detect any syntactic redundancy in textual software artifacts. Topic modelling is another example that can help us to investigate dependencies between documents or quickly get an overview of topics contained in the documents. Visualizations can greatly support all of these automatic analyses to make them easier to comprehend, especially for large text corpora.


extfieldsofstudy:
Computer Science
Mathematics

text:
Enhanced Approximation of Labeled Multi-object Density based on Correlation Analysis

Multi-object density is a fundamental descriptor of a point process and has ability to describe the randomness of number and values of objects, as well as the statistical correlation between objects. Due to its comprehensive nature, it usually has a complicate mathematical structure making the set integral suffering from the curse of dimension and the combinatorial nature of the problem. Hence, the approximation of multi-object density is a key research theme in point process theory or finite set statistics (FISST). Conventional approaches usually discard part or all of statistical correlation mechanically in return for computational efficiency, without considering the real situation of correlation between objects. In this paper, we propose an enhanced approximation of labeled multi-object (LMO) density which evaluates the correlation between objects adaptively and factorizes the LMO density into densities of several independent subsets according to the correlation analysis. Besides, to get a tractable factorization of LMO density, we derive the set marginal density of any subset of the universal labeled RFS, the generalized labeled multi-Bernoulli (GLMB) RFS family and its subclasses. The proposed method takes into account the simplification of the complicate structure of LMO density and the reservation of necessary correlation at the same time.

I. INTRODUCTION
In multi-object inference, the mission is to simultaneously estimate the number of objects as well as their individual states. The applications of multi-object inference involves a wide range of areas, such as forestry [1], biology [2], physics [3], computer vision [4], wireless networks [5], communications [6], multi-target tracking [7], [8], and robotic [9]. The states of objects in multi-object systems such as the coordinates of molecules in a liquid/crystal, trees in a forest, stars in a galaxy is a typical point pattern which is modeled by point processes (specifically simple finite point processes or random finite sets (RFS)) derived from stochastic geometry. The point process theory provides the tools for characterizing the underlying laws of the point patterns. Moreover, finite set statistics (FISST) [10] proposed by Mahler also provides mathematical tools for dealing with RFSs based on a notion of integration and density that is consistent with point process theory.
A fundamental descriptor of point processes is multi-object probability density which can capture the uncertainty of the number and and values of objects, as well as the statistical correlation between objects. Due to its comprehensive nature, the multi-object density usually has a complicate mathematical structure, namely, the multiple hypotheses involving different cardinalities, and the high-dimensional densities conditional on given cardinalities. The core of multi-object estimation is dynamic Bayesian inference. Computing the posterior via Bayes rule requires integrating the product of the prior and likelihood function to obtain the normalizing constant. This integration poses significant practical challenges especially for RFS prior because the complicate structure of multi-object probability density makes the set integral suffer from the curse of dimensionality and the inherently combinatorial nature of the problem.
To solve these problems, tractable approximations of multiobject probability density are necessary and two points during the approximation should be remarked. Firstly, statistical independence between objects can be utilized to enable the parallel implementation to reduce both the number of combination and the dimension of joint density. Secondly, statistical correlation between objects also should be emphasized when required. Statistical correlation usually comes from the ambiguous observation (relative to multiple objects) when considering the posterior multi-object density, or from the interactions between objects in Markov point processes [11]. If one does not consider the correlation when objects strongly depend on each other, multi-object estimation may have a big deviation.
Conventional approach usually approximates multi-object probability density as a certain class of density. There exist two categories of approximate densities: one is to completely discard the correlation between objects and assume thorough independence of objects, such as Poisson process [10], [12], independent identically distributed (i.i.d) process [10], [13], multi-Bernoulli (MB) density [10], [14], [15]. While this kind of densities enjoy many analytical properties, it has been shown that sometimes they are too simplistic for the dynamic Bayesian inference of point processes in complicated scenarios [15]. The other is to cast away only a part of correlation between objects with the typical examples generalized labeled multi-Bernoulli (GLMB) RFS family [16]- [19] and its subclasses. The advantages of the class of GLMB density is that it is a conjugate prior that is also closed under the Chapman-Kolmogorov equation for the standard multi-object system model. Moreover, the set integral of GLMB density only involves the integrals on single-object space getting rid of the curse of dimensionality. However, the class of GLMB densities are not necessarily closed under generic multi-object system because it still assumes independence of objects under each hypothesis involving the existence of different objects. To summarize, the conventional approximate approaches usually discard part or all of statistical correlation mechanically in return for computational efficiency, without regard for the real situation of correlation between objects.
With the recent development of labeled set filters and their advantageous performance compared to previous (unlabeled) random set filters, such as identifying object identities, simplifying the multi-object transition kernel, the study on point processes turns to the labeled set gradually. In this paper, we propose an enhanced approximate approach for labeled multi-object (LMO) density [21] which does approximation based the results of correlation analysis. The proposed method will not approximate the LMO density using a certain type of distribution mechanically regardless the real correlation between objects, but evaluate the correlation between objects adaptively and factorize the LMO density into densities of several independent subsets according to correlation analysis. The proposed method takes into account the simplification of the complicate structure of LMO density and the reservation of necessary correlation at the same time. Note that the proposed method also can be used to make the further approximation of small class of LMO density, such as GLMB RFS family.
The key point of the proposed approximation is the set marginal density. However, the computation of set marginal density is not mature. In [22], we preliminarily give the concept of set marginal and its computing method for joint multi-Bernoulli RFS. In this paper, we further derive the analytical expressions of set marginal density for the universal LMO density, GLMB density family and some subclasses of GLMB density including δ-GLMB and Marginal δ-GLMB (Mδ-GLMB) density, which guarantee the proposed approximation has great practicability.

A. Notations
We adhere to the convention that single-object states are represented by lowercase letters, e.g., x, while multi-object states are represented by uppercase letters, e.g., X, X. To distinguish labeled states and distributions from the unlabeled ones, bold-type letters are adopted for the labeled ones, e.g., x, X, π. Moreover, blackboard bold letters represent spaces, e.g., the state space is represented by X, the label space by L. The collection of all finite sets of X is denoted by F (X).

B. Labeled RFS and LMO Density
A labeled RFS is an RFS whose elements are identified by distinct labels [16], [17]. A labeled RFS with (kinematic) state space X and (discrete) label space L is an RFS on X × L such that each realization X has distinct labels, i.e., |L(X)| = |X|. A labeled RFS and its unlabeled version have the same cardinality distribution. For an arbitrary labeled RFS, its multiobject density can be represented as the expression given in Lemma 1 [21], and our main results in this paper follow from this expression.

C. GLMB RFS Family and Its Subclasses
GLMB RFS family [16] is a class of tractable labeled RFS whose density is conjugate with standard multi-object likelihood function, and is closed under the multi-object Chapman-Kolmogorov equation with respect to the standard multi-object motion model.
A GLMB RFS is a labeled RFS with state space X and (discrete) label space L distributed according to A δ-GLMB RFS with state space X and discrete label space L is a special case of GLMB RFS with where Ξ is a discrete space, i.e., it is distributed according to (7) An marginalized δ-GLMB density π MδGLMB corresponding to the δ-GLMB density π δGLMB in (7) is a probability density of the form where

D. δ-GLMB Density Approximation of LMO Density
An arbitrary LMO density can be approximated as a tractable δ-GLMB density, which is applied to δ-GLMB filter for generic observation model [21].

Lemma 2.
Given any LMO density π, the δ-GLMB density which preserves the cardinality distribution and probability hypothesis density (PHD) of π, and minimizes the Kullback-Leibler divergence from π, is given bŷ

E. Correlation Coefficient
The correlation coefficient [23] is a measure that determines the degree to which two random variables are correlated. The most commonly used measure is the Pearson's correlation coefficient, denoted by ρ, commonly called simply "the correlation coefficient", which is sensitive only to a linear relationship between two variables. The correlation coefficient between two random variables A and B with cov(A, B) the covariance of A and B, and σ A , σ B the standard deviations, is defined as: Our results in this paper follow from this correlation coefficient.

F. Kullback-Leibler divergence
In probability theory and information theory, the Kullback-Leibler divergence (KLD) [34] is a measure of the difference between two probability distributions, and its extension to multi-object densities f (X) and g(X) is given in [35] by where the integral in (13) is a set integral.

III. ENHANCED APPROXIMATE STRATEGY BASED ON CORRELATION ANALYSIS
The LMO density usually is approximated as a given type of multi-object density. In [21], it proposed a tractable δ-GLMB density approximation for an arbitrary LMO density, which matches the PHD and cardinality distribution of LMO density. For standard multi-object system, GLMB density is a closed solution [16], and it can be further approximated using LMB density [20] or Mδ-GLMB density [19]. These approximations usually discard all or part of correlation of original LMO density mechanically for the sake of computation efficiency, without respect for the real situation of correlation between objects.
Actually, correlation of objects play a important role in multi-object estimation. On one hand, when objects exhibit none correlation, the statistical independence can be utilized to enable parallel implementation, and thus simplify computation and enhance estimation performance [19], [24]- [30]. On the other hand, when objects are strongly correlation with each other, their statistics should be jointly considered, or it will produce poor estimation like the the aforementioned strategies.
In practice, the real situation of correlation between objects is usually complicate. Empirical data suggests that in most scenarios not all objects have correlation with each other, but only a small faction of objects has correlation with the other small faction of objects and which object has correlation with which is usually unknown and time-varying.
In this section, we present an enhanced approximate strategy for the approximation of LMO density, in which the correlation between different objects is estimated adaptively, and the original LMO density is factorized into densities of several independent subsets according to the correlation estimate. Besides, we derive the analytical expression of set marginal density of any subsets of the universal LMO RFS and GLMB RFS family.

A. Correlation Estimate
Firstly, we introduce a concept of basic component of labeled RFS in Definition 1, which is important in estimating the correlation between objects.

Definition 1.
For an arbitrary labeled RFS Ψ on space X× L (L is a finite label space), it can be seen as the union of |L| random subsets, i.e., Ψ = ℓ∈L ψ ℓ , with each ψ ℓ on space X × {ℓ}. We refer each random finite subset ψ ℓ , ℓ ∈ L to as a basic component (BC) of Ψ.
A BC ψ ℓ , namely, the random finite subset related to the target with label ℓ, is a labeled Bernoulli RFS which is either the empty set or the singleton set {x, ℓ}.
A BC ψ ℓ is the mathematical representation of the object ℓ, and can describe both the uncertainty of existence and the randomness of state of object ℓ. Hence, to evaluate the correlation between different BCs, we should consider comprehensively from two aspects: 1) the correlation of objects' existences ; 2) the correlation of object states.
1) Absolute Correlation Coefficient of Existence, α ℓ,ℓ ′ : To describe its uncertainty of existence, we define a random variable E ℓ for each BC ψ ℓ as and the statistics of all E ℓ s, ℓ ∈ L are distributed according to the joint probability distribution where "/" denotes the different set, and ω(I) is the joint existence probability of the label set I given in Lemma 1.
We define the absolute correlation coefficient of existence between ψ ℓ and ψ ℓ ′ , ℓ = ℓ ′ ∈ L as where | · | denotes the absolute value of ·, and ρ E ℓ ,E ℓ ′ is the correlation coefficient between E ℓ and E ℓ ′ which can be computed from the joint existence distribution in (15) according to (12).
2) Absolute Correlation Coefficient of State, β ℓ,ℓ ′ : To estimate correlation between states of ψ ℓ and ψ ℓ ′ is on the condition that both ψ ℓ and ψ ℓ ′ exist. Under each hypothesis (involving the existing objects with target label set I ∈ F (L)) where I includes ℓ and ℓ ′ , we can compute a correlation coefficient between (x, ℓ) and (x ′ , ℓ ′ ), denoted as ρ ℓ,ℓ ′ |I , from the corresponding conditional joint probability density p(X)(L(X) = I) defined in Lemma 1, according to (12).
For any two ℓ = ℓ ′ ∈ L, we define the absolute correlation coefficient of state between ψ ℓ and ψ ℓ ′ as where 1 I (I ′ ) denotes an indicator function β ℓ,ℓ ′ actually is the weighted sum of absolute ρ ℓ,ℓ ′ |I s over all hypotheses where the existing target label set I includes ℓ and ℓ ′ .
Note that the absolute correlation coefficient whose value goes form 0 to 1 is a indicator to evaluate the correlation between BCs comprehensively. The value is bigger, the correlation is stronger and vice versa. The value of ω E or ω S varies with different applications. If the correlation of state is emphasized, the value of ω S is larger; otherwise, the value of ω E is larger.

B. Factorization of LMO density
After estimating the correlation between different BCs, we can divide all ψ ℓ s, ℓ ∈ L into several groups such that BCs within a group have correlation, and BCs between different groups exhibit none correlation. We represent each group as the union of the BCs within the group, then Ψ can be divided into several independent random finite subsets, i.e., Ψ = N i=1 Ψ i . Lemma 3. Let Ψ = Ψ 1 ∪ · · · ∪ Ψ N where Ψ 1 , · · · , Ψ N are statistically independent random finite subsets. The probability density of Ψ is related to the probability densities of Ψ 1 , · · · , Ψ n as follows: Lemma 3 is a conclusion provided in [10]. For the labeled RFS, we can obtain the similar conclusions as Proposition 1.
is related to the probability densities of Ψ 1 , · · · , Ψ n as follows According to Proposition 1, we can give an approximation of LMO density which can decrease the dimension of states and reduce the number of hypotheses by utilizing independence and retain correlation if required by adopting LMO densities of independent random finite subsets. However, we still have a problem that how to compute the LMO density of each random subset from the global LMO density, which will be discussed in the following subsection.

C. Set Marginal Density
In [22], we have given concept of the set marginal density as shown in Definition 3 and its generalized computing method as shown in Lemma 4. In this section, Propositions 2−5 provide the specified method to compute the set marginal density of the universal LMO density, GLMB density and some special cases of GLMB density including δ-GLMB and Mδ-GLMB densities, respectively. Definition 3. Let Ψ be an RFS. Then for any random finite subset of Ψ, denoted by Ψ 1 , its multi-object density f Ψ1 (X), is called as set marginal density of Ψ 1 with respect to Ψ.

Lemma 4.
Let Ψ be an RFS. Then for any random finite subset of Ψ, denoted by Ψ 1 , its set marginal density of Ψ 1 with respect to Ψ, denoted by f Ψ1 (X) can be derived by where "δ/δX" denotes a set derivative.
Proposition 3. Assume a GLMB RFS Ψ, whose state space is X × L and multi-object density has the form of (4). If Ψ 1 is a random finite subset of Ψ and its state space is X × L 1 with L 1 ⊆ L, then the set marginal density of Ψ 1 is Proposition 4. Assume a δ-GLMB RFS Ψ on state space is X × L and its multi-object density has the same form of (7). If Ψ 1 is a random finite subset of Ψ and its state space is X × L 1 with L 1 ⊆ L, then the set marginal density of Ψ 1 is Proposition 5. Assume a M δ-GLMB RFS Ψ on state space is X × L and its multi-object density has the same form of (8).
If Ψ 1 is a random finite subset of Ψ and its state space is

IV. NUMERICAL RESULTS
Consider a labeled RFS Ψ on space X × L, where X = R is the field of real number and L = {1, 2, 3}. We design an LMO density of Ψ shown as where

A. Approximations of LMO density
In the subsection, we give three approximations of the LMO density in (28).
• δ-GLMB density approximation,π δGLMB , according to Lemma 2; • Correlation analysis (CA) based approximation,π CA , proposed in Section III; • CA based approximation of the approximate δ-GLMB density,π CA δGLMB , which first approximates the LMO density as a δ-GLMB density and then approximate the resulting δ-GLMB density using the CA based method.
Let Ψ a = ψ 1 ∪ ψ 2 and Ψ b = ψ 3 . According to Proposition 2, we can compute the set marginal density of Ψ a and Ψ b as and Finally, we can obtain the CA based approximation aŝ with L a = {1, 2} and L b = {3}.
According to (19), we can get the absolute correlation coefficients betweenψ 1 ,ψ 2 andψ 3 as where ω E = ω S = 1 2 in (19). One can find that the approximate GLMB density does lose a part of correlation towards the original LMO density comparing (32) and (40).
LetΨ a =ψ 1 ∪ψ 2 and Ψ b =ψ 3 . According to Proposition 3, we can compute the set marginal density ofΨ a andΨ b as Hence, the CA based approximation of the approximated GLMB density iŝ

B. Computational Complexity and Approximate Error Analysis 1) Computational Complexity:
In order to evaluate the computational complexity of the original LMO density and its approximations, some important quantities of π,π δGLMB , π CA andπ CA δGLMB are summarized as Table II,  T 0 : NO. of hypotheses T 1 : NO. of densities on X T 2 : NO. of densities on X 2 T 3 : NO. of densities on X 3 Note that the hypotheses here involves different existing target label sets I, and the hypothesis I = ∅ is omitted because it can be determined by other hypotheses totally.
2) Approximate Error: Herein, we evaluate the approximate error of three approximations in terms of KLD.
3) Summary: δ-GLMB approximation of LMO density actually approximates the conditional joint probability density P (X) under each hypothesis as the product of its marginal densities and retains all hypotheses. Thus, as shown in Table  II, the number of hypotheses ofπ δGLMB are the same as π, and all the densities ofπ δGLMB are on space X. Asπ δGLMB loses a certain degree of correlation, it has the approximate error (the KLD between π andπ δGLMB is not zero). Further comparingπ CA δGLMB withπ δGLMB , we find thatπ δGLMB has redundant statistical information, for it can be further simplified by reducing the number of hypotheses and number of densities without approximate error.
As forπ CA , it reduces the number of hypotheses by utilizing independence, and also retains high-dimensional densities to keep correlation. As shown in Table II, even thoughπ CA has a density on space X 2 whileπ δGLMB does not have, π CA only has 3 densities on space X whileπ δGLMB has 12. Furthermore, the high-dimensional density ofπ CA is retained in return for keeping required correlation. Hence,π CA is a kind of approximation which can balance the computational complexity and approximate error.

V. CONCLUSION
In this paper, we proposed an enhanced approximation of labeled multi-object (LMO) density which evaluates the correlation between objects adaptively and factorizes the LMO density into densities of several independent subsets according to the correlation analysis. Furthermore, to obtain a tractable factorization of LMO density, we derived the set marginal density of any subset of the universal labeled RFS, and GLMB RFS family and its subclasses. Unlike the conventional approximate approach which sacrifices statistical correlation for computational efficiency, the proposed method takes into account the simplification of the complicate structure of LMO density and the reservation of necessary correlation at the same time.