Web Mining –The Ontology Approach
Ee-Peng Lim
Nanyang Technological University
Singapore
Work with: Aixin SUN, Dion GOH, Ming YIN, Myo-Myo NAING, Zhen SUN,Maria MARISSA and other members ofDL group.
The International Advanced Digital Library Conference (IADLC), Nagoya, 2005

Why This Talk?
► Hector Garcia-Molina at JCDL2005“Digital Libraries Initiatives: What I learned (anddidn't) in 10 years”► World Wide Web Tsunami:
 Enormous volume and coverage of content(Everything is free? Heterogeneity?) Large number of users(No difference between producers and consumers)
 Vast number of computers and devices(Many different applications are possible)
2005/9/27

Web Mining - The Ontology Approach2

Some interesting statistics► Google indexes

 > 8 billion web pages
 > 2 billion images
 > 1 billion Usenet messages► Nielsen’s May 2004 survey

 An average surfer went online 30 times for> 24 hours in total during a month►1 time per day►45 mins per day
2005/9/27

Web Mining - The Ontology Approach3

What are the implications toDigital Libraries?
► Search:OPACS vs Google► Browse: Books vs Web Pages/E-Articles► Classification System: Dewey DecimalClassification vs Yahoo! & DMOZ
► Definition of Terms: Encyclopedia vsWikipedia (www.wikipedia.org/)► Users: Library cards vs User blogs
2005/9/27

Web Mining - The Ontology Approach4

Wikipedia

2005/9/27

Web Mining - The Ontology Approach5

User Blog

2005/9/27

Web Mining - The Ontology Approach6

What are the implications to CS
researchers?
► Large amount of Web information waiting to

be processed► Semantic Web► But there are technical challenges!

 Unstructured and semi-structured content
 Links, links, links….
 Large of discipline
 Dynamic Web
2005/9/27

Web Mining - The Ontology Approach7

Use of Web Mining► Types of Web mining: Web content mining Web usage mining Web link mining Web information extraction► Web mining for addressing the challenges► Ontology-based web (content) mining

2005/9/27

Web Mining - The Ontology Approach8

Outline► What is an Ontology?
► Ontology-based Web Mining► Homepage Mining► Homepage Relationship Mining► Conclusion

2005/9/27

Web Mining - The Ontology Approach9Ontology

2005/9/27

Web Mining - The Ontology Approach10Ontology► Genersereth and Nilsson: Ontology is an explicit specification of a set of objects,concepts, and other entities that are presumed to exist
in some area of interest and the relationships that holdthem.
► Ontology is to be shared and reusable► Usually refer to abstract concepts andrelationships (or properties)► Rarely used for concept and relationship instances
2005/9/27

Web Mining - The Ontology Approach11

Our Definition► A set of concepts (C) and relationships (R)between the concepts

2005/9/27

Web Mining - The Ontology Approach12Ontology Research► Ontology construction

 Manual approach: OntoEdit
 Automatic approach: OntoLearn► Ontology representation languages

 Traditional: CycL, Ontolingua, etc..
 Web standards: XML, RDF
 Web-based ontology specification languages:
OIL, DAML+OIL, XOL, SHOE
2005/9/27

Web Mining - The Ontology Approach13

Ontology-based
Web (Content) Mining► Types of web content mining Web page classification
 Web clustering
 Web extraction

2005/9/27

Web Mining - The Ontology Approach14

Web content mining + Ontology► Known instances of ontology entities asadditional features Example: Ontology-based Web site structuremining► Ontology provides background semanticstructures for mining Example: Ontology-based Web classification classifying Web pages as concept instances andWeb page pairs as relationship instances
2005/9/27

Web Mining - The Ontology Approach15

DL Applications ofOntology-based Web Mining► Improved search to Web data
► Better browsing capabilities► Personalization of Web data access

2005/9/27

Web Mining - The Ontology Approach16

Ontology-based Concept Search

2005/9/27

Web Mining - The Ontology Approach17

Ontology-based Relationship Search

2005/9/27

Web Mining - The Ontology Approach18

Ontology-based Browsing► Browsing Movie

homepage

2005/9/27

Web Mining - The Ontology Approach19

Our Ontology-based Web ContentMining Research► Web page classification► Homepage mining► Homepage relationship mining► Focus on web content from a given website

2005/9/27

Web Mining - The Ontology Approach

20Homepage Mining► Given an ontology consisting of concepts

and a web site, find the homepages ofconcept instances

2005/9/27

Web Mining - The Ontology Approach

21

Homepage Relationship Mining► Discovery of homepage pairs as related

concept instances, or relationship instances

22What are the technical challenges?
► Tasks

 Find the homepages
 Assign it with the appropriate concept label
 Identify the relationships among the homepages► Challenges

 Definition of concept instance is subjective
 Web sites organize Web pages in different ways
 Features for identifying relationship instances arelimited
2005/9/27

Web Mining - The Ontology Approach

23

Homepage Mining using Web Units► Idea:A more complete concept instance =homepage + support pages► Web unit: Exactly one homepage
 Zero or more support pages► Web unit-based homepage mining: Finding Web units representing conceptinstances
2005/9/27

Web Mining - The Ontology Approach24

Web Unit
Web Unit of a
CS100 course

Web Unit of aProfessor

2005/9/27

http://..path/course/CS100/CS100.html
http://..path/course/CS100/lecture-programs.html
http://..path/course/CS100/officehours.html
http://..path/course/CS100/instructor.html
http://..path/course/CS100/exams/final.html
http://..path/course/CS100/exams/prelim.html

http://..path/user/johnson/index.html
http://..path/user/johnson/research.html
http://..path/user/johnson/publications.html
http://..path/user/johnson/activities.html
http://..path/user/johnson/students.html
http://..path/user/johnson/teaching.html
http://..path/user/johnson/contact.html
Web Mining - The Ontology Approach25

Web Unit-based Homepage Mining► Two main tasks:

 Find Web pages that form a Web unit anddetermine the role of each page
 Assign concept labels to Web units► Differences between web unit-based

homepage mining and web pageclassification

 Concept-relationship graph vs flat categories
 Web units are not known beforehand
2005/9/27

Web Mining - The Ontology Approach

26

Iterative Web Unit Mining Method(iWUM)
1. Find homepages
2. Find some support pages for each homepage
and construct initial set of web units (may beincomplete) – web fragments
3. Assign concept labels to web units
4. Construct larger web units
5. Reclassify web units
6. Repeat 4-5 until no or little changes to labels
assigned
2005/9/27

Web Mining - The Ontology Approach

27

iWUM

2005/9/27

Web Mining - The Ontology Approach28

Observations on Web Units► Observation 1

 Web pages from the same Web folder are moresemantically related► Observation 2

 Support pages are normally reachable from keypage► Observation 3

 Key page is usually at the highest level of theWeb folder containing the Web unit
2005/9/27

Web Mining - The Ontology Approach29

Observations on Web Units► Observation 4

 Web units of same concept seldom have links betweenthem► Observation 5

 Multi-page Web units of the same concept often residein a set of folders (one for each) under a common
parent folder One-page Web units of the same concept often appear
in the same folder► Observation 6

 Key page of the Web units of the same concept areoften the link targets of a hub page

2005/9/27

Web Mining - The Ontology Approach30

Web Fragment Generation► Associate closely-related Web pages together► Reduce the objects to be classified► Reduce noise in training► Steps:

 Build a directory tree of folders and Web pages
 Compute the connectivity index of each Web folder tomeasure the extent to which the Web pages and folders
under the former are connected Determine the candidate homepages in Web folder withsmall connectivity index values► Web page naming convention: common names for key pages

are “index.html”, “index.htm”, etc..

2005/9/27

Web Mining - The Ontology Approach31Web Fragment Generation► Find Candidate Key Pages

 URL of the page ends with a “/” The folder containing the page and the page sharethe same name, e.g., …path/cs100/cs100.html
 Page file name matches: home, index, welcome,default, and homepage

2005/9/27

Web Mining - The Ontology Approach32

Web Fragment Generation andClassification
Example: Course CS100
1. http://..path/course/CS100/CS100.html [COURSE]
http://..path/course/CS100/lecture-programs.html
http://..path/course/CS100/officehours.html
http://..path/course/CS100/instructor.html
2. http://..path/course/CS100/exams/final.htm [NONE]

Example: Prof Johnson
1. http://..path/user/johnson/index.html [PROF]
http://..path/user/johnson/research.html
http://..path/user/johnson/publications.html
http://..path/user/johnson/activities.html
http://..path/user/johnson/students.html
http://..path/user/johnson/teaching.html
http://..path/user/johnson/contact.html

3. http://..path/course/CS100/exams/prelim.html [NONE]

2005/9/27

Web Mining - The Ontology Approach

33

Web Unit Construction

2005/9/27

Web Mining - The Ontology Approach

34

Web Unit Construction
1. http://..path/course/CS100/CS100.html [COURSE]
http://..path/course/CS100/lecture-programs.html
http://..path/course/CS100/officehours.html
http://..path/course/CS100/instructor.html
2. http://..path/course/CS100/exams/final.htm [NONE]
3. http://..path/course/CS100/exams/prelim.html [NONE]

1. http://..path/course/CS100/CS100.html [COURSE]
http://..path/course/CS100/lecture-programs.html
http://..path/course/CS100/officehours.html
http://..path/course/CS100/instructor.html
http://..path/course/CS100/exams/final.htm
http://..path/course/CS100/exams/prelim.html
2005/9/27

Web Mining - The Ontology Approach

35

Web Unit Classification► Observations 5 and 6:

 Multi-page Web units of the same concept often residein a set of folders (one for each) under a common
parent folder
 Key pages of the Web units of the same concept areoften the link targets of a hub page
► Improve Web unit mining accuracy

 Web site structure features
 Content features

2005/9/27

Web Mining - The Ontology Approach36

Web Unit Classification

2005/9/27

Web Mining - The Ontology Approach37

Web Site Structure Features► Normalized classification score (each web unit) for

each concept► Organization of the web units within the web site

 Closeness to the average depth for each concept
 Highest in-link hub value for each concept
 Precision support of the parent web folder for eachconcept
 Recall support of the parent web folder for each concept► Word features in the web page names and URLs

 Each word (term) in page names and URL
2005/9/27

Web Mining - The Ontology Approach38Performance of iWUM
► Performance is measured by

 Are the web units correctly constructed?
 Are the web units correctly classified?
► Implication of homepage and support pages► iWUM performs well on the WebKB dataset

 4 university websites: Cornell, Texas, Washington andWisconsin 4 concepts: Student, Course, Faculty, Project► iWUM works better for more structured websites
2005/9/27

Web Mining - The Ontology Approach

39

Web Unit-based Homepage
Relationship Mining►Assumptions

►Web units are known by web unit-based homepage
miningRelationships can be determined based on backgroundrelation knowledge
Background relation are represented by interhomepage features

Our proposed method

1. Candidate homepage pair generation
2. Feature acquisition
3. Classifier training
4. Classification

2005/9/27

Web Mining - The Ontology Approach40

Inter-Homepage Features► Navigation Features (N)– links between web pages

 Intra-unit links
 Inter-unit links► Relative Location Features (R) – location in web directory Parent-child Sibling Ancestor-descendent► Common-item Features(E) – shared by homepages

 Email addresses► Supplementary features (A) – additional features derived

for some inter-homepage features

2005/9/27

Web Mining - The Ontology Approach41

Navigation Features (N)2005/9/27

Web Mining - The Ontology Approach

42

Relative Location Features (R)► Parent-child: h2 and h4► Sibling: h2 and h3► Ancestor-descendent: h1 and h4

2005/9/27

Web Mining - The Ontology Approach

43

Experimental Dataset► WebKB Department-of (people, department) Instructor-of (people, course) Member-of (people, project)
University

2005/9/27

Department-of

Instructorof

Member-of

Pos

Neg

PosNeg

PosNegCornell

183

0327654663594Texas

1970427444893851

Washington

161

66512294

1353372

Wisconsin

207

3112

17108

1025148

Web Mining - The Ontology Approach

44

Experimental Results► On the manually labelled web units
Department-ofFeatures

PrRe

Instructor-of

Member-of

F1

Pr

ReF1

Pr

Re

F1

N

0.988

0.796

0.875

0.879

0.651

0.724

0.879

0.884 0.881

NR0.987

1.000

0.994

0.877

0.673

0.737

0.879

0.884 0.881

NE

0.988

0.797

0.876

0.884

0.695

0.759

0.879

0.890 0.883

NRE

0.987

1.000

0.994

0.864

0.698

0.750

0.879

0.890 0.883

2005/9/27

Web Mining - The Ontology Approach45

Experimental Results► On the iWUM mined web units

2005/9/27

Web Mining - The Ontology Approach46

Conclusion► Ontology can be used to add semantics toweb content► We introduce two ontology-based web
content mining problems
 Homepage mining Homepage relationship mining Web Unit to model a concept instance2005/9/27

Web Mining - The Ontology Approach47

Future Research Opportunities► Ontology can be incorporated in other webmining techniques► Digital libraries can benefits from theadditional semantics about web content► Future research Web unit-based searching Link analysis among web units
 Evolution of web units
2005/9/27

Web Mining - The Ontology Approach48

Relevant Publications
►►

►
►
►

►
►
►

Yin Ming, Dion Hoe‐Lian Goh, Ee‐Peng Lim, “On Discovering Concept Entities fromWeb Sites,” International Journal of Web Information Systems (IJWIS), accepted, 2005.
Myo‐Myo Naing, Ee‐Peng Lim, Roger H.L. Chiang, “Extracting Link Chains ofRelationship Instances from a Web Site,” American Society for Information Science andTechnology (JASIST), accepted, 2005.
Aixin Sun and Ee‐Peng Lim, “Web Unit Based Mining of Homepage Relationships,”
JASIST, accepted, 2005.
A. Sun, E.‐P. Lim, W.‐K. Ng, J. Srivastava “Blocking Reduction Strategies in Hierarchical
Text Classification,” IEEE TKDE 16(10):1305‐1308 , 2004.
Myo Myo Naing, Ee‐Peng Lim, Roger Chiang. “CORE: A Search and Browsing Tool for
Semantic Instances of Web Sites,” 7th Asia Pacific Web Conference (APWeb2005),
Shanghai China, March 2005.
A. Sun, E.‐P. Lim, “Web Unit Mining: Finding and Classifying Subgraphs of Web Pages,”
ACM CIKM, 2003.
A. Sun, E.‐P. Lim, and W.‐K. Ng, Performance Measurement Framework for Hierarchical
Text Classification, JASIST 54(11):1014 – 1028, 2003.
A. Sun, E.‐P. Lim, “Web Classification Using Support Vector Machine,” ACM WIDM
2002.

2005/9/27

Web Mining - The Ontology Approach49

Thank You?? ??

2005/9/27

Web Mining - The Ontology Approach50