IDENTIFYING ACTIONS IN DOCUMENTS USING OPTIONS IN MENUS
Documents such as web pages may be regarded as offering various actions; e.g., a website for a movie theater may offer options for viewing movie listings and purchasing tickets. A user may wish to view the set of actions available for a particular document, and/or the performance of an action. However, it may be difficult to identify available actions with acceptable accuracy in an automated manner, and the set of documents (such as the entire worldwide web) may be too voluminous for human identification. In order to identify available actions, the document may be searched for menus containing options, and identifying the actions associated with each option according to an option score. Additionally, documents may be grouped into document categories (e.g., websites for movie theaters and websites for musicians) to facilitate the association options in similar documents with similar sets of actions that are often provided for such documents.
1 . A method of identifying actions available for at least one document on a device having a processor, the method comprising:
executing on the processor instructions configured to:
for respective documents:
identify a document category of the document;
identify at least one menu in the document;
for respective menus, identify at least one option; and
for respective options, assign an option score to the option; and
for respective document categories, identify as actions the options having high option scores among the documents of the document category.
2 . The method of claim 1 :
the device having a document classifier configured to identify document categories of respective documents; and
identifying the document category of a document comprising: invoking the document classifier to identify the document category of the document.
3 . The method of claim 1 , the documents comprising web pages respectively published by a website associated with a website category.
4 . The method of claim 3 , the instructions configured to:
retrieve web pages from respective websites; and
for respective web pages of a website:
identify links to linked web pages within the website, and
retrieve the linked web pages of the website.
5 . The method of claim 3 :
the device having access to a website directory identifying website categories for respective website; and
identifying a website category of a website comprising: identifying the website category associated with the website in the website directory.
6 . The method of claim 1 , assigning an option score to an option comprising:
identifying a part-of-speech feature of the option;
identifying at least one statistical feature of the option; and
assigning an option score to the option based on a part-of-speech feature score based on the part-of-speech feature and a statistical feature score based on the statistical feature.
7 . The method of claim 6 , assigning an option score to an option comprising:
assigning an option score to the option;
assigning a menu score to menu based on the option scores of the options of the menu;
assigning a document score to the document based on the menu scores of the menus of the document; and
updating the option score based on the document score of the document containing the option.
8 . The method of claim 7 , assigning an option score to an option comprising:
assigning an initial option score to the option;
assigning an initial menu score to the menu;
assigning an initial document score to the document score; and
until satisfying an iteration criterion, iteratively updating the option scores of the options, the menu scores of the menus, and the document scores of the documents.
9 . The method of claim 8 , assigning an option score comprising:
assigning the option score according to a mathematical formula comprising:
Score(option t )=α·[POS(option t )+STA(option t )]+β·Σ i,option t in page i Score(document i )
wherein:
option t comprises an option t in a menu of page i;
α comprises a first mathematical weight constant;
POS(option t ) comprises a part-of-speech feature score assigned to the option;
STA(option t ) comprises a statistical feature score assigned to the option;
β comprises a second mathematical weight constant; and
Score(document i ) comprises a score assigned to document i.
10 . The method of claim 8 , assigning a menu score comprising: assigning the menu score according to a mathematical formula comprising:
Score
(
menu
ij
)
=
Σ
j
Score
(
option
ijk
)
,
option
ijk
∈
menu
ij
|
option
ijk
,
option
ijk
∈
menu
ij
|
wherein:
menu ij comprises a menu j in a document i;
option ijk comprises an option k of the menu j in the document i; and
Score(option ijk ) comprises an option score assigned to option k.
11 . The method of claim 8 , assigning a document score comprising: assigning the document score according to a mathematical formula comprising:
Score
(
document
i
)
=
Σ
j
Score
(
menu
ij
)
,
menu
ij
∈
document
i
|
menu
ij
,
menu
ij
∈
document
i
|
wherein:
menu ij comprises a menu j in a document i; and
Score(menu ij ) comprises a menu score assigned to menu j.
12 . The method of claim 1 , comprising: after assigning option scores to respective options, clustering at least two options within a document category associated with an action.
13 . The method of claim 12 , clustering the options comprising:
identifying two options matching an action;
between the two options, identifying a first option having a higher option score sum and a second option having a lower option score sum; and
merging the second option into the first option.
14 . The method of claim 13 , clustering the options comprising:
generating a matrix correlating options with actions;
for respective first rows of the matrix:
comparing the option scores of the first row with the option scores of other rows of the matrix; and
upon identifying a second row of the matrix having similar option scores to the first row and having a higher option score sum than the option score sum of the first row, merging the first row into the second row.
15 . The method of claim 1 , the instructions configured to, upon receiving a request from a user to identify at least one document within a document category associated with an action:
identify the documents of the document category having at least one option of at least one menu associated with the action, and
present the documents to the user.
16 . The method of claim 1 , the instructions configured to, upon receiving a request from a user to identify actions associated with a document:
identify the actions associated with at least one option of at least one menu of the document, and
present the actions to the user.
17 . The method of claim 1 , the instructions configured to, upon receiving a request from a user to perform an action associated with a document,
identify the option associated with the action in the document, and
invoke the option on behalf of the user.
18 . The method of claim 17 :
the documents comprising web pages respectively published by a website; and
invoking the action to the user comprising:
retrieving a web page of the website associated with the action, and
presenting the web page to the user.
19 . A system configured to identify actions available for at least one document on a device having a processor, the system comprising:
a document categorizing component configured to, for respective documents, identify a document category of the document;
an option scoring component configured to, for respective documents:
identify at least one menu in the document;
for respective menus, identify at least one option; and
for respective options, assign an option score to the option; and
an action identifying component configured to, for respective document categories, identify as actions the options having high option scores among the documents of the document category.
20 . A computer-readable storage medium comprising instructions that, when executed on a processor of a device having a document classifier configured to identify document categories of respective documents, identify actions available for at least one document a comprising web page respectively published by a website and associated with a website category by:
retrieving web pages from respective websites by, for respective web pages of a website:
identifying links to linked web pages within the website, and
retrieving the linked web pages of the website;
for respective documents:
invoking the document classifier to identify the document category of the document to identify a document category of the document;
identifying at least one menu in the document;
for respective menus, identifying at least one option; and
for respective options, assigning an option score to the option by:
identifying a part-of-speech feature of the option;
identifying at least one statistical feature of the option;
assigning an initial option score to the option based on a part-of-speech feature score based on the part-of-speech feature and a statistical feature score based on the statistical feature;
assigning an initial menu score to the menu;
assigning an initial document score to the document score; and
until satisfying an iteration criterion:
iteratively updating the option scores of the options based on the document score of the document containing the option according to a mathematical formula comprising:
Score(option t )=α·[POS(option t )+STA(option t )]+β·Σ i,option t in page i Score(document i )
wherein:
option t comprises an option t in a menu of page i;
α comprises a first mathematical weight constant;
POS(option t ) comprises a part-of-speech feature score assigned to the option;
STA(option t ) comprises a statistical feature score assigned to the option;
β comprises a second mathematical weight constant; and
Score(document i ) comprises a score assigned to document i;
iteratively updating the menu scores of the menus based on the option scores of the options of the menu according to a mathematical formula comprising:
Score
(
menu
ij
)
=
Σ
j
Score
(
option
ijk
)
,
option
ijk
∈
menu
ij
|
option
ijk
,
option
ijk
∈
menu
ij
|
wherein:
menu ij comprises a menu j in a document i;
option ijk comprises an option k of the menu j in the document i; and
Score(option ijk ) comprises an option score assigned to option k; and
iteratively updating the document scores of the documents based on the menu scores of the menus of the document according to a mathematical formula comprising:
Score
(
document
i
)
=
Σ
j
Score
(
menu
ij
)
,
menu
ij
∈
document
i
|
menu
ij
,
menu
ij
∈
document
i
|
wherein:
menu ij comprises a menu j in a document i; and
Score(menu ij ) comprises a menu score assigned to menu j;
for respective document categories, identifying as actions the options having high option scores among the documents of the document category;
clustering at least two options within a document category associated with an action by:
generating a matrix correlating options with actions;
for respective first rows of the matrix:
comparing the option scores of the first row with the option scores of other rows of the matrix; and
upon identifying a second row of the matrix having similar option scores to the first row and having a higher option score sum than an option score sum of the first row, merging the first row into the second row;
upon receiving a request from a user to identify at least one document within a document category associated with an action:
identifying the documents of the document category having at least one option of at least one menu associated with the action, and
presenting the documents to the user;
upon receiving a request from a user to identify actions associated with a document:
identifying the actions associated with at least one option of at least one menu of the document, and
presenting the actions to the user; and
upon receiving a request from a user to perform an action associated with a document:
identifying an action associated with the web page;
retrieving a web page of the website associated with the action, and
presenting the web page to the user.