Document (#35465)

Author
Kishida, K.
Title
High-speed rough clustering for very large document collections
Source
Journal of the American Society for Information Science and Technology. 61(2010) no.6, S.1092-1104
Year
2010
Abstract
Document clustering is an important tool, but it is not yet widely used in practice probably because of its high computational complexity. This article explores techniques of high-speed rough clustering of documents, assuming that it is sometimes necessary to obtain a clustering result in a shorter time, although the result is just an approximate outline of document clusters. A promising approach for such clustering is to reduce the number of documents to be checked for generating cluster vectors in the leader-follower clustering algorithm. Based on this idea, the present article proposes a modified Crouch algorithm and incomplete single-pass leader-follower algorithm. Also, a two-stage grouping technique, in which the first stage attempts to decrease the number of documents to be processed in the second stage by applying a quick merging technique, is developed. An experiment using a part of the Reuters corpus RCV1 showed empirically that both the modified Crouch and the incomplete single-pass leader-follower algorithms achieve clustering results more efficiently than the original methods, and also improved the effectiveness of clustering results. On the other hand, the two-stage grouping technique did not reduce the processing time in this experiment.
Theme
Automatisches Klassifizieren

Similar documents (content)

  1. Zamir, O.; Etzioni, O.: Grouper : a dynamic clustering interface to Web search results (1999) 0.23
    0.2338501 = sum of:
      0.2338501 = product of:
        0.835179 = sum of:
          0.019905085 = weight(abstract_txt:time in 1208) [ClassicSimilarity], result of:
            0.019905085 = score(doc=1208,freq=1.0), product of:
              0.061261788 = queryWeight, product of:
                1.0630331 = boost
                4.158956 = idf(docFreq=1836, maxDocs=43254)
                0.013856661 = queryNorm
              0.32491845 = fieldWeight in 1208, product of:
                1.0 = tf(freq=1.0), with freq of:
                  1.0 = termFreq=1.0
                4.158956 = idf(docFreq=1836, maxDocs=43254)
                0.078125 = fieldNorm(doc=1208)
          0.028948918 = weight(abstract_txt:documents in 1208) [ClassicSimilarity], result of:
            0.028948918 = score(doc=1208,freq=1.0), product of:
              0.09001861 = queryWeight, product of:
                1.5782061 = boost
                4.1163282 = idf(docFreq=1916, maxDocs=43254)
                0.013856661 = queryNorm
              0.32158816 = fieldWeight in 1208, product of:
                1.0 = tf(freq=1.0), with freq of:
                  1.0 = termFreq=1.0
                4.1163282 = idf(docFreq=1916, maxDocs=43254)
                0.078125 = fieldNorm(doc=1208)
          0.046150867 = weight(abstract_txt:document in 1208) [ClassicSimilarity], result of:
            0.046150867 = score(doc=1208,freq=2.0), product of:
              0.09750361 = queryWeight, product of:
                1.6425096 = boost
                4.2840466 = idf(docFreq=1620, maxDocs=43254)
                0.013856661 = queryNorm
              0.47332472 = fieldWeight in 1208, product of:
                1.4142135 = tf(freq=2.0), with freq of:
                  2.0 = termFreq=2.0
                4.2840466 = idf(docFreq=1620, maxDocs=43254)
                0.078125 = fieldNorm(doc=1208)
          0.07886885 = weight(abstract_txt:speed in 1208) [ClassicSimilarity], result of:
            0.07886885 = score(doc=1208,freq=1.0), product of:
              0.15339717 = queryWeight, product of:
                1.682134 = boost
                6.5810947 = idf(docFreq=162, maxDocs=43254)
                0.013856661 = queryNorm
              0.514148 = fieldWeight in 1208, product of:
                1.0 = tf(freq=1.0), with freq of:
                  1.0 = termFreq=1.0
                6.5810947 = idf(docFreq=162, maxDocs=43254)
                0.078125 = fieldNorm(doc=1208)
          0.047782764 = weight(abstract_txt:high in 1208) [ClassicSimilarity], result of:
            0.047782764 = score(doc=1208,freq=1.0), product of:
              0.12572595 = queryWeight, product of:
                1.8651339 = boost
                4.8647027 = idf(docFreq=906, maxDocs=43254)
                0.013856661 = queryNorm
              0.3800549 = fieldWeight in 1208, product of:
                1.0 = tf(freq=1.0), with freq of:
                  1.0 = termFreq=1.0
                4.8647027 = idf(docFreq=906, maxDocs=43254)
                0.078125 = fieldNorm(doc=1208)
          0.07763621 = weight(abstract_txt:algorithm in 1208) [ClassicSimilarity], result of:
            0.07763621 = score(doc=1208,freq=1.0), product of:
              0.17376153 = queryWeight, product of:
                2.1926756 = boost
                5.7190075 = idf(docFreq=385, maxDocs=43254)
                0.013856661 = queryNorm
              0.44679746 = fieldWeight in 1208, product of:
                1.0 = tf(freq=1.0), with freq of:
                  1.0 = termFreq=1.0
                5.7190075 = idf(docFreq=385, maxDocs=43254)
                0.078125 = fieldNorm(doc=1208)
          0.5358863 = weight(abstract_txt:clustering in 1208) [ClassicSimilarity], result of:
            0.5358863 = score(doc=1208,freq=4.0), product of:
              0.5502948 = queryWeight, product of:
                6.372057 = boost
                6.232427 = idf(docFreq=230, maxDocs=43254)
                0.013856661 = queryNorm
              0.97381675 = fieldWeight in 1208, product of:
                2.0 = tf(freq=4.0), with freq of:
                  4.0 = termFreq=4.0
                6.232427 = idf(docFreq=230, maxDocs=43254)
                0.078125 = fieldNorm(doc=1208)
        0.28 = coord(7/25)
    
  2. Lee, Y.-H.; Wei, C.-P.; Hu, P.J.-H.: ¬An ontology-based technique for preserving user preferences in document-category evolutions (2011) 0.20
    0.1982721 = sum of:
      0.1982721 = product of:
        0.7081146 = sum of:
          0.04639613 = weight(abstract_txt:vectors in 818) [ClassicSimilarity], result of:
            0.04639613 = score(doc=818,freq=1.0), product of:
              0.10842418 = queryWeight, product of:
                7.8246975 = idf(docFreq=46, maxDocs=43254)
                0.013856661 = queryNorm
              0.42791313 = fieldWeight in 818, product of:
                1.0 = tf(freq=1.0), with freq of:
                  1.0 = termFreq=1.0
                7.8246975 = idf(docFreq=46, maxDocs=43254)
                0.0546875 = fieldNorm(doc=818)
          0.013933559 = weight(abstract_txt:time in 818) [ClassicSimilarity], result of:
            0.013933559 = score(doc=818,freq=1.0), product of:
              0.061261788 = queryWeight, product of:
                1.0630331 = boost
                4.158956 = idf(docFreq=1836, maxDocs=43254)
                0.013856661 = queryNorm
              0.2274429 = fieldWeight in 818, product of:
                1.0 = tf(freq=1.0), with freq of:
                  1.0 = termFreq=1.0
                4.158956 = idf(docFreq=1836, maxDocs=43254)
                0.0546875 = fieldNorm(doc=818)
          0.035098698 = weight(abstract_txt:documents in 818) [ClassicSimilarity], result of:
            0.035098698 = score(doc=818,freq=3.0), product of:
              0.09001861 = queryWeight, product of:
                1.5782061 = boost
                4.1163282 = idf(docFreq=1916, maxDocs=43254)
                0.013856661 = queryNorm
              0.38990492 = fieldWeight in 818, product of:
                1.7320508 = tf(freq=3.0), with freq of:
                  3.0 = termFreq=3.0
                4.1163282 = idf(docFreq=1916, maxDocs=43254)
                0.0546875 = fieldNorm(doc=818)
          0.06461122 = weight(abstract_txt:document in 818) [ClassicSimilarity], result of:
            0.06461122 = score(doc=818,freq=8.0), product of:
              0.09750361 = queryWeight, product of:
                1.6425096 = boost
                4.2840466 = idf(docFreq=1620, maxDocs=43254)
                0.013856661 = queryNorm
              0.66265464 = fieldWeight in 818, product of:
                2.828427 = tf(freq=8.0), with freq of:
                  8.0 = termFreq=8.0
                4.2840466 = idf(docFreq=1620, maxDocs=43254)
                0.0546875 = fieldNorm(doc=818)
          0.08924186 = weight(abstract_txt:grouping in 818) [ClassicSimilarity], result of:
            0.08924186 = score(doc=818,freq=1.0), product of:
              0.21128114 = queryWeight, product of:
                1.9741597 = boost
                7.7236013 = idf(docFreq=51, maxDocs=43254)
                0.013856661 = queryNorm
              0.42238444 = fieldWeight in 818, product of:
                1.0 = tf(freq=1.0), with freq of:
                  1.0 = termFreq=1.0
                7.7236013 = idf(docFreq=51, maxDocs=43254)
                0.0546875 = fieldNorm(doc=818)
          0.13396938 = weight(abstract_txt:technique in 818) [ClassicSimilarity], result of:
            0.13396938 = score(doc=818,freq=7.0), product of:
              0.16576128 = queryWeight, product of:
                2.1416037 = boost
                5.5858 = idf(docFreq=440, maxDocs=43254)
                0.013856661 = queryNorm
              0.80820674 = fieldWeight in 818, product of:
                2.6457512 = tf(freq=7.0), with freq of:
                  7.0 = termFreq=7.0
                5.5858 = idf(docFreq=440, maxDocs=43254)
                0.0546875 = fieldNorm(doc=818)
          0.32486382 = weight(abstract_txt:clustering in 818) [ClassicSimilarity], result of:
            0.32486382 = score(doc=818,freq=3.0), product of:
              0.5502948 = queryWeight, product of:
                6.372057 = boost
                6.232427 = idf(docFreq=230, maxDocs=43254)
                0.013856661 = queryNorm
              0.590345 = fieldWeight in 818, product of:
                1.7320508 = tf(freq=3.0), with freq of:
                  3.0 = termFreq=3.0
                6.232427 = idf(docFreq=230, maxDocs=43254)
                0.0546875 = fieldNorm(doc=818)
        0.28 = coord(7/25)
    
  3. Zhan, J.; Loh, H.T.: Using latent semantic indexing to improve the accuracy of document clustering (2007) 0.18
    0.18223861 = sum of:
      0.18223861 = product of:
        0.911193 = sum of:
          0.019905085 = weight(abstract_txt:time in 2265) [ClassicSimilarity], result of:
            0.019905085 = score(doc=2265,freq=1.0), product of:
              0.061261788 = queryWeight, product of:
                1.0630331 = boost
                4.158956 = idf(docFreq=1836, maxDocs=43254)
                0.013856661 = queryNorm
              0.32491845 = fieldWeight in 2265, product of:
                1.0 = tf(freq=1.0), with freq of:
                  1.0 = termFreq=1.0
                4.158956 = idf(docFreq=1836, maxDocs=43254)
                0.078125 = fieldNorm(doc=2265)
          0.069327 = weight(abstract_txt:reduce in 2265) [ClassicSimilarity], result of:
            0.069327 = score(doc=2265,freq=1.0), product of:
              0.14076085 = queryWeight, product of:
                1.6113611 = boost
                6.304207 = idf(docFreq=214, maxDocs=43254)
                0.013856661 = queryNorm
              0.49251616 = fieldWeight in 2265, product of:
                1.0 = tf(freq=1.0), with freq of:
                  1.0 = termFreq=1.0
                6.304207 = idf(docFreq=214, maxDocs=43254)
                0.078125 = fieldNorm(doc=2265)
          0.06526719 = weight(abstract_txt:document in 2265) [ClassicSimilarity], result of:
            0.06526719 = score(doc=2265,freq=4.0), product of:
              0.09750361 = queryWeight, product of:
                1.6425096 = boost
                4.2840466 = idf(docFreq=1620, maxDocs=43254)
                0.013856661 = queryNorm
              0.6693823 = fieldWeight in 2265, product of:
                2.0 = tf(freq=4.0), with freq of:
                  4.0 = termFreq=4.0
                4.2840466 = idf(docFreq=1620, maxDocs=43254)
                0.078125 = fieldNorm(doc=2265)
          0.047782764 = weight(abstract_txt:high in 2265) [ClassicSimilarity], result of:
            0.047782764 = score(doc=2265,freq=1.0), product of:
              0.12572595 = queryWeight, product of:
                1.8651339 = boost
                4.8647027 = idf(docFreq=906, maxDocs=43254)
                0.013856661 = queryNorm
              0.3800549 = fieldWeight in 2265, product of:
                1.0 = tf(freq=1.0), with freq of:
                  1.0 = termFreq=1.0
                4.8647027 = idf(docFreq=906, maxDocs=43254)
                0.078125 = fieldNorm(doc=2265)
          0.708911 = weight(abstract_txt:clustering in 2265) [ClassicSimilarity], result of:
            0.708911 = score(doc=2265,freq=7.0), product of:
              0.5502948 = queryWeight, product of:
                6.372057 = boost
                6.232427 = idf(docFreq=230, maxDocs=43254)
                0.013856661 = queryNorm
              1.2882385 = fieldWeight in 2265, product of:
                2.6457512 = tf(freq=7.0), with freq of:
                  7.0 = termFreq=7.0
                6.232427 = idf(docFreq=230, maxDocs=43254)
                0.078125 = fieldNorm(doc=2265)
        0.2 = coord(5/25)
    
  4. Mu, T.; Goulermas, J.Y.; Korkontzelos, I.; Ananiadou, S.: Descriptive document clustering via discriminant learning in a co-embedded space of multilevel similarities (2016) 0.16
    0.15903796 = sum of:
      0.15903796 = product of:
        0.6626582 = sum of:
          0.053913105 = weight(abstract_txt:approximate in 3961) [ClassicSimilarity], result of:
            0.053913105 = score(doc=3961,freq=1.0), product of:
              0.10963265 = queryWeight, product of:
                1.0055574 = boost
                7.8681827 = idf(docFreq=44, maxDocs=43254)
                0.013856661 = queryNorm
              0.49176142 = fieldWeight in 3961, product of:
                1.0 = tf(freq=1.0), with freq of:
                  1.0 = termFreq=1.0
                7.8681827 = idf(docFreq=44, maxDocs=43254)
                0.0625 = fieldNorm(doc=3961)
          0.061273307 = weight(abstract_txt:documents in 3961) [ClassicSimilarity], result of:
            0.061273307 = score(doc=3961,freq=7.0), product of:
              0.09001861 = queryWeight, product of:
                1.5782061 = boost
                4.1163282 = idf(docFreq=1916, maxDocs=43254)
                0.013856661 = queryNorm
              0.6806738 = fieldWeight in 3961, product of:
                2.6457512 = tf(freq=7.0), with freq of:
                  7.0 = termFreq=7.0
                4.1163282 = idf(docFreq=1916, maxDocs=43254)
                0.0625 = fieldNorm(doc=3961)
          0.055461597 = weight(abstract_txt:reduce in 3961) [ClassicSimilarity], result of:
            0.055461597 = score(doc=3961,freq=1.0), product of:
              0.14076085 = queryWeight, product of:
                1.6113611 = boost
                6.304207 = idf(docFreq=214, maxDocs=43254)
                0.013856661 = queryNorm
              0.39401293 = fieldWeight in 3961, product of:
                1.0 = tf(freq=1.0), with freq of:
                  1.0 = termFreq=1.0
                6.304207 = idf(docFreq=214, maxDocs=43254)
                0.0625 = fieldNorm(doc=3961)
          0.045218434 = weight(abstract_txt:document in 3961) [ClassicSimilarity], result of:
            0.045218434 = score(doc=3961,freq=3.0), product of:
              0.09750361 = queryWeight, product of:
                1.6425096 = boost
                4.2840466 = idf(docFreq=1620, maxDocs=43254)
                0.013856661 = queryNorm
              0.46376166 = fieldWeight in 3961, product of:
                1.7320508 = tf(freq=3.0), with freq of:
                  3.0 = termFreq=3.0
                4.2840466 = idf(docFreq=1620, maxDocs=43254)
                0.0625 = fieldNorm(doc=3961)
          0.14364865 = weight(abstract_txt:stage in 3961) [ClassicSimilarity], result of:
            0.14364865 = score(doc=3961,freq=2.0), product of:
              0.26547363 = queryWeight, product of:
                3.1295192 = boost
                6.1218853 = idf(docFreq=257, maxDocs=43254)
                0.013856661 = queryNorm
              0.5411033 = fieldWeight in 3961, product of:
                1.4142135 = tf(freq=2.0), with freq of:
                  2.0 = termFreq=2.0
                6.1218853 = idf(docFreq=257, maxDocs=43254)
                0.0625 = fieldNorm(doc=3961)
          0.30314308 = weight(abstract_txt:clustering in 3961) [ClassicSimilarity], result of:
            0.30314308 = score(doc=3961,freq=2.0), product of:
              0.5502948 = queryWeight, product of:
                6.372057 = boost
                6.232427 = idf(docFreq=230, maxDocs=43254)
                0.013856661 = queryNorm
              0.55087394 = fieldWeight in 3961, product of:
                1.4142135 = tf(freq=2.0), with freq of:
                  2.0 = termFreq=2.0
                6.232427 = idf(docFreq=230, maxDocs=43254)
                0.0625 = fieldNorm(doc=3961)
        0.24 = coord(6/25)
    
  5. Guerrero, V.P.; Moya Anegón, F. de: Reduction of the dimension of a document space using the fuzzified output of a Kohonen network (2001) 0.16
    0.15767097 = sum of:
      0.15767097 = product of:
        0.6569624 = sum of:
          0.11248121 = weight(abstract_txt:vectors in 1936) [ClassicSimilarity], result of:
            0.11248121 = score(doc=1936,freq=2.0), product of:
              0.10842418 = queryWeight, product of:
                7.8246975 = idf(docFreq=46, maxDocs=43254)
                0.013856661 = queryNorm
              1.0374181 = fieldWeight in 1936, product of:
                1.4142135 = tf(freq=2.0), with freq of:
                  2.0 = termFreq=2.0
                7.8246975 = idf(docFreq=46, maxDocs=43254)
                0.09375 = fieldNorm(doc=1936)
          0.023318732 = weight(abstract_txt:number in 1936) [ClassicSimilarity], result of:
            0.023318732 = score(doc=1936,freq=1.0), product of:
              0.060287803 = queryWeight, product of:
                1.0545487 = boost
                4.1257625 = idf(docFreq=1898, maxDocs=43254)
                0.013856661 = queryNorm
              0.38679022 = fieldWeight in 1936, product of:
                1.0 = tf(freq=1.0), with freq of:
                  1.0 = termFreq=1.0
                4.1257625 = idf(docFreq=1898, maxDocs=43254)
                0.09375 = fieldNorm(doc=1936)
          0.04912794 = weight(abstract_txt:documents in 1936) [ClassicSimilarity], result of:
            0.04912794 = score(doc=1936,freq=2.0), product of:
              0.09001861 = queryWeight, product of:
                1.5782061 = boost
                4.1163282 = idf(docFreq=1916, maxDocs=43254)
                0.013856661 = queryNorm
              0.5457532 = fieldWeight in 1936, product of:
                1.4142135 = tf(freq=2.0), with freq of:
                  2.0 = termFreq=2.0
                4.1163282 = idf(docFreq=1916, maxDocs=43254)
                0.09375 = fieldNorm(doc=1936)
          0.057339318 = weight(abstract_txt:high in 1936) [ClassicSimilarity], result of:
            0.057339318 = score(doc=1936,freq=1.0), product of:
              0.12572595 = queryWeight, product of:
                1.8651339 = boost
                4.8647027 = idf(docFreq=906, maxDocs=43254)
                0.013856661 = queryNorm
              0.4560659 = fieldWeight in 1936, product of:
                1.0 = tf(freq=1.0), with freq of:
                  1.0 = termFreq=1.0
                4.8647027 = idf(docFreq=906, maxDocs=43254)
                0.09375 = fieldNorm(doc=1936)
          0.09316345 = weight(abstract_txt:algorithm in 1936) [ClassicSimilarity], result of:
            0.09316345 = score(doc=1936,freq=1.0), product of:
              0.17376153 = queryWeight, product of:
                2.1926756 = boost
                5.7190075 = idf(docFreq=385, maxDocs=43254)
                0.013856661 = queryNorm
              0.53615695 = fieldWeight in 1936, product of:
                1.0 = tf(freq=1.0), with freq of:
                  1.0 = termFreq=1.0
                5.7190075 = idf(docFreq=385, maxDocs=43254)
                0.09375 = fieldNorm(doc=1936)
          0.32153177 = weight(abstract_txt:clustering in 1936) [ClassicSimilarity], result of:
            0.32153177 = score(doc=1936,freq=1.0), product of:
              0.5502948 = queryWeight, product of:
                6.372057 = boost
                6.232427 = idf(docFreq=230, maxDocs=43254)
                0.013856661 = queryNorm
              0.58429 = fieldWeight in 1936, product of:
                1.0 = tf(freq=1.0), with freq of:
                  1.0 = termFreq=1.0
                6.232427 = idf(docFreq=230, maxDocs=43254)
                0.09375 = fieldNorm(doc=1936)
        0.24 = coord(6/25)