20IT501_DWDM_U5.ppt

ADVANCED TRENDS

1. 20IT501 –Data Warehousing and
Data Mining
III Year / VI Semester

2. UNIT V -ADVANCED TRENDS
TimeSeriesandSequenceDatainTransactional
Databases-Sentimentanalysis-DescriptiveMining
ofComplexDataObjects-SpatialDatabases-
MultimediaDatabases-Textmining-WorldWide
Web-ApplicationsandTrendsinDataMining-
Casestudiesinvolvingclassificationandclustering

3. Mining Time-Series Data
Atime-seriesdatabaseconsistsofsequencesofvalues
oreventsobtainedoverrepeatedmeasurementsoftime.
Thevaluesaretypicallymeasuredatequaltime
intervals(e.g.,hourly,daily,weekly).
Time-seriesdatabasesarepopularinmany
applications,suchasstockmarketanalysis,economic
andsalesforecastingandetc.

4. Mining Time-Series Data
Withthegrowingdeploymentofalargenumber
ofsensors,telemetrydevices,andotheron-line
datacollectiontools,theamountoftime-series
dataisincreasingrapidly,oftenintheorderof
gigabytesperday(suchasinstocktrading)or
evenperminute(suchasfromNASAspace
programs).

5. Mining Time-Series Data
TrendAnalysis
Therearetwogoalsintime-seriesanalysis:
modelingtimeseries(i.e.,togaininsightintothe
mechanismsorunderlyingforcesthatgeneratethetime
series),and
forecastingtimeseries(i.e.,topredictthefuturevalues
ofthetime-seriesvariables).

6. Mining Time-Series Data
TrendAnalysis–Components:
Trendorlong-termmovements:Theseindicate
thegeneraldirectioninwhichatimeseriesgraph
ismovingoveralongintervaloftime.This
movementisdisplayedbyatrendcurve,oratrend
line.

7. Mining Time-Series Data
TrendAnalysis–Components:
Cyclicmovementsorcyclicvariations:These
refertothecycles,thatis,thelong-term
oscillationsaboutatrendlineorcurve,whichmay
ormaynotbeperiodic.

8. Mining Time-Series Data
TrendAnalysis–Components:
Seasonalmovementsorseasonalvariations:Theseare
systematicorcalendarrelated.
Examplesincludeeventsthatrecurannually,suchasthesudden
increaseinsalesofchocolatesandflowersbeforeValentine’s
DayorofdepartmentstoreitemsbeforeChristmas.
Theobservedincreaseinwaterconsumptioninsummerdueto
warmweatherisanotherexample.

9. Mining Time-Series Data
TrendAnalysis–Components:
Irregularorrandommovements:These
characterizethesporadicmotionoftimeseriesdue
torandomorchanceevents,suchaslabordisputes,
floods,orannouncedpersonnelchangeswithin
companies.

10. Mining Time-Series Data
TrendAnalysis:
Regressionanalysishasbeenapopulartoolformodelingtime
series,findingtrendsandoutliersinsuchdatasets.
Time-seriesmodelingisalsoreferredtoasthedecompositionof
atimeseriesintothesefourbasicmovements.
Thetime-seriesvariableYcanbemodeledaseithertheproduct
ofthefourvariables(i.e.,Y=TxCxSxI)ortheirsum.

11. Mining Time-Series Data
TrendAnalysis:
Acommonmethodfordeterminingtrendisto
calculateamovingaverageofordernasthe
followingsequenceofarithmeticmeans:

12. Mining Time-Series Data
SimilaritySearchinTime-SeriesAnalysis
Unlikenormaldatabasequeries,whichfinddatathat
matchthegivenqueryexactly,asimilaritysearchfinds
datasequencesthatdifferonlyslightlyfromthegiven
querysequence.
Givenasetoftime-seriessequences,S,therearetwo
typesofsimilaritysearches:subsequencematching
andwholesequencematching.

13. Mining Time-Series Data
SimilaritySearchinTime-SeriesAnalysis
SubsequencematchingfindsthesequencesinS
thatcontainsubsequencesthataresimilartoa
givenquerysequencex,whilewholesequence
matchingfindsasetofsequencesinSthatare
similartoeachother(asawhole).

14. Mining Sequence Patterns in
Transactional Databases
Asequencedatabaseconsistsofsequencesofordered
elementsorevents,recordedwithorwithoutaconcrete
notionoftime.
Typicalexamplesincludecustomershopping
sequences,Webclickstreams,biologicalsequences,
sequencesofeventsinscienceandengineering,andin
naturalandsocialdevelopments.

15. Mining Sequence Patterns in
Transactional Databases
Sequentialpatternminingistheminingoffrequently
occurringorderedeventsorsubsequencesaspatterns.
Anexampleofasequentialpatternis“Customerswho
buyaCanondigitalcameraarelikelytobuyanHP
colorprinterwithinamonth.”
Forretaildata,sequentialpatternsareusefulforshelf
placementandpromotions.

16. Mining Sequence Patterns in
Transactional Databases
Givenasetofsequences,whereeachsequence
consistsofalistofevents(orelements)andeachevent
consistsofasetofitems,andgivenauser-specified
minimumsupportthresholdofminsup,sequential
patternminingfindsallfrequentsubsequences,thatis,
thesubsequenceswhoseoccurrencefrequencyinthe
setofsequencesisnolessthanminsup.”

17. Mining Sequence Patterns in
Transactional Databases
Thismodelofsequentialpatternminingisan
abstractionofcustomer-shoppingsequence
analysis.

18. Mining Sequence Patterns in
Transactional Databases
ScalableMethodsforMiningSequential
Patterns:
GSPadoptsacandidategenerate-and-testapproach
usinghorizonaldataformat(wherethedataare
representedas<sequenceID:sequenceofitemsets>,
asusual,whereeachitemsetisanevent).

19. Mining Sequence Patterns in
Transactional Databases
ScalableMethodsforMiningSequentialPatterns:
SPADEadoptsacandidategenerateand-testapproachusing
verticaldataformat(wherethedataarerepresentedas<itemset:
(sequenceID,eventID)>).
Theverticaldataformatcanbeobtainedbytransformingfroma
horizontallyformattedsequencedatabaseinjustonescan.
PrefixSpanisapatterngrowthmethod,whichdoesnotrequire
candidategeneration.

20. Mining Sequence Patterns in
Transactional Databases
GSP:GeneralizedSequentialPatterns
Itisanextensionoftheirseminalalgorithmfor
frequentitemsetmining,knownasApriori.
GSPusesthedownward-closurepropertyof
sequentialpatternsandadoptsamultiple-pass,
candidategenerate-and-testapproach.

21. Mining Sequence Patterns in
Transactional Databases
GSP:GeneralizedSequentialPatterns
Inthefirstscanofthedatabase,itfindsallofthefrequent
items,thatis,thosewithminimumsupport.
Eachsuchitemyieldsa1-eventfrequentsequence
consistingofthatitem.
Eachsubsequentpassstartswithaseedsetofsequential
patterns—thesetofsequentialpatternsfoundinthe
previouspass.

22. Mining Sequence Patterns in
Transactional Databases
GSP:GeneralizedSequentialPatterns
Thisseedsetisusedtogeneratenewpotentially
frequentpatterns,calledcandidatesequences.
Eachcandidatesequencecontainsonemoreitemthan
theseedsequentialpatternfromwhichitwas
generated(whereeacheventinthepatternmaycontain
oneormultipleitems).

23. Mining Sequence Patterns in
Transactional Databases
GSP:GeneralizedSequentialPatterns
Itreducessearchspace,ittypicallyneedstoscanthe
databasemultipletimes.
Itwilllikelygenerateahugesetofcandidate
sequences,especiallywhenmininglongsequences.
Thereisaneedformoreefficientminingmethods.

24. Mining Sequence Patterns in
Transactional Databases
SPADE:(SequentialPAtternDiscoveryusing
Equivalentclasses)
ItisanApriori-basedsequentialpatternmining
algorithmthatusesverticaldataformat.
AswithGSP,SPADErequiresonescantofindthe
frequent1-sequences.

25. Mining Sequence Patterns in
Transactional Databases
SPADE:(SequentialPAtternDiscoveryusing
Equivalentclasses)
Tofindcandidate2-sequences,wejoinallpairsof
singleitemsiftheyarefrequent(therein,itappliesthe
Aprioriproperty),iftheysharethesamesequence
identifier,andiftheireventidentifiersfollowa
sequentialordering

26. Mining Sequence Patterns in
Transactional Databases
SPADE:(SequentialPAtternDiscoveryusing
Equivalentclasses)
Thefirstiteminthepairmustoccurasanevent
beforetheseconditem,wherebothoccurinthesame
sequence.
Similarly,wecangrowthelengthofitemsetsfrom
length2tolength3,andsoon

27. Mining Sequence Patterns in
Transactional Databases
SPADE:(SequentialPAtternDiscoveryusing
Equivalentclasses)
Theuseofverticaldataformat,withthecreationofID
lists,reducesscansofthesequencedatabase.
TheIDlistscarrytheinformationnecessarytofindthe
supportofcandidates.Asthelengthofafrequentsequence
increases,thesizeofitsIDlistdecreases,resultinginvery
fastjoins.

28. Mining Sequence Patterns in
Transactional Databases
MiningMultidimensional,MultilevelSequential
Patterns
Sequenceidentifiers(representingindividualcustomers,
forexample)andsequenceitems(suchasproductsbought)
areoftenassociatedwithadditionalpiecesofinformation.
Miningmultidimensional,multilevelsequentialpatternsis
thediscoveryofinterestingpatternsinsuchabroad
dimensionalspace,atdifferentlevelsofdetail.

29. Mining Sequence Patterns in
Transactional Databases
Constraint-BasedMiningofSequential
Patterns:
wepromoteconstraint-basedmining,which
incorporatesuser-specifiedconstraintstoreduce
thesearchspaceandderiveonlypatternsthatare
ofinteresttotheuser.

30. Mining Sequence Patterns in
Transactional Databases
Constraint-BasedMiningofSequentialPatterns:
First,constraintscanberelatedtotheduration,T,ofa
sequence.
Thedurationmaybethemaximalorminimallengthofthe
sequenceinthedatabase,orauser-specifiedduration
relatedtotime,suchastheyear2005.
Sequentialpatternminingcanthenbeconfinedtothedata
withinthespecifiedduration,T.

31. Mining Sequence Patterns in
Transactional Databases
Constraint-BasedMiningofSequentialPatterns:
Constraintsrelatedtoaspecificduration,suchasa
particularyear,areconsideredsuccinctconstraints.
Aconstraintissuccinctifwecanenumerateallandonly
thosesequencesthatareguaranteedtosatisfythe
constraint,evenbeforesupportcountingbegins.
Suppose,here,T=2005.Allofthesequencesguaranteed
tosatisfytheconstraintbeforeminingbegins.

32. Mining Sequence Patterns in
Transactional Databases
Constraint-BasedMiningofSequentialPatterns:
Finally,ausercanspecifyconstraintsonthekindsof
sequentialpatternsbyproviding“patterntemplates”.
Aserialepisodeisasetofeventsthatoccursinatotal
order,whereasaparallelepisodeisasetofevents
whoseoccurrenceorderingisinsignificant.

33. Mining Sequence Patterns in
Transactional Databases
PeriodicityAnalysisforTime-RelatedSequenceData:
Periodicityanalysisistheminingofperiodicpatterns,that
is,thesearchforrecurringpatternsintime-relatedsequence
data.
Periodicityanalysiscanbeappliedtomanyimportant
areas.Forexample,seasons,tides,planettrajectories,daily
powerconsumptions,dailytrafficpatterns,andweeklyTV
programsallpresentcertainperiodicpatterns.

34. Mining Sequence Patterns in
Transactional Databases
PeriodicityAnalysisforTime-RelatedSequence
Data:
Afullperiodicpatternisapatternwhereeverypoint
intimecontributes(preciselyorapproximately)tothe
cyclicbehaviorofatime-relatedsequence.
Forexample,allofthedaysintheyearapproximately
contributetotheseasoncycleoftheyear.

35. Mining Sequence Patterns in
Transactional Databases
PeriodicityAnalysisforTime-RelatedSequenceData:
Apartialperiodicpatternspecifiestheperiodicbehaviorof
atime-relatedsequenceatsomebutnotallofthepointsin
time.
Forexample,SandyreadstheNewYorkTimesfrom7:00
to7:30everyweekdaymorning,butheractivitiesatother
timesdonothavemuchregularity.

36. Sentiment Analysis
Sentimentanalysis(oropinionmining)isanatural
languageprocessing(NLP)techniqueusedtodetermine
whetherdataispositive,negativeorneutral.
Sentimentanalysisisoftenperformedontextualdata
tohelpbusinessesmonitorbrandandproductsentiment
incustomerfeedback,andunderstandcustomerneeds.

37. Sentiment Analysis
Sentimentanalysisistheuseofnatural
languageprocessing,textanalysis,
computationallinguistics,andbiometricsto
systematicallyidentify,extract,quantify,and
studyaffectivestatesandsubjective
information.

38. Sentiment Analysis
Abasictaskinsentimentanalysisisclassifyingthe
polarityofagiventextatthedocument,sentence,or
feature/aspectlevel—whethertheexpressedopinionin
adocument,asentenceoranentityfeature/aspectis
positive,negative,orneutral.Advanced,"beyond
polarity"sentimentclassificationlooks,forinstance,at
emotionalstatessuchasenjoyment,anger,disgust,
sadness,fear,andsurprise.

39. Sentiment Analysis

40. Sentiment Analysis
Adifferentmethodfordeterminingsentimentis
theuseofascalingsystemwherebywords
commonlyassociatedwithhavinganegative,
neutral,orpositivesentimentwiththemaregiven
anassociatednumberona−10to+10scale(most
negativeuptomostpositive)orsimplyfrom0to
apositiveupperlimitsuchas+4.

41. Sentiment Analysis
Subjectivity/objectivityidentification:
Thistaskiscommonlydefinedasclassifyingagiven
text(usuallyasentence)intooneoftwoclasses:
objectiveorsubjective.
Thesubjectivityofwordsandphrasesmaydependon
theircontextandanobjectivedocumentmaycontain
subjectivesentences(e.g.,anewsarticlequoting
people'sopinions).

42. Sentiment Analysis
Subjectivity/objectivityidentification:
Subjectiveandobjectiveidentification,emerging
subtasksofsentimentanalysistousesyntactic,
semanticfeatures,andmachinelearningknowledgeto
identifyasentenceordocumentarefactsoropinions.
Thetermobjectivereferstotheincidentcarryfactual
information.

43. Sentiment Analysis
Subjectivity/objectivityidentification:
Exampleofanobjectivesentence:
“TobeelectedpresidentoftheIndia,acandidatemust
beatleastthirty-fiveyearsofage.”
Thetermsubjectivedescribestheincidentcontains
non-factualinformationinvariousforms,suchas
personalopinions,judgment,andpredictions.

44. Sentiment Analysis
Subjectivity/objectivityidentification:
Exampleofasubjectivesentence:
'WeIndiansneedtoelectaPrimeMinisterwhois
matureandwhoisabletomakewisedecisions.'

45. Descriptive Mining of
Complex Data Objects
Applicationrequirementshavemotivatedthe
designanddevelopmentofobject-relational
andobject-orienteddatabasesystems.
Thesesystemsorganizealargesetofcomplex
dataobjectsintoclasses,whichareinturn
organizedintoclass/subclasshierarchies.

46. Descriptive Mining of
Complex Data Objects
Eachobjectinaclassisassociatedwith
anobject-identifier
asetofattributesthatmaycontainsophisticated
datastructures
asetofmethods

47. Descriptive Mining of
Complex Data Objects
GeneralizationofStructuredData
Animportantfeatureofobject-relationaland
object-orienteddatabasesistheircapabilityof
storing,accessing,andmodelingcomplex
structure-valueddata,suchasset-andlist-valued
dataanddatawithnestedstructures.

48. Descriptive Mining of
Complex Data Objects
Setvalueddatacanbegeneralizedby,
Generalizationofeachvalueinthesettoits
correspondinghigher-levelconcept,or
Derivationofthegeneralbehavioroftheset,

49. Descriptive Mining of
Complex Data Objects
GeneralizationofStructuredData
Aset-valuedattributemaybegeneralizedtoaset-
valuedorasingle-valuedattribute;
Asingle-valuedattributemaybegeneralizedtoaset-
valuedattributeifthevaluesformalatticeor
“hierarchy”orifthegeneralizationfollowsdifferent
paths.

50. Ex.1 : Generalization of a set-valued attribute.
•Supposethatthehobbyofapersonisaset-
valuedattributecontainingthesetofvalues
{tennis,hockey,soccer,violin,SimCity}.
•Thissetcanbegeneralizedtoasetofhigh-
levelconcepts,suchas{sports,music,
computergames}
•generalizedvaluetoindicatehowmany
elementsaregeneralizedtothatvalue,asin
{sports(3),music(1),computergames(1)},
wheresports(3)indicatesthreekindsofsports,
andsoon.

51. Descriptive Mining of
Complex Data Objects
GeneralizationofStructuredData
List-valuedattributesandsequence-valued
attributescanbegeneralizedinamannersimilarto
thatforset-valuedattributesexceptthattheorder
oftheelementsinthelistorsequenceshouldbe
preservedinthegeneralization.

52. •Example-2: Generalization of list-valued attributes:
•Considerthefollowinglistorsequenceofdatafora
person’seducationrecord:
“((B.Sc.inElectricalEngineering,U.B.C.,Dec.,
1998),
(M.Sc.inComputerEngineering,U.Maryland,May,
2001),
(Ph.D.inComputerScience,UCLA,Aug.,2005))”

53. Descriptive Mining of
Complex Data Objects
GeneralizationofStructuredData
Acomplexstructure-valuedattributemaycontain
sets,tuples,lists,trees,records,andtheir
combinations,whereonestructuremaybenested
inanotheratanylevel.

54. Descriptive Mining of
Complex Data Objects
GeneralizationofStructuredData
Ingeneral,astructure-valuedattributecanbegeneralized
inseveralways,suchas
generalizingeachattributeinthestructurewhilemaintainingthe
shapeofthestructure
flatteningthestructureandgeneralizingtheflattenedstructure,
summarizingthelow-levelstructuresbyhigh-levelconceptsor
aggregation
returningthetypeoranoverviewofthestructure

55. Descriptive Mining of
Complex Data Objects
AggregationandApproximationinSpatialand
MultimediaDataGeneralization
Aggregationandapproximationareanotherimportant
meansofgeneralization.
Theyareespeciallyusefulforgeneralizingattributes
withlargesetsofvalues,complexstructures,and
spatialormultimediadata.

56. Descriptive Mining of
Complex Data Objects
AggregationandApproximationinSpatialand
MultimediaDataGeneralization
Let’stakespatialdataasanexample.
Wewouldliketogeneralizedetailedgeographicpoints
intoclusteredregions,suchasbusiness,residential,
industrial,oragriculturalareas,accordingtoland
usage.

57. Descriptive Mining of
Complex Data Objects
AggregationandApproximationinSpatialandMultimedia
DataGeneralization
Amultimediadatabasemaycontaincomplextexts,graphics,
images,videofragments,maps,voice,music,andotherformsof
audio/videoinformation.
Multimediadataaretypicallystoredassequencesofbyteswith
variablelengths,andsegmentsofdataarelinkedtogetheror
indexedinamultidimensionalwayforeasyreference.

58. Descriptive Mining of
Complex Data Objects
AggregationandApproximationinSpatialandMultimedia
DataGeneralization
Generalizationonmultimediadatacanbeperformedby
recognitionandextractionoftheessentialfeaturesand/or
generalpatternsofsuchdata.
Foranimage,thesize,color,shape,texture,orientation,and
relativepositionsandstructuresofthecontainedobjectsor
regionsintheimagecanbeextractedbyaggregationand/or
approximation.

59. Spatial Data Mining
Aspatialdatabasestoresalargeamountofspace-related
data,suchasmaps,preprocessedremotesensingormedical
imagingdata,andVLSIchiplayoutdata.
Spatialdataminingreferstotheextractionofknowledge,
spatialrelationships,orotherinterestingpatternsnot
explicitlystoredinspatialdatabases.
Suchminingdemandsanintegrationofdataminingwith
spatialdatabasetechnologies.

60. Spatial Data Mining
Acrucialchallengetospatialdataminingisthe
explorationofefficientspatialdatamining
techniquesduetothehugeamountofspatialdata
andthecomplexityofspatialdatatypesand
spatialaccessmethods.
Thetermgeostatisticsisoftenassociatedwith
continuousgeographicspace.

61. Spatial Data Mining
SpatialDataCubeConstructionandSpatial
OLAP
Aspatialdatawarehouseisasubject-oriented,
integrated,time-variant,andnonvolatilecollectionof
bothspatialandnonspatialdatainsupportofspatial
dataminingandspatial-datarelateddecision-making
processes.

62. Spatial Data Mining
SpatialDataCubeConstructionandSpatial
OLAP–TypesofData:
Anonspatialdimension-“hot”fortemperatureand
“wet”forprecipitation
Aspatial-to-nonspatialdimensionisadimension
Aspatial-to-spatialdimension-regionscovering0-5
degrees(Celsius),5-10degrees,andsoon.

63. Spatial Data Mining
SpatialDataCubeConstructionandSpatial
OLAP–TypesofMeasure:
Numericalmeasure:onlynumericaldata.For
example,onemeasureinaspatialdatawarehouse
couldbethemonthlyrevenueofaregion,sothata
roll-upmaycomputethetotalrevenuebyyear,by
county,andsoon.

64. Spatial Data Mining
SpatialDataCubeConstructionandSpatial
OLAP–TypesofMeasure:
Spatialmeasure:Acollectionofpointerstospatial
objects.Theregionswiththesamerangeof
temperatureandprecipitationwillbegroupedintothe
samecell,andthemeasuresoformedcontainsa
collectionofpointerstothoseregions

65. Spatial Data Mining
SpatialDataCubeConstructionandSpatial
OLAP

66. Spatial Data Mining
SpatialDataCubeConstructionandSpatial
OLAP–TypesofMeasure:
regionnamedimension:probelocation<district
<city<region
timedimension:hour<day<month<season<
province

67. Multimedia Data Mining
Amultimediadatabasesystemstoresand
managesalargecollectionofmultimediadata,
suchasaudio,video,image,graphics,speech,
text,document,andhypertextdata,which
containtext,textmarkups,andlinkages.

68. Multimedia Data Mining
SimilaritySearchinMultimediaData
description-basedretrievalsystems,whichbuildindices
andperformobjectretrievalbasedonimagedescriptions,
suchaskeywords,captions,size,andtimeofcreation;
content-basedretrievalsystems,whichsupportretrieval
basedontheimagecontent,suchascolorhistogram,
texture,pattern,imagetopology,andtheshapeofobjects
andtheirlayoutsandlocationswithintheimage.

69. Multimedia Data Mining
SimilaritySearchinMultimediaData–
Approaches:
Colorhistogram–basedsignature:twoimageswith
similarcolorcompositionbutthatcontainvery
differentshapesortexturesmaybeidentifiedas
similar,althoughtheycouldbecompletelyunrelated
semantically.

70. Multimedia Data Mining
SimilaritySearchinMultimediaData–
Approaches:
Multifeaturecomposedsignature:color
histogram,shape,imagetopology,andtexture.The
extractedimagefeaturesarestoredasmetadata,
andimagesareindexedbasedonsuchmetadata.

71. Multimedia Data Mining
SimilaritySearchinMultimediaData–Approaches:
Wavelet-basedsignature:Waveletscaptureshape,
texture,andimagetopologyinformationinasingleunified
framework.
Wavelet-basedsignaturewithregion-based
granularity:thecomputationandcomparisonofsignatures
areatthegranularityofregions,nottheentireimage.

72. Multimedia Data Mining
MultidimensionalAnalysisofMultimediaData
Amultimediadatacubecancontainadditional
dimensionsandmeasuresformultimediainformation,
suchascolor,texture,andshape.
Amultimediadataminingsystemprototypecalled
MultiMediaMiner,whichextendstheDBMinersystem
byhandlingmultimediadata.

73. Multimedia Data Mining
MultidimensionalAnalysisofMultimedia
Data
Eachimagecontainstwodescriptors:afeature
descriptorandalayoutdescriptor.
Theoriginalimageisnotstoreddirectlyinthe
database;onlyitsdescriptorsarestored.

74. Multimedia Data Mining
MultidimensionalAnalysisofMultimediaData
Thedescriptioninformationencompassesfieldslikeimagefile
name,imageURL,imagetype(e.g.,gif,tiff,jpeg,mpeg,bmp,
avi)
Thefeaturedescriptorisasetofvectorsforeachvisual
characteristic.Themainvectorsareacolorvectorcontainingthe
colorhistogramquantizedto512colors(8 8 8forR G B),an
MFC(MostFrequentColor)vector,andanMFO(MostFrequent
Orientation)vector.

75. Multimedia Data Mining
MultidimensionalAnalysisofMultimediaData
Thelayoutdescriptorcontainsacolorlayoutvectorandanedge
layoutvector.Regardlessoftheiroriginalsize,allimagesare
assignedan8x8grid.
Themostfrequentcolorforeachofthe64cellsisstoredinthe
colorlayoutvector,andthenumberofedgesforeachorientation
ineachofthecellsisstoredintheedgelayoutvector.
Othersizesofgrids,like4x4,2x2,and1x1,caneasilybe
derived.

76. Multimedia Data Mining
MultidimensionalAnalysisofMultimediaData
Amultimediadatacubecanhavemanydimensions:
thesizeoftheimageorvideoinbytes;thewidthandheightofthe
frames(orpictures),constitutingtwodimensions;thedateon
whichtheimageorvideowascreated(orlastmodified);theformat
typeoftheimageorvideo;theframesequencedurationinseconds;
theimageorvideoInternetdomain;theInternetdomainofpages
referencingtheimageorvideo(parentURL);thekeywords;acolor
dimension;anedge-orientationdimension;

77. Multimedia Data Mining
ClassificationandPredictionAnalysisofMultimediaData
Datapreprocessingisimportantwhenminingimagedataand
canincludedatacleaning,datatransformation,andfeature
extraction.
Asidefromstandardmethodsusedinpatternrecognition,such
asedgedetectionandHoughtransformations,techniquescanbe
explored,suchasthedecompositionofimagestoeigenvectorsor
theadoptionofprobabilisticmodelstodealwithuncertainty.

78. Multimedia Data Mining
AudioandVideoDataMining
MPEG-k(developedbyMPEG:MovingPictureExpertsGroup)
andJPEGaretypicalvideocompressionschemes.
ThemostrecentlyreleasedMPEG-7,formallynamed
“MultimediaContentDescriptionInterface,”isastandardfor
describingthemultimediacontentdata.
Itsupportssomedegreeofinterpretationoftheinformation
meaning,whichcanbepassedonto,oraccessedby,adeviceora
computer.

79. Multimedia Data Mining
AudioandVideoDataMining
TheaudiovisualdatadescriptioninMPEG-7
includesstillpictures,video,graphics,audio,
speech,three-dimensionalmodels,andinformation
abouthowthesedataelementsarecombinedinthe
multimediapresentation.

80. Text Mining
Textdatabases(ordocumentdatabases),
whichconsistoflargecollectionsof
documentsfromvarioussources,suchasnews
articles,researchpapers,books,digital
libraries,e-mailmessages,andWebpages.

81. Text Mining
TextDataAnalysisandInformationRetrieval
Informationretrievalisconcernedwiththe
organizationandretrievalofinformationfromalarge
numberoftext-baseddocuments.
Applications:On-linelibrarycatalogsystems,on-line
documentmanagementsystems,andthemorerecently
developedWebsearchengines.

82. Text Mining
TextDataAnalysisandInformationRetrieval:
Tolocaterelevantdocumentsinadocumentcollectionbasedon
auser’squery,whichisoftensomekeywordsdescribingan
informationneed.
Ausertakestheinitiativeto“pull”therelevantinformationout
fromthecollection(short-term)
To“push”anynewlyarrivedinformationitemtoauserifthe
itemisjudgedasbeingrelevanttotheuser’sinformationneed.
(Longterm)

83. Text Mining
BasicMeasuresforTextRetrieval:Precision
andRecall:
Precision:Thisisthepercentageofretrieved
documentsthatareinfactrelevanttothequery
(i.e.,“correct”responses).Itisformallydefinedas

84. Text Mining
BasicMeasuresforTextRetrieval:Precision
andRecall:
Recall:Thisisthepercentageofdocumentsthat
arerelevanttothequeryandwere,infact,
retrieved.Itisformallydefinedas

85. Text Mining
BasicMeasuresforTextRetrieval:Precisionand
Recall:
Aninformationretrievalsystemoftenneedstotrade
offrecallforprecisionorviceversa.Onecommonly
usedtrade-offistheF-score,whichisdefinedasthe
harmonicmeanofrecallandprecision:

86. Text Mining
TextRetrievalMethods-Booleanretrievalmodel
Documentisrepresentedbyasetofkeywordsandauser
providesaBooleanexpressionofkeywords,suchas“carand
repairshops,”“teaorcoffee,”or“databasesystemsbutnot
Oracle.”
TheretrievalsystemwouldtakesuchaBooleanqueryand
returndocumentsthatsatisfytheBooleanexpression.
Booleanretrievalmethodgenerallyonlyworkswellwhenthe
userknowsalotaboutthedocumentcollection

87. Text Mining
TextRetrievalMethods-VectorSpacemodel
representadocumentandaquerybothasvectorsina
high-dimensionalspacecorrespondingtoallthe
keywordsanduseanappropriatesimilaritymeasureto
computethesimilaritybetweenthequeryvectorand
thedocumentvector.
Thesimilarityvaluescanthenbeusedforranking
documents.

88. Text Mining
TextRetrievalMethods-VectorSpacemodel
Thefirststepinmostretrievalsystemsistoidentify
keywordsforrepresentingdocuments,apreprocessing
stepoftencalledtokenization.
Astoplistisasetofwordsthataredeemed
“irrelevant.”Forexample,a,the,of,for,with,andso
onarestopwords,eventhoughtheymayappear
frequently.

89. Text Mining
TextRetrievalMethods-VectorSpacemodel
Agroupofdifferentwordsmaysharethesameword
stem.
Atextretrievalsystemneedstoidentifygroupsof
wordswherethewordsinagrouparesmallsyntactic
variantsofoneanotherandcollectonlythecommon
wordstempergroup.

90. Text Mining
TextRetrievalMethods-VectorSpacemodel
Thetermfrequencybethenumberofoccurrences
oftermtinthedocumentd,thatis,freq(d,t).

91. Text Mining
TextRetrievalMethods-VectorSpacemodel
Arepresentativemetricisthecosinemeasure,
definedasfollows.
Letv1andv2betwodocumentvectors.Their
cosinesimilarityisdefinedas

92. Text Mining
TextIndexingTechniques-invertedindex:
Aninvertedindexisanindexstructurethatmaintains
twohashindexedorB+-treeindexedtables:document
tableandtermtable,where
documenttableconsistsofasetofdocumentrecords,each
containingtwofields:docidandpostinglist,whereposting
listisalistofterms(orpointerstoterms)thatoccurinthe
document,sortedaccordingtosomerelevancemeasure.

93. Text Mining
TextIndexingTechniques-invertedindex:
Aninvertedindexisanindexstructurethatmaintains
twohashindexedorB+-treeindexedtables:document
tableandtermtable,where
termtableconsistsofasetoftermrecords,eachcontaining
twofields:termidandpostinglist,wherepostinglist
specifiesalistofdocumentidentifiersinwhichtheterm
appears.

94. Text Mining
TextIndexingTechniques-signaturefile:
Asignaturefileisafilethatstoresasignaturerecordfor
eachdocumentinthedatabase
Eachsignaturehasafixedsizeofbbitsrepresenting
terms.
Eachbitofadocumentsignatureisinitializedto0.Abitis
setto1ifthetermitrepresentsappearsinthedocument.

95. Mining the World Wide Web
TheWorldWideWebservesasahuge,widely
distributed,globalinformationservicecenter
fornews,advertisements,consumer
information,financialmanagement,education,
government,e-commerce,andmanyother
informationservices.
TheWebalsocontainsarichanddynamic
collectionofhyperlinkinformationandWeb
pageaccessandusageinformation,providing
richsourcesfordatamining.

96. MiningtheWebPageLayoutStructure:
•Webpagesarealsoregardedassemi-structureddata.
ThebasicstructureofaWebpageisitsDOM
(DocumentObjectModel)structure.
•TheDOMstructureofaWebpageisatreestructure,
whereeveryHTMLtaginthepagecorrespondstoa
nodeintheDOMtree.TheWebpagecanbesegmented
bysomepredefinedstructuraltags.Usefultagsinclude
<P>(paragraph),<TABLE>(table),<UL>(list),<H1>
to<H6>(heading),etc.ThustheDOMstructurecanbe
usedtofacilitateinformationextraction.

97. APPLICATIONS AND TRENDS
IN DATA MINING
•Financial Data Analysis
•Retail Industry
•Telecommunication Industry
•Biological Data Analysis
•Other Scientific Applications
•Intrusion Detection

98. •Financial Data Analysis
–Designandconstructionofdatawarehousesfor
multidimensionaldataanalysisanddatamining.
–Loanpaymentpredictionandcustomercreditpolicy
analysis.
–Classificationandclusteringofcustomersfor
targetedmarketing.
–Detectionofmoneylaunderingandotherfinancial
crimes.

99. •Retail Industry
–DataMininghasitsgreatapplicationinRetail
Industrybecauseitcollectslargeamountdatafromon
sales,customerpurchasinghistory,goods
transportation,consumptionandservices.

100. •TelecommunicationIndustry
–TodaytheTelecommunicationindustryisoneofthe
mostemergingindustriesprovidingvariousservices
suchasfax,pager,cellularphone,Internetmessenger,
images,e-mail,webdatatransmissionetc.

101. •BiologicalDataAnalysis
–Nowadaysweseethatthereisvastgrowthinfield
ofbiologysuchasgenomics,proteomics,functional
Genomicsandbiomedicalresearch.Biologicaldata
miningisveryimportantpartofBioinformatics.

102. •Other Scientific Applications
–Theapplicationsdiscussedabovetendtohandle
relativelysmallandhomogeneousdatasetsforwhich
thestatisticaltechniquesareappropriate.Huge
amountofdatahavebeencollectedfromscientific
domainssuchasgeosciences,astronomyetc.

103. •IntrusionDetection
–Intrusionreferstoanykindofactionthatthreatens
integrity,confidentiality,oravailabilityofnetwork
resources.Inthisworldofconnectivitysecurityhas
becomethemajorissue.Withincreasedusageof
internetandavailabilityoftoolsandtricksforintruding
andattackingnetworkpromptedintrusiondetectionto
becomeacriticalcomponenttofnetwork
administration.