2.1 Clustering principles

Patent clustering aims to develop meaningful patterns for identifying dominant technologies, forecasting future technological trends, detecting patent infringement, and identifying technological vacuums. It is carried out using structured (e.g. inventors, granted date, etc.) and/or unstructured patent data (free text; e.g. claims, description, etc.). It is clear that although computational algorithms are maturing, human intervention remains essential to bring insight to patent clusters: several authors have emphasised that human expert judgement and outcomes are safest and most accurate on patent analysis and clustering (Fantoni et al. Reference Fantoni, Apreda, Dell’Orletta and Monge2013; Park et al. Reference Park, Kim, Choi and Yoon2013). Moreover, given its importance in the visualisation of patents, the current reliance of computational approaches on the International Patent Classification (IPC) classes is unsatisfactory and can result in landscapes that lack meaning or require further interpretation to be useful (Widodo & Budi Reference Widodo and Budi2011).

The major processes involved in algorithmic clustering are text mining (to extract useful information from the patent corpus) and grouping (to identify similar patents based on structured information received from the text mining step). The key objective of text mining is to extract and classify information that provides some kind of structure for further analysis. For example, function, behaviour and structure (FBS) is one such classification used for text mining purposes (Yan Reference Yan1993). Key requirements for patent text mining are that all patent texts are coded appropriately using a chosen classification mechanism, with steps taken to ensure consistency in applying the established definitions and relationships. Patent grouping is concerned with maximising the similarity within clusters (i.e. homogeneous, with minimal intracluster distance) and the diversity of patents between clusters (i.e. heterogeneous, with maximum intercluster distance) (Yoon & Park Reference Yoon and Park2004). There are various measures for likeness, such as Euclidean distance (Widodo & Budi Reference Widodo and Budi2011), similarity measure (Widodo & Budi Reference Widodo and Budi2011), silhouette measure (Jun et al. Reference Jun, Park and Jang2014), cosine angle (Fu et al. Reference Fu, Cagan and Kotovsky2011) and Hamming distance (Xu et al. Reference Xu, Zhiyong and Bin2013). Table 1 summarises various algorithmic approaches used in the text mining and grouping processes.

Table 1. Summary of text mining and grouping approaches to patent clustering, with highlighted references

Keyword and K-means are the popular approaches used in text mining and grouping respectively. The frequency-inverse document frequency (tf-idf) is often used for determining the importance of words and keyword extraction in text mining (Kukolj et al. Reference Kukolj, Tekic, Nikolic, Panjkov, Pokric, Drazic and Nemet2012). Commonly, a binary patent-keyword/similarity matrix/noun–verb matrix is provided as an input to the K-means clustering approach (Suh & Park Reference Suh and Park2006; Park et al. Reference Park, Kim, Choi and Yoon2013). Indeed, various combinations of the text mining and grouping approaches highlighted in Table 1 can be utilised to find an appropriate clustering process and outcome. Even in doing so, however, there are persistent issues that have been highlighted in the literature.

2.2 Clustering issues

Patent textual analysis is challenging due to variations in writing style, usage of abstract terminologies, and confusion in classifying terms (e.g. technology or effect). When two patents are very different, this leads to ineffective word overlap for text-based analysis methods and causes difficulties in measuring semantic similarities (Xu et al. Reference Xu, Zhiyong and Bin2013; Li et al. Reference Li, Atherton and Harrison2014). The WordNet database can be used to expand patent terms for synonyms, hypernyms, hyponyms and polysemy (one word having multiple meanings) matching to create a level of generalisation. However, this does not contain all of the domain-specific technical terms (Choi et al. Reference Choi, Park, Kang, Lee and Kim2012; Park et al. Reference Park, Kim, Choi and Yoon2013; Abbas et al. Reference Abbas, Zhang and Khan2014). The implicit domain knowledge that is not mentioned in patent documents is missed in cluster analysis procedures (Fu et al. Reference Fu, Chan, Schunn, Cagan and Kotovsky2013b ). Since the importance (weightage) of words is given to frequently occurring terms (Tekic et al. Reference Tekic, Kukolj, Nikolic, Drazic, Pokric, Vitas and Nemet2012), there is a high risk that less-frequent but important terms are not given due attention in the analysis process (Park et al. Reference Park, Kim, Choi and Yoon2013). It has been emphasised that frequencies and co-occurrences of the patterns may not reflect substantial characteristics of inventions (Yoon et al. Reference Yoon, Park and Kim2012), and are unable to discriminate noise from information (Ryley et al. Reference Ryley, Saffer and Gibbs2008), and that keyword vectors cannot reflect structural relationships among technological components (Trappey et al. Reference Trappey, Trappey, Hsu and Hsiao2009; Park et al. Reference Park, Yoon and Kim2011).

In terms of grouping, it is difficult to choose the appropriate technique for a specific task; evaluations have pointed out that the efficiency varies widely for different data sets and approaches (Kukolj et al. Reference Kukolj, Tekic, Nikolic, Panjkov, Pokric, Drazic and Nemet2012; Segev & Kantola Reference Segev and Kantola2012), and that tested cluster similarity scores are not high (Widodo & Budi Reference Widodo and Budi2011). Typically, computational grouping is carried out by the relative distance between text mined data from compared patents, so outcomes do not provide clear categorical clustering (Trappey et al. Reference Trappey, Trappey and Wu2010), which is required to navigate effectively among patents. Most of the clustered outcomes do not clearly establish cluster meaning or provide valuable labels for each cluster (Yoon & Park Reference Yoon and Park2004; Spangler et al. Reference Spangler, Ying, Kreulen, Boyer, Griffin, Alba and Yan2011; Xu et al. Reference Xu, Zhiyong and Bin2013). Additionally, the loss of semantic information through the translation of high-level data in patent documents into specific design functions or requirements can lead to inaccurate clustering (Fan et al. Reference Fan, Lai, Huang and Huang2011; Tekic et al. Reference Tekic, Kukolj, Nikolic, Drazic, Pokric, Vitas and Nemet2012; Abbas et al. Reference Abbas, Zhang and Khan2014) and uncertainty in establishing the distance between patents (Yoon et al. Reference Yoon, Park and Kim2012). Therefore, clustering techniques normally require human expert input at various stages of execution, including semantic annotation (Xu et al. Reference Xu, Zhiyong and Bin2013), extracting key phrases (Kim et al. Reference Kim, Suh and Park2008; Trappey et al. Reference Trappey, Wu, Taghaboni-Dutta and Trappey2011; Choi et al. Reference Choi, Park, Kang, Lee and Kim2012; Park et al. Reference Park, Kim, Choi and Yoon2013), removing irrelevant SAO structures (Choi et al. Reference Choi, Park, Kang, Lee and Kim2012), defining clusters at each iteration (Jun et al. Reference Jun, Park and Jang2014), validating cluster labels (Fu et al. Reference Fu, Chan, Schunn, Cagan and Kotovsky2013b ), feedback for semantic recognition of keywords (Atzmüller & Landl Reference Atzmüller and Landl2009), and verification (Trappey et al. Reference Trappey, Trappey, Peng, Lin and Wang2014). Atzmüller & Landl (Reference Atzmüller and Landl2009) have suggested that it could take up to ‘…6–8 h of the client’s time to develop a thorough understanding of how the map can be interpreted’. This interpretive effort should ideally be carried out when the map is constructed in order to present visualisations that are clear, understandable and useful.

4.1 Task 1: similarity and labelling

4.1.1 Similarity

In the first part of the grouping task, the crowd was asked to create functionally similar groups from the 45 patent set, and if two patents resided in the same group – having a discernible link in functional content – they were designated as a pair. For a set of $N$ patents, the number of possible pairs ( $P$ ) is $P=N\times (N-1)/2$ , so for the 45 patent set, 990 pairs were possible. Table 3 lists the average number of clusters and patent pairs generated through the different approaches. We only used the results of two of the experts (E3 and E4) reported in Fu et al.’s work (refer to Appendix B in Fu et al. (Reference Fu, Chan, Schunn, Cagan and Kotovsky2013b )), as the demarcations between patent groups were unclear in the clusters generated by the other two experts. We found that the average number of clusters generated by the crowd was equivalent to experts’ results. The average number of pairs identified by the crowd (164) was, however, higher than that generated by the two experts ( $69+128/2=99$ ). If a single group has a large number of patents, this will tend to increase the overall number of pairings. For example, the maximum number of patent pairs for a clustered outcome is 513. This is due to the fact that 32 patents are grouped in a single cluster, creating a large number of pairings (496). Thus, spreading the patents more evenly across clusters will reduce the number of pairs. While one of the experts eliminated some patents as irrelevant to the design problem, reducing the experts’ average number of pairs, this practice appears to be equivalent to the crowd workers’ tendency to organise many patents into a single group. For the algorithms, it was found that Fu et al.’s identified 125 pairs and the PatentInspiration software 253. This suggests that Fu’s algorithm is more discerning than the PatentInspiration software, which relies purely on CPC/IPC classifications.

Figure 8 shows the correlation between the number of clusters and the number of connected patent pairs using the different approaches. The average for the crowd has been drawn with an inverse exponential curve, and the other approaches, bar one of the experts, follow this reasonably closely. The overall results show significant variety in patent clusters and labels, which is valuable in providing a range of insights for sifting and prioritisation.

Figure 8. Number of clusters versus number of connected patent pairs for the crowd, experts and algorithms.

Table 3. Composition of clusters and connected patent pairs for different approaches

Examining the performance of the crowd in more detail, Figure 9 shows the frequency of agreement in patent pairings across the 83 workers, i.e. the number of patent pairs. The left of the peak can be characterised as largely speculative pairings between patents with little in common. The peak itself between eight and 12 workers indicates the greatest degree of consensus on patent pairs that are less explicitly linked. The aggregated intellectual interpretation in this region provides a degree of working confidence in the crowd insight. Moreover, to the right of the peak, we see increasingly explicit connections, with a maximum of 58 workers agreeing to a patent pair. At least one crowd worker identified a link in all 989 patent pairs (i.e. there was only one unconnected pair).

Figure 9. The number of crowd workers identifying identical patent pairs.

Table 4 describes the five patent pairs with the highest number of workers (i.e. towards the right of Figure 9) in agreement in more detail. This shows that patent pairs are linked and extensively labelled by the crowd for both explicit (e.g. different valve types) and implicit (e.g. joint assembly and steering device) functional relationships. It is in the less obvious pairings that the crowd provides a distinct advantage over computational approaches. Further analysis to compare expert and algorithm outcomes with aggregated crowd results indicates that only unlinked patent pairs can be predicted with a high degree of confidence (refer to Appendix C for Phi nominal correlation and regression results).

Table 4. Patent pairs with highest generated labels by the crowd compared with algorithmic and expert assessment

We conducted a further analysis with the number of the crowd who agreed on a pairing compared with the percentage of agreement with Expert 1, Expert 2, Fu et al.’s algorithm and the PatentInspiration software (Figure 10). With reference to a particular number of crowd workers, the agreement percentage was calculated by comparing the frequency of crowd pair agreement with the frequency of pair agreement of the various other approaches. This allows us to examine the degree of consensus in identifying patents that should be grouped, are of equal importance, and those that should not. For patent pairs where few of the crowd agreed on a link, we can see a similarly low proportion of proposed pairs by the experts and algorithms. A fairly stable direct relationship holds until we reach patent pairs where the level of crowd agreement is 30 and above. At this point, the relationships break down. For instance, 45 crowd workers agreed on a link between a pair (1 and 43 from Table 4), but experts and algorithmic approaches did not link that particular patent pair. This highlights that both algorithmic and expert approaches have overlooked patent pairs that the crowd workers identified, and supported with meaningful rationale, as relevant.

Figure 10. Percentage of benchmark pairings identified by numbers of crowd workers.

4.1.2 Labelling

The second part of the grouping task was for the crowd to create appropriate labels with rationale. Clusters require appropriate labelling to summarise their content and assist with positioning. Both algorithmic outputs (Fu et al. algorithm and PatentInspiration) produced a list of words as labels, whereas both the crowd and experts can add more context and rationale. Therefore, while a higher number of patents can be processed computationally to provide an overview of a sector or field, there is a potential advantage to be gained from human intervention in the creation of more meaningful cluster labels at a functional level. Table 5 sets out the number of distinct cluster labels generated in both algorithmic and human approaches, and shows that a greater number of labels were generated by the crowd. Given the size of the crowd over the expert group, it would appear that there is convergence in the cluster labelling undertaken by the individual crowd members.

Table 5. Distinct cluster labels generated in various approaches

Fu et al. used two methods to generate labels for each cluster. They selected the top five highest average words generated by the highest average rank labelling method (which ranks each word in the latent semantic analysis space for each patent within a cluster) and the highest cosine similarity labelling method (which generates the highest cosine similarity values in the pool of words for the patents within that cluster). Raising the cut-off values of rank and cosine similarity scores (i.e. choosing the top 10 rather than the top five words with the highest scores) to increase the number of labels generated through the algorithmic approaches may dilute the quality of the generated labels.

Table 6. Comparison of cosine similarity scores for labels across different clustering approaches

Table 7. Grammar percentages for labels generated by various approaches

We went on to compare the labelling of the different methods using the cosine similarity across common label sets (Table 6), with the vector representing the frequency of a particular label presented in each approach. In this case, scores range from 0–1, with a 1 indicating that they are identical. The results show a strong cosine similarity correlation between the experts and the crowd workers, with a much lower match between the experts and the algorithmic approaches.

The reason for this non-convergence is that the algorithmic approaches mostly generated object- (i.e. noun) oriented labels rather than functionally oriented labels. The part-of-speech tagger from NLTK (http://www.nltk.org) was used to categorise labels generated with various approaches with respect to English grammar. Table 7 summarises the grammar percentages for labels generated by various approaches. The grammar percentages demonstrate clear differences between algorithmic and human labelling approaches. The algorithmic approaches mostly chose noun labels, whereas humans provide more context to labels by using a wide variety of English grammars.

4.2 Task 2: Relevance

The third aspect of cluster analysis we explored was the relevance of patents to the design problem. Fu’s clustering algorithm situates the design problem in the dark circle at the top left of Figure 2. This allows us to identify clusters in close proximity, which might provide practical design information to assist in embodiment design, and more distant clusters, which might provide more analogous ideas and principles that could be brought to bear. Most software landscaping tools, however, do not have the capability of locating the design problem in relation to clusters (providing a ‘centre’ to the map), so instead these become visual aids to browse and understand but are more difficult to apply. One of the main advantages in asking experts to review patents in relation to a design problem is the facility for this kind of interpretation: they can find the shallow and deep links for different patent types, consider clustering depending on the nature of the problem and the perspective this brings, and prioritise cluster groups based on this information. The question for us was whether this kind of expert analysis, so dependent on experience and insight, could be replicated in a crowd that has a greater number but less expertise.

A task was therefore set which asked the crowd workers to rate the level of relevance of patents to the design brief of designing a device to collect energy from human motion for use in developing and impoverished rural communities. A 1–6 rating was chosen to match the distance rankings generated by Fu’s algorithm – Figure 2 shows that the patents occupying the top left node are most relevant (a rating of 1), with those five nodes removed in the bottom right (a rating of 6). Figure 11 compares the relevance ranking generated by Fu’s algorithm and the highest cumulative rank frequency marked by the crowd workers. This shows that the crowd rankings concentrated at the extremes of the ranking scale, whereas Fu’s algorithm populated mostly the middle rankings.

Figure 11. Comparison between the crowd and Fu’s algorithm ranking of patent relevance to the given problem.

This indicates a significant variance between the crowd and the computational approach with respect to patent relevance for a particular design problem. While it may have been useful to correlate with relevance as identified by experts, only one of the four in Fu’s analysis (Expert 2) was deemed to have explicitly incorporated distance from the design problem in their clustering. Even for that expert, distance was measured roughly from the design problem circle to the centre of each cluster rather than each patent, so an accurate correlation was not deemed appropriate.

4.3 Evaluation of crowd responses

To assess the validity of the crowd results, evaluation was conducted on the 989 patent pairs and their labels by three evaluators. Evaluator 1 was an RA with eight years of design research experience, Evaluator 2 was a post-doc with a design-related PhD and Evaluator 3 was a senior product design undergraduate with prior experience in patent research. The experts reviewed every patent pair with associated labels, and for each identified whether the crowd had created suitable similarity labels, generating any additional labels not already present, or indicated that there was no link between the patent pair. It took the evaluators an average of approximately 20 hours to complete the analysis of crowd labels. The Cronbach alpha inter-coding reliability scores were 0.811 (Evaluators 1 and 2), 0.878 (Evaluators 1 and 3) and 0.735 (Evaluators 2 and 3), indicating a high level of internal consistency. Table 8 summarises patent pair agreement between the evaluator and crowd results. On average, the evaluators agreed with 59% of the crowd’s patent pairs and labels, and with 6% of the crowd’s patent pairs (but not the labels). The evaluators generated additional labels for 18% of agreed patent pairs.

Table 8. Patent pair agreement between evaluator and crowd results

Figure 12 portrays box plots showing the correlation between the number of evaluators and the number of crowd workers agreeing with a patent pair. A one-way ANOVA was conducted to determine whether the number of crowd workers who agreed with a patent pair varied in relation to the number of evaluators who agreed with a patent pair. The mean $\pm$ standard deviation for zero, one, two and three evaluators in agreement against the crowd results is shown. The number of crowd workers agreeing pairs increased from $9.40\pm 4.71$ for no evaluators agreeing pairs, to $10.87\pm 5.19$ for one evaluator agreeing, to $13.94\pm 5.81$ for two evaluators agreeing, to $17.33\pm 7.88$ for all three evaluators agreeing. The relationship between these groups was statistically significant, ( $F(3,985)=96.392$ , $p<0.001$ ), showing that the likelihood of all evaluators agreeing with a patent pair is high if there are more crowd workers in agreement for that pair.

Figure 12. Box plot illustrating the relationship between the number of agreed evaluators and the number of crowd workers agreed with a patent pair.

4.4 Final cluster outcome

The generation and evaluation of patent pairs, cluster labelling and ranking of relevance to the design problem led to the production of a patent matrix to aid visualisation and understanding of the groupings created. We used ClustergrammerFootnote ¹ to generate a dynamic and interactive matrix visualisation rather than the static patent clusters represented in Section 2. Figure 13 illustrates the partial patent cluster matrix between patents ( $x$ -axis) and generated labels ( $y$ -axis). This choropleth visualisation uses colour variation to represent relevance to the design problem (a darker shade represents stronger relevance to the problem). For example, the ‘material handling’ label is associated with Patents 3, 9 and 14, and Patents 9 and 14 are more relevant to the design problem than Patent 3. The order of the labels and patents is augmented by the software to optimise the clusters; however, this can be controlled by the user if desired.

Figure 13. Visualisation of clustering between patents and patent labels for a cropped patent cluster zone.

The visualisations are highly interactive: they can be reordered according to hierarchical clustering, rank by sum, and rank by variance approaches, and the right top and bottom left sliders can be changed to increase or decrease the number of patent clusters with the slider. This level of control allows designers to dynamically choose and change the number of clusters according to the level of detail or granularity required for the task in hand. The generation of different views in this way can help to identify unique patent to label relationships, and stimulate new insights in relation to the design problem. Furthermore, matrices can be generated for patent to patent and label to label clusters in addition to the patent to label clusters shown in Figure 13. This can help to identify relationships between them and their importance to the design problem. Important labels can be automatically chosen by varying the relevance sum or variance score. This function represents dimensionality reduction performed by various algorithms.

The visualisation communicates the specific relationship between each patent pair with appropriate labels, showing both dense patent clusters and also sparse links between patents. In other words, the map does not categorically isolate different clusters. It comprehensively represents the information generated from the evaluated crowd results, avoiding any loss of information that can occur in the algorithmic refinement process. Additionally, there is the opportunity for designers to navigate patent clusters dynamically according to their requirements: mouse hovering highlights a particular patent and connected label, and clicking a particular cell in the cluster bring up the relevance score. Moreover, the addition of IPC/CPC codes as categories can help engineers to understand how different domains interact with reference to crowd-generated similarity labels.