

![0_image_0.png](0_image_0.png)

Figure 2: Schematic diagrams of personal hierarchies created by Flickr users. (a) Ambiguity: the same term may have different meaning ("turkey" can refer to a bird or a country). (b) Conflict: users' different organization schemes can be incompatible (china is a parent of travel **in one hierarchy, but**
the other way around in another). (c) Granularity: users have different levels of expressiveness and specificity, and even mix different specificity levels within the same hierarchy (Scotland **(country) and**
London (city) are both children of UK**). Nodes are colored to aid visualization.** sets can refer to different concepts. Consider the hierarchy in Figure 2 (a), where turkey **collection could be about**
a bird or a country. Similarly, victoria **can either be a** place in Canada or Australia. When combining metadata to learn common folksonomies, we need to be aware of its meaning. Structural and contextual information may help disambiguate metadata.

## 3.4 Structural Noise And Conflicts

Like vocabulary noise, structural noise has a number of sources and can lead to inconsistent or conflicting structures.

Structural noise can arise as a result of variations in individuals' organization preferences. Suppose that, as shown in Figure 2 (b), user A **organizes photos first by activity,**
creating a collection called travel**, and as part of this collection, a set called** china**, for photos of her travel in China.** Meanwhile, user B **organizes photos by location first, creating a collection** china**, with constituent sets** travel, people, food, etc. In one hierarchy, therefore, travel is more general than china**, and in the second hierarchy, it is the other**
way around. Sometimes conflicts are caused by vocabulary differences among individual users. For example, to some users bug is a "pest," a term broader than insect**, while to**
others it is a subclass of insect**. As a result, some users may**
express bug → insect**, while the others express an inverse**
relation. Another source of noise is variation in degree of expertise on a topic. Many users assemble images of spiders in a set called spiders **and assign it to an** insect **collection,** while others correctly assign spiders to arachnid.

## 3.5 Varying Granularity Level

Differences in users' level of expertise and expressiveness may also lead to relatively imprecise metadata. Experts may use specific breed names to tag dog photos, while nonexperts will simply use the tag dog **to annotate them[5]. In**
addition, one user may organize photos first by country and then by city, while another organizes them by country, then subregion and then city, as shown in Figure 2 (c). Combining data from these users potentially generates multiple paths from one concept to another.

## 4. Learning Folksonomies From Structured Metadata

We propose a simple, yet effective approach to combine many personal hierarchies into a global folksonomy that takes above challenges into account. We define a personal hierarchy as a shallow tree, a sapling**, composed of a root node**
r i**and its children, or leaf nodes** hl i 1, ..lij i**. The root node corresponds to a user's collection, and inherits its name, while**
the leaf nodes correspond to the collection's constituent sets and inherit their names. Only a small number of users define multi-level hierarchies; for these, we decompose them and represent them as collections of saplings. At the top level, we have a root node, which corresponds to the top-level collection, and its leaf nodes corresponding to the root's sets or collections. We then construct saplings that correspond to the leaf nodes, which are collections, and so on. We assume that hierarchical relations between a root and its children, r i → l i j**, specify broader-narrower relations. Hence,**
the sapling in Figure 1 (b) is Plant Pests → {Plant Parasites, Sap Suckers, Plant Eaters, **Caterpillars** }.

In addition to hierarchical structure, each sapling carries information derived from tags. On Flickr, users attach tags only to photos; therefore, the tag statistics of a sapling's leaf (set) are aggregated from that set's constituent photos.

Tag statistics are then propagated from the leaves to the parent node. In our example, Plant Parasites **aggregates tag** statistics from all photos in this set, and its parent Plant Pests **contains tag statistics accumulated from all photos in** Plant Parasites **and its siblings. We define a tag statistic**
of node x as τx := {(t1, ft1
),(t2, ft2
), · · ·(tk, ftk
)}**, where** tk and ftk are tag **and its frequency respectively. Hence,** τri is aggregated from all τl i j s.

Given a collection of saplings, specified by many different users, our goal is to aggregate them into a common, denser and deeper tree. Before describing our approach, we first briefly describe data preprocessing steps that address the sparseness and noise challenges listed above.

## 4.1 Data Preprocessing

We extract terms representing concepts from collection and set names. We found that users often combine two or more concepts within a single name, e.g., "Dragonflies/Damselflies", "Mushrooms & Fungi", "Moth at Night." Terms can be joined by bridging words that include prepositions "at",
"of", "in," and conjunctions "and" and "or," or special characters, such as '&', '<', '>**', ':', '/'. We start by tokenizing**
collection and set names on these words and characters. We do not tokenize on white spaces to avoid breaking up terms like "South Africa." We remove terms composed only of nonalphanumeric characters and frequently-used uninformative words, e.g.**, "me" and "myself." We then normalize all terms**
by lowercasing them.

After tokenization, a set or collection name may be split