JP2007080061A - Retrieval method of web page and clustering method of web page - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To provide a method for retrieving a desired web page by clustering according to visual similarity. <P>SOLUTION: Visual information included in the web page is vectorized on the basis of the thumbnail image of the web page. Then, main components are analyzed on the basis of the vector of the visual information and a plurality of feature vectors are obtained for the plurality of web pages. The plurality of feature vectors are clustered, and a result is displayed. Thus, retrieval based on an image, which is impossible by clustering based on character information, is made possible. <P>COPYRIGHT: (C)2007,JPO&INPIT

Description

  The present invention relates to a method for searching a target Web page from among a plurality of Web pages, a hierarchical clustering method used when executing the method, and a feature vector extraction method.

  Japanese Patent Laying-Open No. 2005-122690 (Patent Document 1) analyzes text information from a plurality of information items (Web pages) including text information, obtains feature vectors for the plurality of information items (Web pages), A technique for performing hierarchical clustering based on a vector and visually displaying a hierarchical clustering result on a display screen is disclosed.

  Recently, clustering technology has begun to be utilized as an advanced function of Web search engines. For example, Vivisimo (trademark) [http: //www.vivisimo] and Highlight (trademark) [http://highlit.njit.edu] perform hierarchical clustering based on text information for normal Web search results. And providing a service that automatically assigns a label to each cluster and displays it to the user through natural language processing. Also, AltaVista (trademark) [http://www.altavista.com] performs clustering in the same way for search queries, and displays related words, so that the user can narrow down the query. Service is provided. The Google (registered trademark) news site [http://news.google.com] automatically collects articles from many news sites, classifies them into appropriate topics, and displays them.

The types of Web search can be classified into two types: browsing (directory service as provided by Yahoo (registered trademark)) and querying (Google or AltaVista). Browsing is effective when the information being searched is vague, and querying is considered effective when the information being searched for is clear. However, most of the searches are considered to have many requests that are intermediate between browsing and querying. Therefore, it is possible to provide browsing and an intermediate function by clustering the querying search results. As a result, it is possible to assist in efficiently searching for a page requested by the user.
JP 2005-122690 A

  The common point of the clustering service in the above-mentioned Patent Document 1 and existing Web search results is that processing based on text is performed. Semantic information such as text is important information for clustering. However, the Web page includes many visual features such as images, URLs, and layouts, that is, non-semantic information, in addition to text. If the user visits the querying results sequentially, assuming that the decision on which page and how long to stay is determined instantaneously, this decision is not only for text information (character information) but also for the page as an image. It can be considered that the impression is also used as information. Conventionally, however, the impression of a page as an image has not been considered in clustering. For this reason, it has been difficult to obtain a desired Web page based on an image. In the clustering based on character information, the possibility that a desired Web page can be searched from an unexpected Web page is extremely low.

  An object of the present invention is to provide a method for searching for a desired Web page by performing clustering based on visual similarity.

  Another object of the present invention is to provide a method for searching a desired Web page from Web pages by performing clustering using visual information and character information.

  Another object of the present invention is to provide a Web page clustering method using visual information and character information.

  Another object of the present invention relates to a method for extracting feature vectors of a Web page using visual information and character information.

  A clustering technique in the information search field is used for the purpose of assisting a user in efficiently searching for a target page from the results of a Web search engine or providing a bird's-eye view of search results. Text is often used as a feature of Web pages used for clustering. However, the Web page includes a lot of non-semantic information (visual information) such as images, URLs, and layouts in addition to text (text information). When a user actually classifies Web pages, it is considered that the awareness that Web pages that are similar in visual impression are related is potentially working. Based on this idea, the user is filtering with a visual (image) impression before reading individual Web pages in detail. The present invention is based on this concept.

  Therefore, the present invention performs clustering based on a plurality of feature vectors respectively obtained from a plurality of Web pages, and in a method for searching for a desired Web page from a plurality of Web pages based on the clustering result, Cluster by visual similarity. Therefore, in the present invention, first, the visual information included in the Web page is vectorized. Next, principal component analysis is performed based on the vector of visual information to obtain a plurality of feature vectors for a plurality of Web pages. When these feature vectors are clustered, it becomes possible to perform a search based on an image image, which cannot be retrieved by clustering based on character information. It is also possible to search for a desired Web page from Web pages that cannot be encountered by clustering based on character information.

  The present invention does not deny considering character information. Therefore, it goes without saying that clustering may be performed in consideration of both character information and visual information. In that case, clustering is performed based on a plurality of feature vectors respectively obtained from a plurality of Web pages, and included in the Web page when a desired Web page is searched from the plurality of Web pages based on the clustering result. Character information to be vectorized, and visual information included in the Web page is vectorized. A vector of character information and a vector of visual information are concatenated into a concatenated vector, and principal component analysis is performed based on the concatenated vector to obtain a plurality of feature vectors for a plurality of Web pages. In this way, there are more opportunities to view Web pages that are not encountered in conventional clustering based on character information. As a result, there is a high possibility that a desired Web page that cannot be easily obtained by the conventional method can be searched.

  The method of obtaining visual information is arbitrary, but visual information is obtained by extracting color histograms, extracting edge distributions, two-dimensional fast Fourier transform (FFT), two-dimensional wavelet transform, etc. from web pages. Once obtained, visual information can be extracted more accurately. Although how to obtain the character information is arbitrary, the character information can be obtained by acquiring the keyword position and / or the word histogram from the Web page.

  In addition, when displaying the clustering result on the display screen using a plurality of symbols representing a plurality of Web pages, the color shade that gives the symbol the proximity of the distance between each of the plurality of Web pages determined from the feature vector. You may display by proximity. This makes it easy to visually search for a desired Web page based on the color of the symbol displayed on the screen.

  Further, when displaying the clustering result on the display screen so that the cluster can be identified using a plurality of symbols representing a plurality of Web pages, thumbnails of representative Web pages in the plurality of clusters displayed on the screen are displayed. May be displayed on the screen. In this way, the clustering cluster can be grasped as an image, and it becomes easy to visually search for a desired Web page.

  If each cluster is represented by one web page, it is possible to present the entire search result as a bird's-eye view (bird's eye view) to the user by displaying only the representative web page. is there.

  According to the present invention, by obtaining a feature vector from a vector of visual information and performing clustering, there is an advantage that a search based on an image can be performed, which cannot be performed by clustering based on character information. . It is also possible to search for a desired Web page from Web pages that cannot be encountered by clustering based on character information. Further, if clustering is performed in consideration of both character information and visual information, there is an advantage that it is possible to search for a desired Web page that cannot be easily obtained by the conventional method.

  DESCRIPTION OF THE PREFERRED EMBODIMENTS Embodiments in the case where a Web page search method, Web page clustering method, and feature vector extraction method of the present invention are implemented using a computer will be described in detail below with reference to the drawings. The present invention is based on the fact that a user connected to the Internet has a potential awareness that web pages with similar visual impressions are related when classifying web pages. It is characterized by extracting features from an image and performing clustering. Since the entire Web page has a large amount of data, the present embodiment deals with thumbnail images obtained by reducing the Web page for list display.

  When a desired Web page is searched from a plurality of Web pages, a search engine that can be used via the Internet is used. In a conventionally proposed Web page search method using search engine search results, clustering is performed based on a plurality of feature vectors respectively obtained from a plurality of Web pages, and a plurality of Web pages are determined based on the result of clustering. A desired web page is searched from. In the present embodiment, in particular, Web page groups are clustered based on visual similarity. Therefore, in this embodiment, first, the visual information included in the Web page is vectorized. Specifically, the thumbnail image of the Web page is vectorized using a known vectorization technique. Next, principal component analysis is performed based on the visual information vector of each Web page to obtain a plurality of feature vectors for a plurality of Web pages. The above vectorization and feature vector acquisition are all performed using a computer.

  When visual information is vectorized, it is as follows. FIG. 1 is a diagram used for explaining an example of extracting a feature vector from visual information of a Web page. In the image of the Web page, all parts constituting the page such as a frame, text, and advertisement bar are included in the image. When extracting features from an image, attention may be paid to the shape and arrangement of these components. However, it is not easy to extract these parts from the image. Therefore, in this embodiment, instead of paying attention to such components, the thumbnail images themselves are treated as patterns, and feature extraction is performed using principal component analysis, which is a statistical pattern recognition method. Application of principal component analysis to images has been proposed by Turk et al. In a paper entitled “Eigenfaces for Recognition” (Journal of Cognitive Neuro Science, 3, 1, pp71-86 (1991). Eigenface Technique, which is widely used in facial image recognition, is disclosed, which is applied not only to images but also to removing redundancy from information in vector format, and is a typical feature extraction technique. Principal component analysis is a method of constructing new variables expressed by linear combinations from data statistics expressed in multivariate and summarizing them into uncorrelated “principal components”.

FIG. 1 shows a procedure (steps performed by a computer) of extracting a feature vector from visual information in a thumbnail image of a Web page using principal component analysis. First, i-th image out of N color thumbnail images expressed in red, green and blue (RGB) or HSV [H (Hue / Hue), S (Saturation / Saturation), V (Value / Lightness))] Is expressed as an M-dimensional vector xi with the values of each pixel or the number of vector elements. Also, the average vector of N images

And a vector obtained by subtracting the average vector from each image

Represented by A set of images obtained by subtracting the average vector from each image is a matrix X.

Represented by

The orthonormal basis U = [u ₁ ,... U _L ] that optimally approximates the image set in terms of mean square error is the covariance matrix V of X

Eigenvalue problem

It can be obtained as a solution of Where λ is an eigenvalue. U is assumed to take up to L eigenvectors for the order of the eigenvalue magnitude. The eigenvector u obtained in this way is named an eigenvector or eigenwebpage (Eigen Webpage). At this time, the expression y in the eigenspace for an image x _i is

It can be calculated as follows. Such y is called a feature vector. Each component of y can be interpreted as representing the contribution of each unique Webpage for representing the image x. From the relationship of singular value decomposition of the matrix,

When

Considering the eigenvalue problem as follows, between u and v

The following relationship holds.

  Therefore, when the number N of images is smaller than the image size M, the eigenvalue problem related to [Equation 8] is solved. Then, the eigenvalue u may be calculated. In general, since the image size (the number of vector elements when vectorized using RGB, HSV, etc.) M is considerably larger than the number N of images used for learning, the eigenvalue problem relating to V (covariance matrix) is solved. As a result, the required amount of calculation can be reduced.

  As described above, a learning eigenvector for obtaining a feature vector is obtained. Next, a new thumbnail (Web page) is sequentially selected from a plurality of Web pages obtained as thumbnail data, and this thumbnail is also vectorized using RGB, HSV, or the like. Then, the inner product of this vectorized product and the above-described eigenvector is calculated, and the feature vector of the new thumbnail (Web page) is sequentially obtained.

Next, hierarchical clustering is performed based on the feature vectors obtained from the visual features of a plurality of Web pages (thumbnails) as described above. Hierarchical clustering consists of a top-down approach that starts with one cluster containing all samples and divides the cluster continuously, and starts with one sample of N and continuously merges the clusters at each level. There is a bottom-up approach to form clusters at Since the bottom-up approach has a large number of samples and the number of clusters is reduced, the number of operations for fusing the clusters increases. Therefore, in this embodiment, the top-down approach is performed as shown in FIG. Use. For this clustering, the kmeans method is used. Here, the kmeans method is a method of classifying N samples into k clusters. First, an average vector (μ ₁ , μ ₂ ,... Μ _k ) of _k clusters is randomly selected from samples and initialized. Thereafter, to classify the N samples to the nearest distance mu _i, recalculates the mu _i, repeated until a change in mu _i is eliminated. The Euclidean distance was used for the distance calculation at this time. In the present embodiment, k is the number of thumbnail images displayed at a time on one screen. The number of Web pages that the user sees at a time is set to k = 9 for ease of viewing.

FIG. 3 shows a flow of an example in which the embodiment of the Web page search method of the present invention is actually implemented. First, thumbnail images of a plurality of Web pages as a search result obtained by inputting a search query (data extraction condition) to an existing search engine such as Google (registered trademark) are collected as learning thumbnail images. To do. This state is the same as the thumbnail data shown in the left area of FIG. 4 (or in the right area of FIG. 1). Next, the visual information contained in each thumbnail image is vectorized (Z ₁ ... Z _N ). Then, feature vectors are extracted for each thumbnail image using principal component analysis (learning feature vectors f ₁ ... F _N are obtained for each thumbnail image as shown in FIG. 4). Next, the test thumbnail image is actually vectorized (Zt), the inner product of this vector Zt and the learning feature vector f ₁ ... F _N previously obtained is obtained, and the feature vector of the thumbnail image is obtained. Let ft. In this way, feature vectors are obtained for all test thumbnail images.

  Next, hierarchical clustering of a plurality of feature vectors obtained from a plurality of thumbnail images for testing is created using the above-described kmeans method (in this example, k = 9). When displaying a result to the user, a thumbnail image is displayed with the page having the highest rank of the search result as a representative of the cluster among the k clusters (see the left side of FIG. 5). By clicking the representative thumbnail image of each cluster, the user can refer to the cluster one layer below in the cluster (see the right side of FIG. 5).

  Next, a description will be given of a result of an experiment that implements the above embodiment using the top 200 search results of Google for the search query “search engine”. The left side of FIG. 5 shows the result of hierarchical level 1. The display screen displays the page thumbnail, the URL, and the total number of pages included in the cluster together with the representative thumbnail image of each cluster. The representative Web pages of each cluster had the following results in descending order of the total number of pages.

Search engine site AltaVista (117)
Search engine site Lycos (36)
Webcrawler (19) that returns results from multiple search engines
FreeFind that provides full-text search function in the site (11)
Meta search engine site Kartoo (10)
Walt Disney Internet Group site Go. com (3)
Art-related search engine site Artcyclopedia (2)
Medical World Search (1) providing search engines related to medicine
Trivia Knowledge Site Coolquiz (1)
The one-stage lower cluster (hierarchy level 2) in the AltaVista cluster that forms the largest cluster (total page number 117) is shown on the right side of FIG. The representative web pages of each cluster had the following results in descending order of the total number of pages.

Meta search engine site Vivisimo for clustering search results (36)
Search engine site AltaVista (35)
A site where you can search only pages related to education Education World (19)
Wired Ventures search engine site Hotbot (9)
Search Engine Showdown (7)
Music Robot Site for Music (6)
Meta search engine site Search. com (3)
Search engine site that can input queries in the form of questions Ask Jeeves (3)
Strathclyde University Computer Science site (1)
Detailed analysis of the pages contained in these clusters confirmed that pages with similar layout and color usage were classified into each cluster. For example, in the cluster of AltaVista at the hierarchical level 2, Web pages with very similar image impressions such as search engine sites Google, AlltheWeb, Mamma Metasearch, and Picsearch are classified.

  For comparison, when the same query “search engine” was input to Vivisimo that is clustering based on text, 222 search results were obtained from Vivisimo. The top level hierarchical clusters are:

Search Engine Optimization (73)
Submission (39)
Features (14)
Internet Search (16)
Metasearch (15)
Search engines and directories (11)
Businesses (9)
Yahoo (11)
Technologies (5)
Search Advertising (4)
In Search Engine Optimization and Metasearch clusters, appropriate pages are classified into labels. However, search engine sites that users such as Google, Yahoo, and Lycos are seeking are classified into a cluster called Search Advertising, which is not intuitive. However, Vivisimo performs clustering on search results from search engines such as MSN, Lycos, Looksmart, Wisenut, Open Directory, and Overture, and does not use search results from Google. Therefore, it was difficult to give an objective evaluation.

  In the above embodiment, Web page thumbnail information is converted into feature vectors through principal component analysis, and search results are used for clustering. In a search using a query in a conventional search engine, there are many cases where it is difficult to reach a page requested by a user because there are too many search results output. Therefore, in the next embodiment, the search is facilitated by using both character information and visual information of the Web page.

  In this embodiment, as shown in FIG. 6, character information included in a Web page is vectorized, and visual information included in the Web page is vectorized. A vector of character information and a vector of visual information are concatenated into a concatenated vector, and principal component analysis is performed based on the concatenated vector to obtain a plurality of feature vectors for a plurality of Web pages. How to get visual information is arbitrary. When visual information is obtained by extracting color histograms, edge distributions, two-dimensional fast Fourier transform (FFT), two-dimensional wavelet transform, etc. from a web page, the visual information can be extracted more accurately. . Also, how the character information is obtained is arbitrary. Character information may be obtained by obtaining keyword positions, word histograms, term frequency / inverse document frequency (tf · idf), etc. from a Web page.

  The principal component analysis based on the concatenated vector may be performed in the same manner as in the previous embodiment. Then, clustering is performed based on the feature vector obtained by the principal component analysis. In this way, there are more opportunities to view Web pages that are not encountered in conventional clustering based on character information. As a result, there is a high possibility that a desired Web page that cannot be easily obtained by the conventional method can be searched.

  FIG. 7 is a diagram illustrating a schematic example when the result of clustering is displayed on the display screen. In this example, the clustering result is displayed on the display screen using a plurality of symbols (circular figures) representing a plurality of Web pages. In FIG. 7, the difference in color is displayed in shades of black and white. Web pages belonging to clusters 1 to m are displayed as a collection of symbols. The position of the symbol is proportional to the distance of the cluster. In this example, the closeness of the distance between each of the plurality of Web pages determined from the feature vector is displayed based on the closeness of the color shade attached to the symbol. In this example, even if the clusters are different, if the colors of the symbols are close, it indicates that either the visual information or the character information is close. This makes it easy to visually search for a desired Web page based on the color of the symbol displayed on the screen.

  In this example, representative Web pages in a plurality of clusters displayed on the screen are displayed on the screen as thumbnails. Therefore, the clustering cluster can be grasped as an image, and a desired Web page can be easily searched visually.

It is a figure used in order to explain the example in the case of extracting a feature vector using principal component analysis from the visual information of a Web page. It is a figure which shows the structure of hierarchical clustering. The flow of the example which actually implemented embodiment of the search method of the web page of this invention is shown. It is a figure used in order to explain the way of thinking when obtaining a feature vector by principal component analysis. It is a figure which shows an example of the display mode of the search result by clustering. It is a figure used in order to demonstrate the concept of another embodiment of this invention. It is a figure which shows the other example of the display mode of the search result by clustering.

Claims (8)

A method of performing clustering based on a plurality of feature vectors respectively obtained from a plurality of Web pages, and searching for a desired Web page from the plurality of Web pages based on the result of the clustering,
Vectorizing visual information contained in the web page;
A Web page search method, wherein principal component analysis is performed based on the visual information vector to obtain the plurality of feature vectors for the plurality of Web pages. A method of performing clustering based on a plurality of feature vectors respectively obtained from a plurality of Web pages, and searching for a desired Web page from the plurality of Web pages based on the result of the clustering,
Vectorize the character information contained in the web page,
Vectorizing visual information contained in the web page;
The character information vector and the visual information vector are concatenated into a concatenated vector,
A Web page search method, wherein principal component analysis is performed based on the concatenated vectors to obtain the plurality of feature vectors for the plurality of Web pages.   3. The web page according to claim 1, wherein the visual information is obtained by performing color histogram extraction, edge distribution extraction, two-dimensional fast Fourier transform, two-dimensional wavelet transform, and the like from the web page. Search method.   The Web page search method according to claim 2, wherein the character information is obtained by acquiring a keyword position and / or a word histogram from the Web page.   When the clustering result is displayed on a display screen using a plurality of symbols representing the plurality of Web pages, a color that attaches to the symbol the proximity of each of the plurality of Web pages determined from the feature vector The method of searching for a Web page according to claim 2, wherein the display is based on the closeness of the color of the web page.   When displaying the clustering result on a display screen so that a cluster can be identified using a plurality of symbols representing the plurality of Web pages, representative Web pages in the plurality of clusters displayed on the screen The web page search method according to claim 1, wherein thumbnails are displayed as thumbnails on the screen. A method of performing clustering based on a plurality of feature vectors respectively obtained from a plurality of web pages,
Vectorize the character information contained in the web page,
Vectorizing visual information contained in the web page;
The character information vector and the visual report vector are concatenated into a concatenated vector,
A Web page clustering method, wherein principal component analysis is performed based on the connected vectors to obtain the plurality of feature vectors for the plurality of Web pages. A method for extracting a plurality of feature vectors from a plurality of Web pages,
Vectorize the character information contained in the web page,
Vectorizing visual information contained in the web page;
The character information vector and the visual information vector are concatenated into a concatenated vector,
A feature vector extraction method characterized in that principal component analysis is performed based on the concatenated vectors to obtain the plurality of feature vectors for the plurality of Web pages.